K-th order neighbors in graph - Python networkx

Question

I have a directed graph in which I want to efficiently find a list of all K-th order neighbors of a node. K-th order neighbors are defined as all nodes which can be reached from the node in question in exactly K hops.

I looked at networkx and the only function relevant was neighbors. However, this just returns the order 1 neighbors. For higher order, we need to iterate to determine the full set. I believe there should be a more efficient way of accessing K-th order neighbors in networkx.

Is there a function which efficiently returns the K-th order neighbors, without incrementally building the set?

EDIT: In case there exist other graph libraries in Python which might be useful here, please do mention those.

Answer 1

I had a similar problem, except that I had a digraph, and I need to maintain the edge-attribute dictionary. This mutual-recursion solution keeps the edge-attribute dictionary if you need that.

def neighbors_n(G, root, n):
    E = nx.DiGraph()

    def n_tree(tree, n_remain):
        neighbors_dict = G[tree]

        for neighbor, relations in neighbors_dict.iteritems():
          E.add_edge(tree, neighbor, rel=relations['rel'])

        #you can use this map if you want to retain functional purity
        #map(lambda neigh_rel: E.add_edge(tree, neigh_rel[0], rel=neigh_rel[1]['rel']), neighbors_dict.iteritems() )

        neighbors = list(neighbors_dict.iterkeys())
        n_forest(neighbors, n_remain= (n_remain - 1))

    def n_forest(forest, n_remain):
        if n_remain <= 0:
            return
        else:
            map(lambda tree: n_tree(tree, n_remain=n_remain), forest)

    n_forest( [root] , n)

    return E

Answer 2

You can use: nx.single_source_shortest_path_length(G, node, cutoff=K)

where G is your graph object.

Answer 3

For NetworkX the best method is probably to build the set of neighbors at each k. You didn't post your code but it seems you probably already have done this:

import networkx as nx

def knbrs(G, start, k):
    nbrs = set([start])
    for l in range(k):
        nbrs = set((nbr for n in nbrs for nbr in G[n]))
    return nbrs

if __name__ == '__main__':
    G = nx.gnp_random_graph(50,0.1,directed=True)
    print(knbrs(G, 0, 3))

Answer 4

Yes,you can get a k-order ego_graph of a node subgraph = nx.ego_graph(G,node,radius=k) then neighbors are nodes of the subgraph neighbors= list(subgraph.nodes())