获取两个节点之间节点的子图？

Question

我有这张图表：

%matplotlib inline 
import networkx as nx

G = nx.Graph()

G.add_edge(1, 2)
G.add_edge(2, 3)
G.add_edge(3, 4)
G.add_edge(3, 5)
G.add_edge(4, 6)
G.add_edge(5, 6)
G.add_edge(3, 7)
G.add_edge(7, 6)
G.add_edge(6, 8)
G.add_edge(8, 9)

nx.draw(G, pos=nx.spring_layout(G), with_labels=True)

如果不使用nx.subgraph(G, [3,4,5,6,7])，是否有可能获得节点3和6之间的子图。我的意思是，如果我知道有这个子图，但是我不知道例如5的存在怎么办？

- user1602492

---

如果我通过 G.add_edges_from([(3,10),(10,11),(11,6)]) 向你的图添加了三条边（这将创建一条从 3 到 6 的新路径，但是它会穿过节点 10 和 11，所以比其他路径更长） - 你想让 10 和 11 在你的子图中吗？ - Joel

我已经编辑了您的标题以更好地匹配您的问题。请仔细检查它。此外，您可以使用G.add_edges_from([(1, 2), (2, 3), (3, 4), (3, 5), (4, 6), (5, 6), (3, 7), (7, 6), (6, 8), (8, 9)])更紧凑地生成您的图形，因此您可能需要编辑您的问题以显示它。 - Joel

但是这行代码不符合 PEP8 标准。 :-) - user1602492

删除我的答案...它不起作用。但是我有一个新的想法，不需要花费几个小时。 - Corley Brigman

Answer 1

我的答案与back2basics非常相似，但更直接地找到两者之间的节点。如果从source到target存在路径，则可以通过nx.all_simple_paths(G, source=source, target=target)找到该路径，它返回路径的生成器。

import networkx as nx

G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (3, 5), (4, 6), (5, 6), (3, 7), (7, 6), (6, 8), (8, 9)])

paths_between_generator = nx.all_simple_paths(G,source=3,target=6)
nodes_between_set = {node for path in paths_between_generator for node in path}
SG = G.subgraph(nodes_between_set)

nodes_between_set = ...使用了一个“生成器集合”。它相当于：

nodes_between_set = set()
for path in paths_beween_generator:
    for node in path:
        nodes_between_set.add(node)

- Joel

Answer 2

前三行代码帮助生成了你需要创建子集的列表。

import networkx as nx

c_score = nx.algorithms.betweenness_centrality_subset(G,(3,), (6,))
nodes_between = [x for x in c_score if c_score[x]!=0.0]
nodes_between.extend((3,6))  #add on the ends
SG = G.subgraph(nodes_between)

nx.draw(SG, pos=nx.spring_layout(SG), with_labels=True)

一个注意点：子图的点被定义为从点3到点6的路径上的点。

- Back2Basics

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Joel

我已经仔细检查过了，betweenness_centrality_subset 对于10和11给出的值是0... - user1602492

在这个数据集上我可能没有注意到。谢谢。 - Back2Basics

Answer 3

这个原理是基于以下两点：

1. 新子图中的任何节点都可以从源或目标到达，
2. 路径上的任何节点在定义上至少有一个前驱和一个后继（对于有向图）或两个邻居（对于无向图）。

因此，首先我们找到可以到达的节点的子图，然后递归地删除没有至少一个前驱和一个后继的节点，直到只剩下现有的子图。

import networkx as nx
def subgraph_from_connections(G, source, target, directed = None):
    included_nodes = [x for x in G.node if nx.has_path(G, source, x) and nx.has_path(G, x, target)]
    G2 = G.subgraph(included_nodes)
    # If this is a undirected graph, we only need to know if it only has 1 neighbor
    # If this is a directed graph, then it needs at least 1 predecessor and at least 1 successor
    if directed == True or (directed is None and type(G) == nx.classes.digraph.DiGraph):
        removals = [x for x in G2.node if len(G2.predecessors(x)) == 0 or len(G2.successors(x)) == 0]
        while len(removals) > 0:
            G2.remove_nodes_from(removals)
            removals = [x for x in G.node if len(G2.predecessors(x)) == 0 or len(G2.successors(x)) == 0]
    else:
        removals = [x for x in G2.node if len(G2.neighbors(x)) < 2]
        while len(removals) > 0:
            G2.remove_nodes_from(removals)
            removals = [x for x in G2.node if len(G2.neighbors(x)) < 2]
    return G2

虽然没有经过广泛测试，但对于这里概述的少数情况它是有效的，并且包括从Joel的测试中包含的10/11。该算法足够快-之前我进行的1000/10节点随机测试只用了130毫秒（也许我不应该删除它）。

- Corley Brigman