1

我正在尝试使用 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 来解决这两个问题。

4

1 回答 1

5

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

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

于 2013-10-25T10:56:02.573 回答