Find nodes within distance in networkx and python

user_13908802 0
Viewed 1415

Is there a way in networkx to find all the nodes within some distance from a particular node? As in, I specify a node and a distance and get back all nodes within that distance. This is assuming that I added a weight to every edge.

Alternatively, is there a way to find all nodes within a specified degrees from a particular node? Like, what are all the nodes within 2 degrees of separation from a particular node? Degrees meaning, a node is connected to a node is connected to the node. Thank you for your help!

networkx python
2 Answers

You can use the ego_graph function of networkx library:

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

For example:

import networkx as nx

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

Original graph Graph centered in 0

user_52961060

This will provide a pseudo adjacency matrix, which represents adjacency within your provided radius (in degrees, not distance), not just directly linked nodes .

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

This should be significantly faster than the networkx solution in certain cases, depending on the ratio of edges to nodes, and how many nodes you want to solve for.

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]
user_54286680
Related