Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding the n-degree neighborhood of a node

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.

enter image description here

like image 411
Jack Twain Avatar asked Mar 30 '14 10:03

Jack Twain


2 Answers

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']
like image 162
Abhi Avatar answered Oct 16 '22 22:10

Abhi


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.
like image 42
Michael Dorner Avatar answered Oct 16 '22 23:10

Michael Dorner