加载非常大的RDF三元组到iGraph中 ->快速顶点查找？

Question

我需要将DBPedia图的一个子集加载到iGraph中，以便计算一些图统计数据(例如节点中心性，…)。我使用Redlands libRDF python库加载DBPedia三元组。每个节点都与一个URI(唯一标识符)相关联。

我在将图表加载到iGraph时遇到了一些麻烦。我是这样做的:

1)读三行(主语，谓语，宾语)

2)使用以下算法获取或创建一个顶点(带属性)

def add_or_find_vertex (self, g, uri):
    try:
        return g.vs.find(name=uri)
    except (KeyError, ValueError):
        g.add_vertex(name=uri)
        return g.vs.find(name=uri)
subjVertex = self.add_or_find_vertex(self.g, subject)
objVertex = self.add_or_find_vertex(self.g, object)
self.g.add_edge(subjVertex, objVertex, uri=predicate)

问题是，我的脚本是非常慢的，我需要加载25M三元组。每个节点都是唯一的，但在三元文件中会出现几次。因此，我需要在创建边之前执行查找。你能告诉我"查找"方法是否使用索引进行查找(哈希表，…)?顶点查找的复杂度是多少?你会怎么做?

非常感谢

Answer 1

已经回答了。为了完整起见，我在这里也复制了我的答案:

顶点查找通常是O(|V|)，因为默认情况下顶点属性没有索引- 除了 name顶点属性，它是索引的。然而，g.vs.find只有在这样做时才会使用这个索引:g.vs.find(url)，而不是这样做:g.vs.find(name=url)。这是一个bug，因为索引可以在两种情况下使用。也可以从邮件列表中查看昨天的帖子。

但是，请注意，igraph的数据结构是针对静态图形进行优化的，因此g.add_vertex(我假设您也使用g.add_edge)也可能成为瓶颈。在内部，igraph使用一个有索引的边列表来存储图，并且每次改变图时都必须重新构建索引，因此在可能的情况下批量添加顶点和边要有效得多。

因为你似乎已经有一个迭代器，在(subject, predicate, object)的形式产生你的图的边，也许它更容易使用Graph.DictList来构建图形，因为它也照顾存储在name属性的顶点id，在有意义的批次添加边，并从你的三胞胎添加predicate属性:

>>> g = Graph.DictList(vertices=None, edges=({"source": subject,
...         "target": object, "predicate": predicate}
...         for subject, predicate, object in your_iterator))

Graph.DictList在我的机器上在1.63秒内处理100000个预先生成的随机三元组，所以我想这稍微改善了一些。