|
二分圖又稱二部圖，是圖論中的一種特殊模型，它的頂點可分割為兩個互不相交的子集，并且圖中的每條邊所關(guān)聯(lián)的兩個頂點分別屬于這兩個不同的頂點集。二分圖在復雜網(wǎng)絡(luò)分析中有很多應用，例如科學家合作網(wǎng)絡(luò)（作者和論文）、商品網(wǎng)絡(luò)（商品和購買者）、城市公交網(wǎng)絡(luò)（線路和站點）等都可以用二分圖來進行描述。NetworkX提供了一些基本的二分圖建模與分析功能，下面對這些功能作一個簡單的介紹。 一、建立二分圖 建立二分圖與建立普通的圖方法比較類似，需要注意的是，邊只能在不同類節(jié)點之間添加，同類節(jié)點之間不要添加邊就可以。下面是一個簡單的例子（本例中用1開頭的編號表示項目節(jié)點，用2開頭的編號表示參與者節(jié)點）： import networkx as nx B = nx.Graph() #添加一個項目101，它有3個參與者：201,202,203 B.add_edge(101,201) B.add_edge(101,202) B.add_edge(101,203) #添加一個項目102，它有2個參與者：203,202,2034 B.add_edge(102,203) B.add_edge(102,204) ………………………… 此外， NetworkX還提供了多種二分圖演化模型的建立方法，在這里把它們列出來供大家參考： -- networkx.generators.classic.complete_bipartite_graph(n1, n2, create_using=None) 建立一個完全二分圖 -- networkx.generators.bipartite.bipartite_configuration_model (aseq, bseq, create_using=None, seed=None) 根據(jù)兩個度序列建立一個二分圖 -- networkx.generators.bipartite.bipartite_random_regular_graph(d, n, create_using=None, seed=None) 建立一個隨機的規(guī)則二分圖 -- networkx.generators.bipartite.bipartite_preferential_attachment_graph(aseq, p, create_using=None, seed=None) 建立一個優(yōu)先連接的二分圖 -- networkx.generators.bipartite.bipartite_havel_hakimi_graph(aseq, bseq, create_using=None) 根據(jù)兩個度序列建立一個Havel-Hakimi模式的二分圖（下面兩個模型類似，我沒有接觸過這個模型，不太理解具體含義） -- networkx.generators.bipartite.bipartite_reverse_havel_hakimi_graph(aseq, bseq, create_using=None) -- networkx.generators.bipartite.bipartite_alternating_havel_hakimi_graph(aseq, bseq, create_using=None) 二、檢測圖的二分性 用networkx.is_bipartite()方法可以檢測一個圖是否是二分圖。例如對上邊代碼建立的二分圖，nx.is_bipartite(B)返回的結(jié)果是True，而對一個隨機圖R = nx.random_graphs.gnp_random_graph(100,0.2)，由于它不是二分圖，nx.is_bipartite(R)返回的結(jié)果是False。 NetworkX并沒有提供圖的二分度計算方法，如果使用到這一功能需要自己編制代碼。何大韌老師等編寫的《復雜系統(tǒng)與復雜網(wǎng)絡(luò)》一書的132頁有二分度的計算公式，感興趣的朋友可以自己實現(xiàn)這一程序。 此外，NetworkX還提供了對二分圖節(jié)點進行著色的算法：networkx.bipartite_color()，它可以返回一個字典結(jié)構(gòu)，分別為二分圖中的兩類節(jié)點賦予一個顏色值以示區(qū)別。例如對前面建立的二分圖進行著色：print nx.bipartite_color(B)，將返回結(jié)果 ：{101: 1, 102: 1, 201: 0, 202: 0, 203: 0, 204: 0}，項目節(jié)點被賦予顏色值1，參與者節(jié)點的顏色值是0?？梢杂眠@個值來檢測節(jié)點類型，也可以用它來進行繪圖（參看第4篇筆記《網(wǎng)絡(luò)可視化》）。 三、二分圖的投影 二分圖可以通過向參與者節(jié)點投影或向項目節(jié)點投影轉(zhuǎn)換為一個單分圖（見下圖），NetworkX提供的networkx.project(B, nodes)方法可以完成這一工作。它接受兩個參數(shù)：一個是二分圖B，另一個是投向的節(jié)點集合nodes。  二分圖投影示意（向下投影）
對于節(jié)點集合的提取可以用networkx.bipartite_sets方法，它可以將一個二分圖的兩類節(jié)點提取為兩個集合(X,Y)，其中X是項目節(jié)點，Y是參與者節(jié)點。下面是一段示例代碼，演示上述兩個函數(shù)的用法：（接第一節(jié)的代碼之后） NSet = nx.bipartite_sets(B) #將二分圖中的兩類節(jié)點分別提取出來 Act = nx.project(B,NSet[0]) #向項目節(jié)點投影 Actor = nx.project(B,NSet[1]) #向參與者節(jié)點投影 print Act.edges() #輸出 [(101, 102)] print Actor.edges() #輸出 [(201, 202), (201, 203), (202, 203), (203, 204)] 四、通過派系提取構(gòu)造二分圖 對于一個存在派系（Clique）的圖，可以通過提取派系結(jié)構(gòu)生成一個二分圖。NetworkX提供的networkx.make_clique_bipartite方法可以從圖中查找派系，然后將一個派系作為一個項目節(jié)點并和該派系中的節(jié)點建立連接，從而構(gòu)造一個二分圖。它是二分圖向參與者節(jié)點投影的逆過程，下邊是一段示例代碼： （接第三節(jié)的代碼之后） G = nx.make_clique_bipartite(Actor) print G.edges() #輸出：[(201, -1), (202, -1), (203, -2), (203, -1), (204, -2)] 補充一點，NetworkX的派系提取算法據(jù)說效率很高，不過我沒有做過這方面的東西，感興趣的朋友可以去看它的源代碼（見http://networkx./reference/algorithms.clique.html）。 五、小結(jié) 本篇筆記介紹了用NetworkX進行二分圖建模與分析的方法，到今天為止，我的《NetworkX學習筆記》就暫告一段落了。我目前的工作中只用到了這幾篇筆記中所寫的功能，以后如果有其他的心得體會我還會繼續(xù)進行補充。希望這些文章對學習和研究復雜網(wǎng)絡(luò)的朋友們能起到一點幫助作用，也歡迎各位留言批評、討論。 最后，向NetworkX的三位開發(fā)者Aric Hagberg、Dan Schult 、Pieter Swart 以及許許多多的貢獻者致敬*，感謝他們?yōu)槲覀兲峁┝诉@樣一個優(yōu)秀的復雜網(wǎng)絡(luò)分析工具！ 根據(jù)三位開發(fā)者的建議，如果要在論文中引用NetworkX，請引用以下文獻: Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), G?el Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008 * 意外發(fā)現(xiàn)NetworkX的貢獻者里還有復雜網(wǎng)絡(luò)圈里的周濤、劉建國和汪秉宏老師，佩服??！見https://networkx./trac/changeset/681/networkx/trunk/networkx ：“Graph A and B are from Tao Zhou, Jian-Guo Liu, Bing-Hong Wang: Comment on ``Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality". http:///pdf/physics/0511084 ” |
|
|
