搜索個別二分網絡

我在下面的形式，它構成了一個二分網絡數據。搜索個別二分網絡

A1 - B1 
A2 - B2 
A2 - B1 
A3 - B1 
A4 - B2 
A5 - B3 
A6 - B3 
A7 - B3 
A7 - B3 
A8 - B4 
A9 - B3

我想要做的是寫一些東西（理想情況下用python或C）或使用現有的庫來標識數據中的單個社區。例如

A1，A2，A3，A4是同一個社區的一部分，因爲它們連接到B1，B2類似的A5，A6，A7，A8，A9都連接到B3和B4。

我有點糊塗在閱讀大量有關網絡流量和圖表，以我的問題，坐在什麼地方的各種物品。這只是廣度優先搜索的一種形式，還是有更高效的方法來做到這一點？

感謝

來源

2010-01-09 David

@Eli有一個好主意，找到連接的部件。既然你知道了標籤（在這種情況下無論如何）開始與「A」，你可以做這樣的：

import networkx as nx 
edges = """A1 - B1 
A2 - B2 
A2 - B1 
A3 - B1 
A4 - B2 
A5 - B3 
A6 - B3 
A7 - B3 
A7 - B3 
A8 - B4 
A9 - B3""".split('\n') 
G = nx.parse_edgelist(edges,delimiter=' - ') 
for component in nx.connected_components(G): 
    print [n for n in component if n.startswith('A')]

來源

2012-11-24 00:02:11 Aric

如果你想使用Python，閱讀有關NetworkX庫。它有很多圖形模塊和算法實現。特別是，您可能會發現Bipartite模塊有用。我不確定「社區」是什麼意思，但該模塊的bipartite_color函數可能會對您有所幫助。

來源

2010-01-09 10:36:02

通過社區我的意思是，我的數據中，我將有幾個未連接的二分圖，我想要的方式建立與數據中每個未連接的二部圖關聯的所有A和B. – David 2010-01-09 11:43:27

@David：然後嘗試首先在數據上運行「連接組件」算法（NetworkX中也存在該算法）以查找連接的子圖。然後，您可以確定每個組件/子圖的雙份分段。 – 2010-01-09 14:11:36

也許是這樣的：

import collections 

data = (("A1", "B1"), ("A2", "B2"), ("A2", "B1")) 
out = collections.defaultdict(list) 

for value, key in data: 
    out[key].append(value) 

print out 
-> defaultdict(<type 'list'>, {'B1': ['A1', 'A2'], 'B2': ['A2']})

這隻能雖然單向的。你當然可以做2個字母，其中一個以A組爲鍵，另一個以B組爲鍵。它假定鍵是不可變的（字符串，數字）。

來源

2010-01-09 10:36:42 extraneon

我想如果我要沿着這條路走下去，那麼我將不得不使用像你所說的兩個字典，因爲B1是與B2相關的，因爲A2是兩者中的一個值。 – David 2010-01-09 11:40:49

使用Python和igraph library，可以執行以下操作：

import igraph 
graph = igraph.Graph.Formula("A1-B1, A2-B2, A2-B1, A3-B1, A4-B2, A5-B3, A6-B3, A7-B3, A8-B4, A9-B3") 
comms = graph.clusters() 
for comm in comms: 
    print ", ".join(graph.vs[comm]["name"])

甲簡短說明：Graph.Formula構造的圖表出類似上面的一個字符串表示的，但可以使用通過所提供的任何其他方法igraph來構建你的圖形。使用Graph.Formula的優點是它會自動創建包含頂點名稱的頂點屬性name。 graph.clusters()搜索網絡的連接組件並返回一個VertexClustering對象。此對象可用於for循環以遍歷組件。在for循環的核心中，comm變量將始終包含當前社區中節點的索引。我使用graph.vs[comm]選擇社區的頂點，請求它們的名稱作爲列表（graph.vs[comm]["name"]），然後通過逗號加入名稱。

來源

2010-01-22 00:28:18

不！請小心使用NetworkX庫，因爲它對於雙向圖沒有超過4個函數。一個用於驗證是否是二分，一個用於着色的節點，一個用於創建一個沒有砝碼的簡單二分網絡，另一個用於創建雙邊網絡您可以可使用最後一個功能的投影。

來源

2011-05-02 22:08:09 johann

搜索個別二分網絡

回答

相關問題