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

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

where G is your graph object.

Answer 2

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 3

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 4

You solve your problem using modified BFS algorithm. When you're storing node in queue, store it's level (distance from root) as well. When you finish processing the node (all neighbours visited - node marked as black) you can add it to list of nodes of its level. Here is example based on this simple implementation:

#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import defaultdict 
from collections import deque

kth_step = defaultdict(list)

class BFS:
    def __init__(self, node,edges, source):
        self.node = node
        self.edges = edges
        self.source = source
        self.color=['W' for i in range(0,node)] # W for White
        self.graph =color=[[False for i in range(0,node)] for j in range(0,node)]
        self.queue = deque()

        # Start BFS algorithm
        self.construct_graph()
        self.bfs_traversal()

    def construct_graph(self):
        for u,v in self.edges:
            self.graph[u][v], self.graph[v][u] = True, True

    def bfs_traversal(self):
        self.queue.append((self.source, 1))
        self.color[self.source] = 'B' # B for Black
        kth_step[0].append(self.source)

        while len(self.queue):
            u, level =  self.queue.popleft()
            if level > 5: # limit searching there
                return
            for v in range(0, self.node):
                if self.graph[u][v] == True and self.color[v]=='W':
                    self.color[v]='B'
                    kth_step[level].append(v)
                    self.queue.append((v, level+1))

'''
0 -- 1---7
|    |
|    |
2----3---5---6
|
|
4

'''


node = 8 # 8 nodes from 0 to 7
edges =[(0,1),(1,7),(0,2),(1,3),(2,3),(3,5),(5,6),(2,4)] # bi-directional edge
source = 0 # set fist node (0) as source

bfs = BFS(node, edges, source)


for key, value in kth_step.items():
    print key, value

Output:

$ python test.py
0 [0]
1 [1, 2]
2 [3, 7, 4]
3 [5]
4 [6]

I don't know networkx, neither I found ready to use algorithm in Graph Tool. I believe such a problem isn't common enough to have its own function. Also I think it would be overcomplicated, inefficient and redundant to store lists of k-th neighbours for any node in graph instance so such a function would probably have to iterate over nodes anyway.

Answer 5

As proposed previously, the following solution gives you all secondary neighbors (neighbors of neighbors) and lists all neighbors once (the solution is based on BFS):

{n: path for n, path in nx.single_source_shortest_path(G, 'a', cutoff=2).items() if len(path)==3}

Another solution which is slightly faster (6.68 µs ± 191 ns vs. 13.3 µs ± 32.1 ns, measured with timeit) includes that in undirected graphs the neighbor of a neighbor can be the source again:

def k_neighbors(G, source, cutoff):
    neighbors = {}
    neighbors[0] = {source}
    for k in range(1, cutoff+1):
        neighbors[k] = set()
        for node in level[k-1]:
            neighbors[k].update(set(G.neighbors(node)))
    return neighbors

k_neighbors(B, 'a', 2) #dict keyed with level until `cutoff`, in this case 2

Both solutions give you the source itself as 0th-order neighbor.

So it depends on your context which one to prefer.

Answer 6

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())