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 のトリプルをロードする必要があることです。各ノードは一意ですが、トリプル ファイル内で何度か見つかります。したがって、エッジを作成する前にルックアップを実行する必要があります。「find」メソッドが検索用のインデックス (Hashtable など) を使用しているかどうか教えていただけますか? 頂点ルックアップの複雑さは? あなたならどうしますか？

どうもありがとうございました

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 はインデックス付きのエッジ リストを使用してグラフを保存し、グラフを変更するたびにインデックスを再構築する必要があるため、可能であれば頂点とエッジの追加をバッチで行う方がはるかに効率的です。

グラフのエッジを形式で生成するイテレータが既にあるように見えるので、頂点 ID を属性に格納し、バッチでエッジを追加することも処理するため、一度にグラフを作成する(subject, predicate, object)方が簡単かもしれません。センス、そしてトリプレットからの属性も追加します：Graph.DictListnamepredicate

>>> 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 に答える