如何使用networkx计算"附近"节点

Question

我在这里寻找的可能是一个内置函数networkx,并有一个数学名称 - 如果是这样,我想知道它是什么!看起来谷歌很难实现.

给定一个图形G和一个起始节点i,我想找到所有节点"在P边缘内" 的子图i- 即那些i通过小于P边的路径连接的节点.

我的实施草案是:

import networkx as nx

N = 30
G = nx.Graph()

# populate the graph...
G.add_cycle(range(N))

# the starting node:
i = 15

# the 'distance' limit:
P = 4

neighborhood = [i]
new_neighbors = [i]
depth = 0

while depth < P:
    new_neighbors = list(set(sum([
        [k for k in G[j].keys() if k not in neighborhood]
    for j in new_neighbors], [])))

    neighborhood.extend(new_neighbors)

    depth += 1

Gneighbors = G.subgraph(neighborhood)

顺便说一句,这段代码是有效的,所以我不需要实现方面的帮助.我只想知道它是否有名称,以及它是否由networkx图书馆提供.

当您的代码崩溃并且您想要了解原因时,它非常有用 - 您只能在问题节点附近呈现图形的"位置/区域".

Answer 1

迟了两年,但我一直在寻找同样的东西,发现了一个内置的,我想会得到你想要的子图:ego_graph.功能签名和文档:

ego_graph(G, n, radius=1, center=True, undirected=False, distance=None)

返回在给定半径内以节点n为中心的邻居的诱导子图.

Answer 2

使用single_source_shortest_path或single_source_shortest_path_length使用截止值p

就像是:

nx.single_source_shortest_path_length(G ,source=i, cutoff=p)