複雜網路分析工具Python+igraph(二)

一、igraph中Graph類里實現的社區發現演算法：

1）community_leading_eigenvector(clusters=None, weights=None, arpack_options=None)

a)參數說明：

clusters：想要得到的社區數目，值為None時，將得到儘可能多的社區數目。需要注意的是當特徵向量的標記完全一致時，社區將不會再被分割，所以實際發現的社區數目可能會小於預期

weights：邊屬性的名字或一個包含邊權值的list，可為None

arpack_options：（先說一下，ARPACK為Fortran實現的隱式重啟動Arnodli演算法，一個計算給定矩陣的特徵值和特徵向量的演算法）一個用於調整ARPACK特徵向量計算的ARPACKOptions對象。默認時模塊級變數arpack_options會被調用

b)返回值：一個VertexClustering（一個圖的節點集聚類）或VertexDendrogram（從層次聚類中得到的一個圖的節點集樹圖結果）對象

c)應用的網路類型：從文獻[1]中描述得知該演算法僅應用於無向網路

2）community_fastgreedy(self, weights=None)

a)參數說明：

weights：邊屬性名或一個包含邊權值的list

b)返回值：VertexDendrogram對象

c)應用的網路類型：無向網路[2]

3）community_infomap(self, edge_weights=None, vertex_weights=None, trials=10)

a) 參數說明：

edge_weights：邊屬性的一個名字或一個包含邊權值的list

vertex_weights：節點屬性名或包含節點權值的list

trials：預期將網路分割的數目，默認值為10，並沒有對其進行詳細說明

b) 返回值：VertexClustering對象以及一個額外的屬性codelength，其中存儲著有演算法確定的code length

c) 應用的網路類型：該演算法是從對節點進行編碼的角度考慮的，忽視了連邊屬性，所以可用於有向和無向網路，參考文獻[3][4]是提出的infomap演算法以及它的改進，但是說實話英文看起來實在是太費事了，如果只是想了解一下的話，有一篇碩士畢業論文里對其做了簡要說明，可以看一下[5]

4）community_label_propagation(weights=None, initial=None, fixed=None)

a) 參數說明：

weights：一個變屬性的名字或包含邊權值的list

initial：節點屬性的名字或包含初始節點標籤的list。標籤為0到n-1，其中n為節點數。向量中的負數代表沒有標籤的節點

fixed：針對每個節點值為bool的list。True為在演算法中標籤不應改變的節點，只有初始化節點標籤這個參數才有意義。

b) 返回值：VertexClustering對象

c) 應用的網路類型：因為在標籤是根據連邊的方向來傳播的，所以該演算法僅應用於有向網路[6]

5）community_multilevel(self, weights=None, return_levels=False)

a) 參數說明：

weights：邊的屬性名或包含邊權值的list

return_levels：這是一個boolean類型。該演算法屬於層次聚類，會發現多層社區結構。當值為True時，演算法返回一個vertexclustering的list，包含每一層的社區結構。若為False，則返回模塊度最優的社團結構。

b) 返回值：VertexDendrogram

c) 應用的網路類型：僅應用於無向網路[7]

6）community_edge_betweenness(self, clusters=None, directed=True, weights=None)，速度明顯要慢一些

a) 參數說明：

clusters：期望得到的社區數目，這個實際定義的是我們截斷的樹圖的某一層從而得到節點的成員向量，如果值為None，則將截取樹圖中模塊度最大化的一級

directed：是否為有向圖，True or False

weights：同上

b) 返回值：VertexDendrogram，模塊度最優的截斷或希望得到的社區數目

c) 應用的網路類型：無向網路和有向網路

7）community_spinglass(weights=None, spins=25, parupdate=False, start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", gamma=1, implementation="orig", lambda_=1)，也是要慢一些

a) 參數說明：

weights：邊屬性名或包含邊權值的list

spins：發現社區數的上限

parupdate：是否同步更新節點的spin（對此演算法不是很了解，大概是在演算法中動態更新社區數目）

start_temp：初始溫度

stop_temp：停止溫度

cool_fact：模擬退火演算法的冷卻因素

update_rule：定義模擬的空模型，可為config(將節點度相同的隨機圖作為輸入)或simple(邊數相同的隨機圖)

gamma：implementation：lambda_：

註：說明一下，這個參數有點多，而且在運行時間上也相對較慢一些，所以在此不做詳細說明

8）community_walktrap(self, weights=None, steps=4)

a) 參數說明：同上

b) 返回值：同6)

c) 應用的網路類型：無向圖和有向圖

最後再說一下，上面所列出來的函數除非有特殊需求基本上是不用對它的默認參數進行修改的，所以用起來還是很方便的。

二、社區結果可視化

1）一般直接由plot(obj, target=None, bbox=(0, 0, 600, 600), *args, **kwds)來畫圖

a) 參數說明

obj：需要畫的對象，可以是Graph類，也可以是VertexClustering類等

target：需要指定畫成怎樣的格式，類型可以是None（系統會自己生成一個適合的surface用來畫）；cairo.Surface（可以是PNG圖片, 一個任意的窗口, 或者是SVG文件）；string（一個給定的文件名，可以將畫出的圖綁定在這個文件中，支持的文件格式有：PNG, PDF, SVG and PostScript）

bbox：兩個或四個整數元組或BoundingBox對象。當為兩個整數的元組時被認為是畫布的長和寬（對PNG格式來說是像素，對PDF, SVG 和 PostScript來說是點，72 pt = 1 inch = 2.54 cm）；當為四個點是被認為是一個頂點及它的對角頂點的坐標

layout：如果沒有layout實例，將會用Graph.layout來計算layout(說實話這個到底是什麼意思我也不太懂)。主要注意的是這個參數你必須給它賦值，要不然沒法畫圖

目前用到的就是這幾個參數，但是該函數還有很多其他的參數來設定預期的畫圖結果，在後面會再做詳細說明，下面來具體看一下各社區演算法發現結果

2）可視化對比

g = Graph.GRG(100,0.2)

圖1是用Graph類中生成隨機圖的函數GRG生成了具有100個節點的隨機網路，0.2為生成邊的概率。其中前三種社區發現函數返回的是VertexDendrogram對象，將其直接作為object的參數畫出來的是樹圖，如果想得到更直接的結果，可通過VertexDendrogram.as_clustering()將其轉換為VertexClustering對象來作為object的參數。

從上面的圖中可以看出infomap演算法和隨機遊走演算法的結果是基本一致的，其餘幾個社區發現演算法的所發現的社區數目基本在5個左右，但各個社區規模都有所不同。Fastergreedy演算法和multilevel演算法都是基於最優模塊度的，但所發現的社區結構甚至社區數目都是完全不同的，這與演算法的穩定性有關，即不同的節點輸入順序會導致不同的社區發現結果。邊介數演算法、標籤傳播演算法以及spinglass演算法的所發現的社區結構是大致相同的，標籤傳播演算法的結果更加細化一些，對於導致這些結果的原因並沒有細究。僅對於100個節點的網路來說，邊介數演算法和spinglass演算法的已經明顯的慢了一些，所以並不推薦用這兩個演算法進行大型網路的社區發現。需要註明的一點是由於原網路是隨機生成的，並沒有復現性，當時忘記用leading_eigenvector演算法進行社區發現，所以並沒有在本文中對其社區發現結果的分析。

2）VertexClustering的__plot__(self, context, bbox, palette, *args, **kwds)，以及VertexDendrogram的__plot__(self, context, bbox, palette, *args, **kwds)都可以畫圖，但是參數還是沒太搞懂。我覺得這並不是關鍵，畢竟通過第一種比較簡單的方法就可以得到我們想要的圖了，所以並不需要再將時間浪費在這些細節（該死的參數構造）上。如果有感興趣的，可以閱讀官方文檔的相關部分：igraph.drawing.plot函數的相關參數說明（http://igraph.org/python/doc/igraph.Graph-class.html#__plot__

http://igraph.org/python/doc/igraph.drawing-module.html#plot）

[1]Newman M E J. Finding community structure in networks using the eigenvectors of matrices.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2006, 74(3 Pt 2):036104.

[2]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 70(2):066111.

[3]Rosvall M, Bergstrom C T. Maps of Information Flow Reveal Community Structure In Complex Networks[J]. Proceedings of the National Academy of Sciences Usa, 2007:1118--1123.

[4]Rosvall M, Axelsson D, Bergstrom C T. The map equation[J]. The European Physical Journal Special Topics, 2009, 178(1):13-23.

[5]張善卓. 社會網路上的社區發現演算法研究[D]. 哈爾濱工業大學, 2014.

[6]Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007, 76(2):036106.

[7]Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of community hierarchies in large networks[J]. J Stat Mech, 2008, abs/0803.0476.

推薦閱讀：