如何用networkx提取给定图的所有可能诱导子图

Question

我想知道能不能用networkx这个库来提取一个大图中所有可能的特定节点数的诱导子图（也叫图小块），或者有没有其他的工具可以做到这一点？比如说，如果我有一个大图，用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个节点的小图，算法应该返回给我：

子图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

对于那些和我一样遇到同样问题的人，尤其是节点太多的情况，这里有一些简单的改进建议，参考了@Hooked的回答（虽然@Hooked在评论中提到还有更好的解决方案，这里只是给那些和我有相同困扰的人提供一个快速的解决办法）

1) igraph的性能比networkx要好很多

2) 我们可以只关注一个节点的邻居，这样可以去掉大部分不必要的组合

举个例子，如果我们在更大的network中寻找一个motif（这两个都是igraph对象）

    motif_rank = max(max(motif.shortest_paths_dijkstra()))
    result = collections.OrderedDict.fromkeys(network.vs['label'], 0)

    for node in self.network.vs:
        # Get relevant nodes around node of interest that might create the motif of interest
        nodes_to_expand = {node}
        for rank in range(motif_rank):
            nodes_expanded = nodes_to_expand
            for node_to_expand in nodes_to_expand:
                nodes_expanded = set.union(nodes_expanded, set(node_to_expand.neighbors()))
            nodes_to_expand = nodes_expanded

        # Look at all combinations
        for sub_nodes in itertools.combinations(nodes_to_expand, motif.vcount()):
            subg = network.subgraph(sub_nodes)
            if subg.is_connected() and subg.isomorphic(motif):
                result[node['label']] = result[node['label']]+1

Answer 2

这段话的意思是，你想找出和某个target（目标图）匹配的所有子图，你需要先定义这个目标图。最简单的方法就是遍历所有节点的组合，找出那些相连的节点，然后检查它们是否是同构的。这里不太清楚你是想找网络模式（network motif）还是图形小块（graphlet）。在图形小块中，原始图中的所有边都必须存在，这样的话就会把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)]

你的例子在这里列出。