Finding the n-degree neighborhood of a node

Question

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.

Answer 1

import networkx as nx
G = nx.Graph()
G.add_edges_from([('v1','v2'),('v2','v4'),('v1','v3')])

def neighborhood(G, node, n):
    path_lengths = nx.single_source_dijkstra_path_length(G, node)
    return [node for node, length in path_lengths.iteritems()
                    if length == n]

print(neighborhood(G, 'v1', 1))
# ['v2', 'v3']
print(neighborhood(G, 'v1', 2))
# ['v4']

Answer 2

The most efficient way to find the n-neighbors of a given node is to use Depth first search: http://en.wikipedia.org/wiki/Depth-first_search. The function below returns the neighbors of start for all distances. However, if you need to find the n-neighbors for all nodes, using this function for all nodes would not be the most efficient solution. Instead, one could use this function just for a start-node in each connected component, and compute the n-neighbors for the other nodes relative to the starts, but that would be quite more complicated.

import networkx as nx

def n_neighbor(G, start):

    #  {distance : [list of nodes at that distance]}
    distance_nodes = {}

    # nodes at distance 1 from the currently visited ones
    next_shell = G.neighbors(start)

    # set of all visited nodes
    visited=set()
    visited.add(start)

    # how fare we are from start
    distance = 0

    # until we run out of nodes
    while len(next_shell) > 0:

        # this will be the next shell
        shell_after_this = []

        # update distance
        distance += 1
        distance_nodes[distance] = []

        # update visited and distance_nodes
        for node in next_shell:
            visited.add(node)
            distance_nodes[distance].append(node)


        # compute shell_after_this
        for node in next_shell:
            # add neighbors to shell_after_this
            # if they have not been visited already
            for neighbor in G.neighbors(node):
                if neighbor not in visited:
                    shell_after_this.append(neighbor)

        # we repeat with the new_shell
        next_shell = set(shell_after_this)

    return distance_nodes


# example 
G=nx.Graph()

G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,3)
G.add_edge(2,4)
G.add_edge(3,5)
G.add_edge(5,17)
G.add_edge(2,6)

print n_neighbor(G, 1)    

Answer 3

When you perform a Breadth First Search on a graph, starting at a root node r - the nodes are considered in increasing distance from r.

Thus, you just need to track the level of the nodes as you perform a BFS, see http://en.wikipedia.org/wiki/Level_structure for a more thorough discussion.

Answer 4

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.

Answer 5

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']