21

特定のノードを含むすべての接続されたノードのサブグラフを大きなグラフから抽出しようとしています。

Networkx ライブラリに解決策はありますか?

[編集]
私のグラフは DiGraph です

[編集]
簡単
に言い換えると、特定のノード N_i を含むグラフの一部と、入力エッジまたは出力エッジを使用して直接または間接的に (他のノードを通過して) 接続されているすべてのノードが必要です。
例：

>>> g = nx.DiGraph()
>>> g.add_path(['A','B','C',])
>>> g.add_path(['X','Y','Z',])
>>> g.edges()
[('A', 'B'), ('B', 'C'), ('Y', 'Z'), ('X', 'Y')]

私の望ましい結果は次のようになります。

>>> g2 = getSubGraph(g, 'B')
>>> g2.nodes()
['A', 'B', 'C']
>>> g2.edges()
[('A', 'B'), ('B', 'C')]
4

4 に答える 4

23

shortest_path() を使用して、特定のノードから到達可能なすべてのノードを見つけることができます。あなたの場合、最初にグラフを無向表現に変換して、インエッジとアウトエッジの両方に従う必要があります。

In [1]: import networkx as nx

In [2]: >>> g = nx.DiGraph()

In [3]: >>> g.add_path(['A','B','C',])

In [4]: >>> g.add_path(['X','Y','Z',])

In [5]: u = g.to_undirected()

In [6]: nodes = nx.shortest_path(u,'B').keys()

In [7]: nodes
Out[7]: ['A', 'C', 'B']

In [8]: s = g.subgraph(nodes)

In [9]: s.edges()
Out[9]: [('A', 'B'), ('B', 'C')]

または1行で

In [10]: s = g.subgraph(nx.shortest_path(g.to_undirected(),'B'))

In [11]: s.edges()
Out[11]: [('A', 'B'), ('B', 'C')]
于 2012-12-18T13:29:52.797 に答える
13

ターゲットノードがサブグラフ内に含まれるまで、サブグラフをループするだけです。

有向グラフの場合、サブグラフは、他のすべてのノードからすべてのノードにアクセスできるようなグラフであると想定しています。これは強く接続されたサブグラフであり、そのためのnetworkx関数はですstrongly_connected_component_subgraphs。

（MWE）最小限の作業例：

import networkx as nx
import pylab as plt

G = nx.erdos_renyi_graph(30,.05)
target_node = 13

pos=nx.graphviz_layout(G,prog="neato")

for h in nx.connected_component_subgraphs(G):
    if target_node in h:
        nx.draw(h,pos,node_color='red')
    else:
        nx.draw(h,pos,node_color='white')

plt.show()

ここに画像の説明を入力してください

有向サブグラフ（有向グラフ）の例では、対応する行を次のように変更します。

G = nx.erdos_renyi_graph(30,.05, directed=True)
...
for h in nx.strongly_connected_component_subgraphs(G):

ここに画像の説明を入力してください

ノードの1つは連結成分にありますが、強連結成分にはないことに注意してください。

于 2012-12-17T15:31:35.287 に答える
1

connected_component_subgraphsページの最後にある例を使用してください。

リストの最初の要素ではなく、最後の要素を参照するようにしてください

>>> G=nx.path_graph(4)
>>> G.add_edge(5,6)
>>> H=nx.connected_component_subgraphs(G)[-1]
于 2012-12-17T13:18:20.777 に答える