获取两个节点之间的节点子图?
Getting subgraph of nodes between two nodes?
我有这张图:
%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?
前 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 的路径中
我的回答和back2basics很像,但是更直接的找到了两者之间的节点。如果存在从 source
到 target
的路径,则该路径将由 nx.all_simple_paths(G, source=source, target=target)
找到,其中 returns 是路径的生成器。
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)
这是基于
的原则
- 新子图中的任何节点都可以从源或目标到达,并且
- 根据定义,路径上的任何节点至少有一个前驱和一个后继(对于有向图)或两个邻居(对于无向图)。
所以,首先我们找到我们能到达的节点的子图,然后递归地删除没有至少一个前驱和一个后继的节点,直到只剩下现有的子图。
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,当这些情况包含在 Joel 的测试中时。该算法足够快——我之前的 1000/10 节点随机测试为 130 毫秒(也许我根本不应该删除它)。
我有这张图:
%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?
前 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 的路径中
我的回答和back2basics很像,但是更直接的找到了两者之间的节点。如果存在从 source
到 target
的路径,则该路径将由 nx.all_simple_paths(G, source=source, target=target)
找到,其中 returns 是路径的生成器。
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)
这是基于
的原则- 新子图中的任何节点都可以从源或目标到达,并且
- 根据定义,路径上的任何节点至少有一个前驱和一个后继(对于有向图)或两个邻居(对于无向图)。
所以,首先我们找到我们能到达的节点的子图,然后递归地删除没有至少一个前驱和一个后继的节点,直到只剩下现有的子图。
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,当这些情况包含在 Joel 的测试中时。该算法足够快——我之前的 1000/10 节点随机测试为 130 毫秒(也许我根本不应该删除它)。