I'm new to networkx and actually a bit confused on how to efficiently find the n-degree neighborhood of a node. The n-degree neighborhood of a node v_i is the set of nodes exactly n hops away from v_i. Given a specified n, I need find the n-degree neighborhood for each node in the graph/network.
Suppose I have the following graph and I want to find the n=1 neighborhood of node v1. That would be v2 and v3. Next suppose I want to find the n=2 neighborhood of node v1, then that would be v4.
Find n hop neighbor using adj matrix
import networkx as nx
G = nx.Graph()
G.add_edges_from([('v1','v2'),('v2','v4'),('v1','v3')])
def n_neighbor(G, id, n_hop):
node = [id]
node_visited = set()
neighbors= []
while n_hop !=0:
neighbors= []
for node_id in node:
node_visited.add(node_id)
neighbors += [id for id in G.neighbors(node_id) if id not in node_visited]
node = neighbors
n_hop -=1
if len(node) == 0 :
return neighbors
return list(set(neighbors))
print(n_neighbor(G, 'v2', 1))
Function:
G: Networkx Graph
id : Root node Id to find neighbors
n_hop : hop length
return:
Neighbor list
Output:
print(n_neighbor(G, 'v2', 1))
['v1', 'v4']
nx.descendants_at_distance()
does the trick (although made for directed graphs):
G = nx.Graph()
G.add_edges_from([('v1', 'v2'), ('v2', 'v4'), ('v2', 'v4'), ('v1', 'v3')])
nx.descendants_at_distance(G, 'v1', distance=2) # returns {'v4'}
From the source code comment:
This is basically BFS, except that the queue only stores the nodes at `current_distance` from source at each iteration.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With