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.

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

回答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)    

回答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.