python - 图中的 K 阶邻居 - Python networkx

Question

我有一个有向图，我想在其中有效地找到一个节点的所有 K 阶邻居的列表。K 阶邻居被定义为可以从所讨论的节点以精确 K跳数到达的所有节点。

我看了看，networkx唯一相关的功能是neighbors. 但是，这只会返回顺序为 1 的邻居。对于更高阶，我们需要迭代来确定完整的集合。我相信应该有一种更有效的方式来访问networkx.

是否有一个函数可以有效地返回 K 阶邻居，而无需增量构建集合？

编辑：如果 Python 中存在其他可能在这里有用的图形库，请提及这些。

Answer 1

您可以使用： nx.single_source_shortest_path_length(G, node, cutoff=K)

G您的图形对象在哪里。

Answer 2

对于 NetworkX，最好的方法可能是在每个 k 处构建一组邻居。您没有发布您的代码，但似乎您可能已经这样做了：

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

您使用修改后的 BFS 算法解决您的问题。当您将节点存储在队列中时，也要存储它的级别（与根的距离）。当您完成处理节点（所有邻居访问 - 节点标记为黑色）时，您可以将其添加到其级别的节点列表中。这是基于这个简单实现的示例：

#!/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

输出：

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

我不知道networkx，我也没有发现可以在 Graph Tool 中使用算法。我相信这样的问题还不够普遍，无法拥有自己的功能。此外，我认为为图形实例中的任何节点存储第 k 个邻居的列表会过于复杂、低效和冗余，因此这样的函数可能无论如何都必须遍历节点。

Answer 4

我有一个类似的问题，除了我有一个有向图，我需要维护边缘属性字典。如果需要，这种相互递归解决方案会保留边缘属性字典。

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 5

如前所述，以下解决方案为您提供所有次要邻居（邻居的邻居）并列出所有邻居一次（该解决方案基于 BFS）：

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

另一个稍微快一点的解决方案（6.68 µs ± 191 ns vs. 13.3 µs ± 32.1 ns，用 测量timeit）包括在无向图中，邻居的邻居可以再次成为源：

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

两种解决方案都将源本身作为 0 阶邻居。

所以这取决于你的上下文更喜欢哪一个。