python - 在 Python 中使用 igraph 创建网络的性能瓶颈

Question

我正在尝试使用 igraph python 模块创建一个巨大的网络。我正在通过以下格式的字典列表进行迭代:

d1={'el1':2, 'el3':4, ...,'el12':32}
d2={'el3':5, 'el4':6, ...,'el12':21}

网络是按以下方式创建的:每个节点都是字典的键之一，具有表示节点所有值总和的属性(例如，考虑到这两个值，el3 的值为 9给定字典)，如果两个节点一起出现在同一个字典中，则它们之间有一条边，其权重属性等于它们一起出现的次数(例如，对于 el3 和 el12，它们一起出现时为 2在 2 部词典中)。

我正在使用以下循环来创建网络，其中“item”是前面描述的字典。明确地说，我有大约 12.000 个元素要分析

g = ig.Graph()


for el in news_db:
    item = dict(news_db.get(el))['commenters']
    print count 
    count = count + 1
    for user in item:


        try:
            g.vs.find(user)['comment'] = g.vs.find(user)['comment'] + 1
        except:
            g.add_vertex(user)
            g.vs.find(user)['comment'] = 1

    for source, target in itertools.combinations(item.keys(), 2):
        source_id = g.vs.find(source).index
        target_id = g.vs.find(target).index
        if g.are_connected(source_id,target_id):
            edge_id = g.get_eid(source_id,target_id)
            g.es[edge_id]['weight'] = g.es[edge_id]['weight'] + 1 
        else:
            g.add_edge(source_id,target_id,weight=1)

问题是这个程序的速度真的很慢。循环遍历前 25 个元素大约需要 23 秒，并且循环执行时间随着时间的推移而变得更糟。我使用了分析工具，发现 97% 的时间花在了“add_edge”函数上。我在最好地使用 igraph 吗？是否有可能降低这个执行时间？

需要说明的是，我还有一个替代的 networkx 版本，创建图表大约需要 3 分钟。在那种情况下，问题是将图形保存到磁盘的过程占用了太多内存，我的笔记本电脑死机了。此外，考虑到纯 Python 实现，我认为使用 networkx 分析图会非常慢，所以我决定直接切换到 igraph 来解决这两个问题。

Answer 1

Look here由于 add_edge 如此缓慢的原因。

而且，看起来你做事很没效率。最好在实例化图形之前收集所有必要的数据，而不是执行这么多更新。有一个用于这些目的的 collections.Counter 类:

import collections
import itertools

news_db = [{'el1':2, 'el3':4, 'el12':32},
           {'el3':5, 'el4':6, 'el12':21}]

vertices = collections.Counter()
edges = collections.Counter()

for item in news_db:
    vertices.update(**item)
    edges.update(itertools.combinations(item.keys(), 2))

print vertices 
print edges

输出所需的顶点和边集

Counter({'el12': 53, 'el3': 9, 'el4': 6, 'el1': 2})
Counter({('el3', 'el12'): 2, ('el3', 'el4'): 1, ('el3', 'el1'): 1, ('el1', 'el12'): 1, ('el12', 'el4'): 1})

你可以使用它们实例化图表