Python igraph：將大圖轉換爲python-igraph的最快方法

Question

我有一個大的無向加權圖，約375,000個節點，3,400,000個邊表示爲鄰接列表（字典詞典）。

例如作爲

{A : {B : 2, C : 4}, B : {A : 2}, C : {A : 4}} 

我想這個圖形轉換成的python-的igraph圖形，隨後運行walktrap社區檢測算法

A --> (B,2), (C,4) 
B --> (A,2) 
C --> (A,4) 

表示。我曾嘗試以下方法：

g = igraph.Graph() 

for node in mygrpah.keys(): 
    g.add_vertex(name=node) # each node is a string 

for node,neighbours in mygraph.iteritems(): 
    g.add_edges([(node,neighbour) for neighbour in neighbours.keys()]) 
    for neighbour in neighbours.keys(): 
     # to avoid adding edge while traversing neighbour's dictionary 
     del mygraph[neighbour][node] 

我15萬個節點測試這對一個子圖，它在我的電腦有4GB內存和CPU i5-4200U @ 1.60GHz的×4處理器就拿〜11個小時。

1. 有沒有更好的方法來執行轉換？
2. 是有速度更快，並提供walktrap社區檢測算法支持任何其他圖形庫？

Answer 1

問題是，您添加一個接一個的邊緣，由於基礎數據結構，這非常耗時。首先建立頂點列表和邊緣列表，然後通過一次調用將所有邊緣添加到add_edges(...)的速度要快得多。

mygraph = {"A" : {"B" : 2, "C" : 4}, "B" : {"A" : 2}, "C" : {"A" : 4}, "D":{}} 
g = igraph.Graph(directed=False) 
g.add_vertices(mygraph.keys()) 
edges = [(start, end) for start in mygraph.keys() for end in mygraph[start].keys()] 
# or if you only want to have undirected links only once: 
edges = [edge for edge in edges if edge[0] > edge[1]] 
g.add_edges(edges) 
igraph.plot(g)