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.

Zymotic

Answer 1

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

where G is your graph object.

Astral

This would be wasteful if it runs Dijkstra's algorithm on the whole graph. Is that what it does? – Escalate

@graffe It seems that by specifying cutoff=K, it does not run on the whole graph: it should only run on the Kth neighbors. (I tested by using a 10k-node path graph and timing the output for various K values.) – Valenevalenka

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

Nearly

Indeed. I am doing the same thing. In fact, to speed things up, I am creating and storing the i-th neighbors for i ranging from 1 all the way up to K. I was hoping I could find a short cut. Looks like there isn't one. Appreciate your response. – Zymotic

Where are you using l in your loop? – Blackman

Answer 3

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

Bowden

This is the simplest answer, and it seems like it might be the developer-intended way to do this. I assume the low vote count relative to the accepted answer is just because the other answer is nine years old, but is there any other reason why this wouldn't be the right choice? E.g. performance with large graphs, etc.? – Valenevalenka

Answer 4

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

Discomfortable

Answer 5

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.

Sadie

I appreciate your answer, although this is not what I am looking for. I already have a version which incrementally builds the K-th order neighbors set by growing the set of order 1 nbrs, then adding their nbrs, and so on till I reach order K neighbors. But this is beyond what networkx offers. – Zymotic

Answer 6

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.

Assam

Answer 7

It sounds like you're looking for nx.descendants_at_distance(G, source, distance).

>>> G = nx.DiGraph()
>>> G.add_edges_from([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)])
>>> nx.descendants_at_distance(G, 0, 2)
{3, 4, 5, 6}
>>> nx.descendants_at_distance(G, 5, 0)
{5}
>>> nx.descendants_at_distance(G, 5, 1)
set()

Selwin