http://blog.sciencenet.cn/home.php?mod=space&uid=404069&do=blog&id=297233

?

剛加入復(fù)雜網(wǎng)絡(luò)圈子，暫時(shí)還沒有成熟的研究內(nèi)容，先發(fā)個(gè)資料性的東西占坑：）

作復(fù)雜網(wǎng)絡(luò)研究離不開對各種實(shí)際或模擬網(wǎng)絡(luò)的統(tǒng)計(jì)、計(jì)算、繪圖等工作。對于一般性的工作，我們可以用Pajek、Netdraw和Ucinet等軟件完成。但對一些特殊應(yīng)用（比如自己開發(fā)了一個(gè)新模型），現(xiàn)有的軟件不能提供相應(yīng)的建模或計(jì)算功能，這時(shí)就必須要通過編程的辦法來解決問題了。

在這篇文章中，向大家介紹我使用過的4個(gè)面向圖論及復(fù)雜網(wǎng)絡(luò)分析的程序庫，它們可以（分別或同時(shí)）用C、C++、C#和Python等語言調(diào)用。同時(shí)這些庫都是開源的，可以通過研讀它們的源代碼提高編程水平。

好，下邊開始介紹，第一位出場的是：

一、Boost Graph Library —— “準(zhǔn)”C++標(biāo)準(zhǔn)庫

Boost Graph Library（BGL）是C++ Boost庫的成員之一。Boost是一個(gè)經(jīng)過千錘百煉的C++庫，作為標(biāo)準(zhǔn)模板庫STL的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的發(fā)動(dòng)機(jī)之一。Boost庫由C++標(biāo)準(zhǔn)委員會(huì)庫工作組成員發(fā)起，在C++社區(qū)中影響甚大，是不折不扣的“準(zhǔn)”標(biāo)準(zhǔn)庫。

BGL的特點(diǎn)是靈活性和高運(yùn)行效率。BGL是以模板的形式提供的，這意味著你可以在模板的基礎(chǔ)上創(chuàng)建自己的類型，比如自定義的節(jié)點(diǎn)類。BGL的開發(fā)者是世界上最頂尖的C++專家，這個(gè)庫中實(shí)現(xiàn)的各種圖算法具有非常高的執(zhí)行效率，而且BGL本身具有工業(yè)強(qiáng)度，你可以放心的使用它。此外，BGL的代碼結(jié)構(gòu)良好，是非常值得研讀的精品，對于學(xué)習(xí)算法與數(shù)據(jù)結(jié)構(gòu)會(huì)有很大的幫助。

從我的角度來看，BGL的缺點(diǎn)是沒有提供復(fù)雜網(wǎng)絡(luò)分析的算法，所以在實(shí)際中我使用的還不多。建議對于分析大規(guī)模的網(wǎng)絡(luò)問題時(shí)使用這個(gè)庫，利用它良好的圖數(shù)據(jù)結(jié)構(gòu)，開發(fā)自己的復(fù)雜網(wǎng)絡(luò)分析算法，將會(huì)獲得很高的執(zhí)行效率。

參考資源：
BGL官方網(wǎng)站： http://www.boost.org/doc/libs/1_42_0/libs/graph/
技術(shù)書籍《The Boost Graph Library》，作者: Jeremy G. Siek，Lie-Quan Lee，Andrew Lumsdaine，見： http://www.douban.com/subject/1463103/
《使用Boost Graph library》，一個(gè)簡短的BGL使用介紹，適合快速上手，見： http://www.cppprog.com/2009/0408/100.html
《Boost Graph Library 學(xué)習(xí)筆記》，討論學(xué)習(xí)BGL中遇到的問題，見： http://blog.csdn.net/magicblue/archive/2009/05/22/4208976.aspx

二、QuickGraph —— .NET平臺(tái)下的BGL

QuickGraph是一個(gè)用C#語言編寫的.NET組件庫，所提供的算法與BGL類似，可以看作是Boost Graph Library在.NET平臺(tái)下的實(shí)現(xiàn)。目前QuickGraph的最高版本是3.3，支持.NET 2.0和.NET 3.5平臺(tái)。

對于復(fù)雜網(wǎng)絡(luò)研究，QuickGraph能夠提供的幫助與BGL基本類似。如果你對C#語言（以及其它支持.NET的語言）比較熟悉，可以考慮選擇這個(gè)庫。但由于.NET程序是在虛擬機(jī)下運(yùn)行的原因，所以效率不夠高，不適合處理大規(guī)模的計(jì)算問題。

參考資源：
QuickGraph官方網(wǎng)站： http://www.codeplex.com/quickgraph
中文資料暫時(shí)還找不到。

三、igraph —— C語言寫的復(fù)雜網(wǎng)絡(luò)分析庫

igraph是一個(gè)建立和操縱無向圖、有向圖的開源C程序庫，它既包含經(jīng)典圖論里的各種算法（例如最小支撐樹、網(wǎng)絡(luò)流等），也包含了最近的出現(xiàn)的一些網(wǎng)絡(luò)分析算法（如社團(tuán)結(jié)構(gòu)搜索等）。

igraph是C寫的，這意味著你很容易在C/C++中使用它。如果你不熟悉這兩種語言，或者覺得用C/C++太繁瑣的話，igraph還提供了R語言（一種國外很流行的統(tǒng)計(jì)分析語言）和Python語言的接口，所以也很適合科研人員使用（我現(xiàn)在用的是Python，調(diào)用igraph很簡單）。

參考資料：
igraph官方網(wǎng)站： http://igraph.sourceforge.net/
關(guān)于Python語言的介紹，見： http://zh.wikipedia.org/wiki/Python
關(guān)于R語言的介紹，見： http://zh.wikipedia.org/wiki/R語言

四、NetworkX —— 全面支持復(fù)雜網(wǎng)絡(luò)分析的Python包

NetworkX是一個(gè)創(chuàng)建和操縱復(fù)雜網(wǎng)絡(luò)，并對復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)、功能和動(dòng)力學(xué)進(jìn)行研究的Python包，它提供了目前應(yīng)用最廣泛的一些復(fù)雜網(wǎng)絡(luò)分析算法，當(dāng)然也包括基本的經(jīng)典圖論算法。NetworkX目前只能在Python語言中使用（這也是我學(xué)Python的原因之一，見《從C#到Python —— 談?wù)勎覍W(xué)習(xí)Python一周來的體會(huì)》）。

我個(gè)人認(rèn)為NetworkX比igraph要好用，因?yàn)镹etworkX的文檔更清晰易讀，程序結(jié)構(gòu)組織得也很好，我現(xiàn)在主要在用這個(gè)包。但NetworkX的執(zhí)行效率多數(shù)情況下會(huì)比igraph要低（見Drew Conway所作的對比： http://files.meetup.com/1406240/sna_in_R.pdf）。所以也不適合作太大規(guī)模的網(wǎng)絡(luò)分析計(jì)算。此外，NetworkX和Python的一個(gè)繪圖包——Matplotlib結(jié)合得很好，可很方便地進(jìn)行復(fù)雜網(wǎng)絡(luò)可視化。

參考資源：
NetworkX官方網(wǎng)站： http://networkx.lanl.gov/
Matplotlib（科學(xué)繪圖的Python包）： http://matplotlib.sourceforge.net

五、總結(jié)

本文介紹了圖論與復(fù)雜網(wǎng)絡(luò)研究常用的一些程序庫。用好這些程序庫（以及其它一些軟件工具），可以避免我們無謂的re-invent the wheel，從而提高工作效率。在網(wǎng)上了解到，國外同行用這些庫的很多，而在國內(nèi)還很少搜索到這方面的資料（除了BGL）。作為我進(jìn)復(fù)雜網(wǎng)絡(luò)圈的敲門磚，向各位圈友推薦這幾個(gè)庫。另外，我近期正在學(xué)習(xí)Python和NetworkX，如果您感興趣，歡迎和我交流：）

介紹幾個(gè)圖論和復(fù)雜網(wǎng)絡(luò)的程序庫 —— BGL，QuickGraph，igraph和NetworkX