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

Question

networkx 中有没有办法找到距离特定节点一定距离内的所有节点？就像我指定一个节点和一个距离并取回该距离内的所有节点。这是假设我为每条边添加了权重。

或者，有没有办法从特定节点找到指定度数内的所有节点？比如，与特定节点相距 2 度以内的所有节点是什么？度的意思是，一个节点连接到一个节点，一个节点连接到该节点。感谢您的帮助！

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)

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]

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

Find nodes within distance in networkx and python

python

networkx