4

我需要将 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 三元组。每个节点都是唯一的，但在三重文件中多次找到。因此，我需要在创建边缘之前执行查找。您能告诉我“查找”方法是否使用索引进行查找（哈希表，...）？顶点查找的复杂性是多少？你会怎么做？

非常感谢

4

1 回答 1

4

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

顶点查找通常是 O(|V|)，因为默认情况下不索引顶点属性 -除了索引的name顶点属性。但是g.vs.find，仅当您这样做时才使用此索引：g.vs.find(url)而不是如果您这样做：g.vs.find(name=url)。这是一种错误，因为索引可以在这两种情况下使用。另请参阅邮件列表中昨天的主题。

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

由于您似乎已经有一个迭代器可以生成图形的边，因此一次构建图形(subject, predicate, object)可能更容易使用Graph.DictList，因为它还负责将顶点 ID 存储在name属性中，并在生成的位置批量添加边感觉，并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 个预先生成的随机三元组，所以我想这会稍微改善一些情况。

于 2014-05-12T12:06:37.090 回答