tehwalrus tehwalrus - 2 months ago 8
Python Question

how to compute 'nearby' nodes with networkx

What I'm looking for here may well be a built-in function in

networkx
, and have a mathematical name - if so, I'd like to know what it is! it is very difficult to Google for, it seems.

Given a graph
G
and a starting node
i
, I'd like to find the subgraph of all the nodes "within
P
edges" from
i
- that is, those that are connected to
i
by a path of less than
P
edges.

My draft implementation for this is:

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)


This code works, by the way, so I don't need help with the implementation. I would simply like to know if this has a name, and whether it is provided by the
networkx
library.

It is very useful when your code is crashing and you want to see why - you can render just the "locality/region" of the graph near the problem node.

YXD YXD
Answer

Use single_source_shortest_path or single_source_shortest_path_length with a cutoff of p

Something like:

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