python - 如何使用 networkx 从给定图中提取所有可能的诱导子图

Question

我想知道是否可以使用 networkx 从输入的大图中提取子图中具有特定节点数的所有可能的诱导子图(graphlet)，或者是否有另一个包可以完成这项工作？例如，如果我有一个大图，它以 networkx 邻接表格式说明，

图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 个节点的 graphlet，算法应该返回我

子图1:

1 2 3
2 1
3 1

[(1,2),(1,3)] 子图2:

1 3 7
3 1
7 1

[(1,3),(1,7)] 子图 3:

3 4 5
4 3 5
5 3 4

[(3,4),(3,5),(4,5)]

子图 4、子图 5、子图 6...

以下是@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)]

Answer 1

这假设您需要您必须定义的给定 target 的所有匹配子图。 native 方法是遍历所有节点组合，找到那些连接的节点，然后检查同构。目前还不清楚你是想要一个网络主题还是一个小图。在 graphlet 中，原始图中存在的所有边都必须存在——这将从您的目标中排除 3-4-5。此方法查找 graphlets，要查找图案，您必须检查每个组合是否存在诱导子图(以及有多少!)。

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)]

此处列出了您的示例。