如何使用NetworkX计算“附近”的节点

Question

我寻找的可能是networkx中的内置函数，并且具有数学名称-如果是这样，我想知道它是什么！但很难在Google上搜索到。

给定一个图G和一个起始节点i，我想找到所有节点“在P条边内”的子图，从i通过少于P条边的路径连接到i的那些节点。

我对此的初步实现如下：

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 库提供。

当你的代码崩溃并且你想查看原因时，这个算法非常有用-你可以仅渲染靠近问题节点的“局部/区域”图形。

- tehwalrus

Answer 1

虽然晚了两年，但我也在寻找同样的东西，并发现一个内置选项，我认为可以得到你想要的子图：ego_graph。函数签名和文档：

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

返回以给定半径为中心节点n的邻居所形成的诱导子图。

- valrus

---

非常有用的东西！+1 - FaCoffee

Answer 2

使用 single_source_shortest_path 或 single_source_shortest_path_length，并设置截止长度为p。

类似这样：

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

- YXD

---

谢谢，实际上看起来nx.single_source_shortest_path_length会更好，因为它返回的数据较少（我认为它也做了较少的工作）。但是没错，这是编写/维护最少的代码，谢谢！ - tehwalrus