图中的第K个邻居 - Python networkx

Question

我有一个有向图，想要高效地查找一个节点的所有K阶邻居节点列表。K阶邻居定义为从该节点恰好经过 K 次跳跃可以到达的所有节点。

我看了一下 networkx，唯一相关的函数是 neighbors，但这只返回一阶邻居。对于更高阶，我们需要迭代以确定完整集合。我相信在 networkx 中应该有一种更有效的访问K阶邻居的方式。

是否存在一种能够高效地返回 K 阶邻居而无需逐步构建集合的函数呢？

编辑：如果存在其他 Python 图形库可能在此处有用，请提及。

- Nik

Answer 1

你可以使用以下代码来查找从给定节点开始到其他节点的最短路径长度，该路径长度小于或等于K： nx.single_source_shortest_path_length(G, node, cutoff=K) 其中，G是你的图形对象。

- kelvin

---

如果在整个图上运行Dijkstra算法，这将是浪费的。它是否真的这样做了？ - Simd

@graffe 通过指定cutoff=K，似乎它不会在整个图上运行：它应该只在第K个邻居上运行。（我使用了一个10k节点路径图，并计时了各种K值的输出来进行测试。） - Tashus

Answer 2

是的，您可以获得一个节点的k阶邻域图。

subgraph = nx.ego_graph(G,node,radius=k)

然后，邻居节点就是子图中的节点。

neighbors= list(subgraph.nodes())

- feverer

---

这是最简单的答案，看起来这可能是开发者预期的方法。我认为相对于被接受的答案，低投票数只是因为另一个答案已经有九年了，但是是否选择这种方法还有其他原因吗？例如大型图表的性能等等？ - Tashus

Answer 3

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

- Aric

---

确实。我正在做同样的事情。事实上，为了加快速度，我正在创建并存储第 i 个邻居，其中 i 的范围从1一直到 K。我希望我能找到捷径。看来没有。感谢您的回复。 - Nik

你在循环中哪里使用了 l？ - MERose

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

- notconfusing

Answer 5

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

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

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

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

这两种解决方案都将源代码本身作为零阶邻居。

因此，取决于您的上下文环境，您可以选择其中一种。

- Michael Dorner

Answer 6

你可以使用修改后的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-th 邻居列表会过于复杂、低效和冗余，因此这样的函数可能仍需要迭代节点。

- Nykakin

---

我感谢您的回答，尽管这不是我要找的。我已经有一个版本，通过增加一阶邻居集合的方式逐步构建第K阶邻居集合，然后添加它们的邻居，直到达到第K阶邻居。但这超出了networkx所提供的范围。 - Nik

Answer 7

看起来你正在寻找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()

- seeinglogic