Python igraph : Fastest way to convert large graph to python-igraph graph

Question

我有一个大型无向加权图，其中有约 375,000 个节点和约 3,400,000 个边，表示为邻接列表(字典的字典)。

例如

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

表示为

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

我想将此图转换为 python-igraph 图，然后运行 ​​walktrap 社区检测算法。我尝试过以下方法:

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]  

我在具有 150,000 个节点的子图上对此进行了测试，在配备 4GB RAM 和 i5-4200U CPU @ 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)