K-th order neighbors in graph - Python networkx

问题:

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.

回答1:

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

where G is your graph object.

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

回答3:

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.

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