在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分钟.在这种情况下,问题是将图形保存到磁盘的过程占用了太多内存,我的笔记本电脑冻结了.除此之外我用networkx分析图表会非常慢,因为它纯粹的Python实现,所以我决定直接切换到igraph来解决这两个问题.

Answer 1

在这里查看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})

并且您可以使用它们实例化图形