1

私はPythonのオープンソースnetworkxパッケージからDiGraph.pyを継承するクラスを書いています。

私のクラスのいくつかのメソッドでは、特定の次数（有向グラフの場合はoutdegreesまたはindegrees）のノードを検索して返す必要があります。

このクラスは、データマイニングプロジェクト\自然言語処理で使用され、非常に大規模なネットワークで使用されます。私が必要としているのは、説明されているメソッドの高速実装です（特定のアウト度または特定のイン度を持つノードのリストを返します）。

スーパークラスにはすでにいくつかの定義があります。1。メソッドnetwork.outdegree()：ノードキーとoutdegree値を含むディクショナリを返します。

{'school': 4, 'middle school': 0, 'university': 0, 'commercial': 0, 'private': 5, 'institution': 2, 'high school': 0, 'college': 0, 'elementary school': 0, 'central': 0, 'company': 0, 'public': 3, 'bank': 2}
  1. である方法

network.out_degree_iter（）

<generator object out_degree_iter at 0x02EEB328>

この方法の使い方がわかりません。誰かがその使い方を説明してくれればありがたいです。

3.ネットワーク内のすべてのノードのリストである属性network.nodesがあります。

質問：たとえば、network.nodesでリスト内包を実行することにより、すべてのノードを反復処理してoutdegree 2のノードを返すことができます。または、辞書を反復処理して値2のノードのリストを返すか、またはout_degree_iter()これがどのように使用されているのか、またはforループ（dict.iteritems（）のfor k、v）で辞書アイテムを反復処理するのとどのように違うのかわかりません。ノードとエッジの非常に大規模なネットワークでは、これらのどれが高速でしょうか。なぜですか。

ありがとう

4

2 に答える 2

2

最も簡単な方法は、あなたが提案したリスト内包表記で out_degree_iter() メソッドを使用することです。方法は次のとおりです。

import networkx as nx
G=nx.DiGraph(nx.gnp_random_graph(1000,0.001))
t1=[n for n,k in G.out_degree_iter() if k==2

最速の方法は、内部データ構造にアクセスする必要があります。

t2=[n for n,nbrs in G.succ.items() if len(nbrs)==2]

学位については、in_degree_iter() および G.pred.items() を使用します。

ここにいくつかのタイミングがあります

In [41]: %timeit t1=[n for n,k in G.out_degree_iter() if k==2]
1000 loops, best of 3: 368 us per loop

In [42]: %timeit s2=[n for n,nbrs in G.succ.items() if len(nbrs)==2]
1000 loops, best of 3: 198 us per loop
于 2011-01-15T14:37:07.847 に答える
2

ディクショナリのコピーを作成しないため、イテレータは大きなグラフに適しています。このようなものはどうですか：

list_of_2 = []
for g in G.out_degree_iter():
    if g[1]==2:
        list_of_2.append(g[0])

または、

list_of_2 = map(lambda x:x[0],filter(lambda x:(x[1]==2),G.out_degree_iter()))
于 2011-01-14T20:44:05.803 に答える