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

我有这个图：获取两个节点之间的节点的子图？

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

是否有可能得到的节点3和6之间的子图，而无需使用nx.subgraph(G, [3,4,5,6,7])。我的意思是，如果我知道有这个子图，但我不知道关于5？

来源

2015-09-11 marcus

如果我用'G.add_edges_from（[（3,10），（10,11），（11,6）]）'添加3条边到图中（它创建了一条从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标准。 :-) – marcus

我的回答是非常相似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 = ...使用“set generator”。它相当于

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

来源

2015-09-11 21:57:28 Joel

前3行帮助制作出您需要制作子集的列表。

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点

来源

2015-09-11 20:19:41 Back2Basics

我认为'betweenness_centrality_subset'只会在两个节点之间的最短路径上给出非零条目。如果将3-10,10-11,11-6边添加到给定的'G'中，则10和11都不会在'SG'中。 – Joel

我有双重检查这和'betweenness_centrality_subset'给10为10和11 ... – marcus

不会注意到这个数据集。 TY。 – Back2Basics

这个工作的原则是

在新的子图的任何节点是从源或目标可达，并
定义路径上的任何节点至少有一个前导和一个后继（对于有向图）或两个邻居（对于无向图）。

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

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

没有广泛的测试，但它的工作对这里列出的少数情况下，它包括那些从乔尔的测试包括10/11。该算法足够快 - 从我之前的1000/10节点随机测试算起130毫秒（也许我不应该删除它）。

来源

2015-09-17 13:18:00

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

回答

相关问题