在networkx和Python中查找距离内的节点。

Question

有没有一种方法可以在networkx中找到距离特定节点一定距离内的所有节点？也就是说，我指定一个节点和一个距离，然后得到所有在该距离内的节点。假设我为每条边添加了权重。

或者说，有没有一种方法可以找到距离特定节点指定度数以内的所有节点？比如，从一个特定节点开始，它与另外一个节点相连，那个节点再与另外一个节点相连，以此类推，找出所有与该节点相隔两个连接关系的节点。谢谢您的帮助！

- AP_Vehn

Answer 1

您可以使用 `networkx` 库中的 `ego_graph` 函数：

node = 3 # The center node
radius = 3 # Degrees of separation
new_graph = nx.generators.ego_graph(graph, node, radius=radius)

例如：

import networkx as nx

G = nx.gnm_random_graph(n=n, m=30, seed=1)
G = nx.generators.ego_graph(G, 0, radius=2)

- Riccardo Bucco

Answer 2

这将提供一个伪邻接矩阵，表示在你提供的半径范围内（以度为单位，而非距离），不仅包括直接连接的节点。

def neighbors_in_radius(G, radius):
    adj = np.array(nx.linalg.graphmatrix.adjacency_matrix(G).todense()).astype(float)  # much faster as float
    power_adj = connected = adj
    for i in range(radius - 1):
        power_adj = power_adj.dot(adj)
        connected = connected + power_adj
    connected = connected.astype(bool).astype(int)
    return connected

这个方法在某些情况下应该比networkx的解决方案快得多，具体取决于边与节点的比例以及您要解决的节点数量。

G = nx.gnm_random_graph(n=1000, m=10000, seed=1)
%time v1 = neighbors_in_radius(G, radius=2)  # 98 ms 
%time np.where(v1[n]) # 29 microsec  # to get results for specific node

%time v2 = [nx.generators.ego_graph(G, n, radius=2).nodes for n in G.nodes] # 21 sec

# confirm solutions equivalent
assert v1.sum(axis=1).tolist() == [len(x) for x in v2]

- J. Doe