Python igraph：将大图转换为 python-igraph 图的最快方法

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 个小时。

是否有更好的转换方法？
有没有其他更快并支持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)

Python igraph：将大图转换为 python-igraph 图的最快方法

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

python

algorithm

graph

igraph