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

Question

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

10

我想知道是否可以使用networkx从一个输入的大型图中提取出特定节点数的引出子图（graphlets），或者是否有其他软件包可以完成这个任务？例如，如果我有一个用networkx邻接表格式表示的大型图，

图G：

它将会看起来像这样：

enter image description here

如果我想要提取包含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)]

- TinyEpic

@hivert Graphlets对我来说也是一个新术语。维基百科称它们为“大型网络的小型连接非同构诱导子图。” - Hooked

@Hooked: 三角形3、4、5 是相连的。 - hivert

@hivert...“可能诱导子图（图形子结构）”... - Hooked

@hivert 我认为OP打算询问网络“模体”，不过... - Hooked

@tohnperfect 您的问题很好，欢迎来到 Stack Overflow！我已经尝试回答您的问题，但是正如讨论所显示的那样，有一些部分不太清晰。一旦您获得足够的声望，您将能够自己发布图像 - 请务必为好的答案/问题投票并在答案完整时接受一个答案。 - Hooked

显示剩余6条评论

2个回答

2

对于遇到相同问题但节点过多的人，以下是对@Hooked答案的一些简单改进（虽然我相信像@Hooked在评论中提到的那样，还有更好的解决方案，但这只是一个快速复制粘贴修复的方法，适用于遇到与我相同原因且存在扩展问题的人）：

1）igraph比networkx更适合扩展

2）我们只能取一个节点的邻域来消除大部分不必要的组合

例如，如果我们正在寻找较大网络（两个igraph对象）中的一个motif：

    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

- ozgeneral

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hooked · Accepted Answer

假设您想要给定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)]

这里列出了您的示例。