將非常大的RDF三元組加載到iGraph中 - >快速頂點查找？

我需要將DBPedia圖的一個子集加載到iGraph中，以便計算一些圖統計信息（例如節點中心性...）。我使用Redlands libRDF python庫加載DBPedia三元組。每個節點都與一個URI（唯一標識符）關聯。將非常大的RDF三元組加載到iGraph中 - >快速頂點查找？

我有一些麻煩加載圖形到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三元組。每個節點都是唯一的，但在三重文件中多次找到。因此我需要在創建邊緣之前執行查找。你能告訴我，如果「find」方法使用索引進行查找（Hashtable，...）嗎？頂點查找的複雜性是什麼？你會怎麼做？

非常感謝您

來源

2014-05-11 Kevin.

加載列表中的所有邊並通過一次調用創建圖。 –

非常感謝@GaborCsardi。事實上，瓶頸是'add_edge（）'調用，我一次一個地調用每個關係。相反，我們在Python列表中創建了一個邊列表，並在末尾用'add_edges（list）'刷新了列表。現在，它超快！ –

已經回答here。爲了完整起見，我在這裏複製我的答案，以及：

頂點查找通常是O（| V |），因爲頂點屬性默認情況下，沒有索引 - 除了的name頂點屬性，它是索引。但是，g.vs.find僅在您使用此索引時才使用此索引：g.vs.find(url)但如果您這樣做：g.vs.find(name=url)。這是一種錯誤，因爲索引可以在兩種情況下使用。另請參閱郵件列表中的yesterday's thread。

但是，請注意，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秒我的機器上十萬預先生成的隨機三胞胎，所以我想改善的東西一點點。

來源

2014-05-12 12:06:37

太棒了，我更瞭解iGraph數據結構現在如何工作。也許，在文檔中添加註釋以讓潛在用戶知道這些操作的複雜性是值得的。 –

將非常大的RDF三元組加載到iGraph中 - >快速頂點查找？

回答

相關問題