如何使用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,算法应该返回给我

subgraph1:

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

Answer 1

这假设您需要所有匹配的子图target,您必须定义它们.本机方式是遍历节点的所有组合,找到那些连接的节点,然后检查同构.目前还不清楚你是否需要网络主题或图形.在图表中,原始图表中存在的所有边都必须存在 - 这将从目标中排除3-4-5.这个方法找到graphlet,如果有一个诱导子图(以及有多少!),找到你必须检查每个组合的图案.

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

您的示例在此处列出.