9

入力された大きなグラフからサブグラフ内の特定の数のノードを持つすべての可能な誘導サブグラフ (グラフレット) を抽出するために networkx を使用できるかどうか、またはジョブを実行できる別のパッケージがあるかどうか疑問に思っていますか? たとえば、ネットワークx隣接リスト形式で示されている大きなグラフがある場合、

グラフ G:

1 2 3 7
2 1 4
3 1 4 6 5
4 2 3 5
5 3 4 6
6 3 5 7
7 1 6

次のようになります

ここに画像の説明を入力

3 つのノードでグラフレットを抽出したい場合、アルゴリズムは私を返す必要があります

サブグラフ1:

1 2 3
2 1
3 1

[(1,2),(1,3)] ここに画像の説明を入力 subgraph2:

1 3 7
3 1
7 1

[(1,3),(1,7)] ここに画像の説明を入力 subgraph3:

3 4 5
4 3 5
5 3 4

[(3,4),(3,5),(4,5)] ここに画像の説明を入力

subgraph4,subgraph5,subgraph6...

以下は、@Hooked が提案した質問のコードです。n=3 としましょう

import itertools
target = nx.complete_graph(3)
for sub_nodes in itertools.combinations(g.nodes(),len(target.nodes())):
    subg = g.subgraph(sub_nodes)
    if nx.is_connected(subg):
        print subg.edges()

出力は次のようになります

[(1, 2), (1, 3)]
[(1, 2), (2, 4)]
[(1, 2), (1, 7)]
[(1, 3), (3, 4)]
[(1, 3), (3, 5)]
[(1, 3), (3, 6)]
[(1, 3), (1, 7)]
[(1, 7), (6, 7)]
[(2, 4), (3, 4)]
[(2, 4), (4, 5)]
[(3, 4), (3, 5), (4, 5)]
[(3, 4), (3, 6)]
[(3, 5), (3, 6), (5, 6)]
[(3, 6), (6, 7)]
[(4, 5), (5, 6)]
[(5, 6), (6, 7)]
4

2 に答える 2

13

これは、定義する必要がある特定の一致するすべてのサブグラフが必要であると想定してtargetいます。ネイティブな方法は、ノードのすべての組み合わせをループし、接続されているものを見つけて、同型性をチェックすることです。ネットワーク モチーフまたはグラフレットのどちらが必要かは不明です。グラフレットでは、元のグラフに存在するすべてのエッジが存在する必要があります。これにより、ターゲットから 3-4-5 が除外されます。このメソッドは、グラフレットを見つけて、誘導されたサブグラフ (およびその数!) があるかどうか、各組み合わせについてチェックする必要があるモチーフを見つけます。

import networkx as nx

g = nx.Graph()
g.add_edge(1,2);g.add_edge(1,3)
g.add_edge(1,7);g.add_edge(2,4)
g.add_edge(3,4);g.add_edge(3,5)
g.add_edge(3,6);g.add_edge(4,5)
g.add_edge(5,6);g.add_edge(6,7)

import itertools

target = nx.Graph()
target.add_edge(1,2)
target.add_edge(2,3)

for sub_nodes in itertools.combinations(g.nodes(),len(target.nodes())):
    subg = g.subgraph(sub_nodes)
    if nx.is_connected(subg) and nx.is_isomorphic(subg, target):
        print subg.edges()

私にとっては、これにより次のエッジセットの一致が得られます。

[(1, 2), (1, 3)]
[(1, 2), (2, 4)]
[(1, 2), (1, 7)]
[(1, 3), (3, 4)]
[(1, 3), (3, 5)]
[(1, 3), (3, 6)]
[(1, 3), (1, 7)]
[(1, 7), (6, 7)]
[(2, 4), (3, 4)]
[(2, 4), (4, 5)]
[(3, 4), (3, 6)]
[(3, 6), (6, 7)]
[(4, 5), (5, 6)]
[(5, 6), (6, 7)]

あなたの例はここにリストされています。

于 2014-03-04T19:20:08.577 に答える