查找节点的n度邻域

Question

我刚接触networkx，实际上对如何高效地找到一个节点的n度邻居有点困惑。一个节点v_i的n度邻居是指从v_i出发，经过n次跳跃能到达的节点集合。给定一个特定的n，我需要为图中的每个节点找到它的n度邻居。

假设我有一个这样的图，我想找到节点v1的n=1邻居。那就是v2和v3。接下来，如果我想找到节点v1的n=2邻居，那就是v4。

Answer 1

nx.descendants_at_distance() 这个函数可以解决问题（虽然它是为有向图设计的）：

G = nx.Graph()
G.add_edges_from([('v1', 'v2'), ('v2', 'v4'), ('v2', 'v4'), ('v1', 'v3')])
nx.descendants_at_distance(G, 'v1', distance=2) # returns {'v4'}

来自 源代码注释：

This is basically BFS, except that the queue only stores the 
nodes at `current_distance` from source at each iteration.

Answer 2

使用邻接矩阵找到n跳邻居

import networkx as nx
 
G = nx.Graph()
G.add_edges_from([('v1','v2'),('v2','v4'),('v1','v3')])

def n_neighbor(G, id, n_hop):
    node = [id]
    node_visited = set()
    neighbors= []
    
    while n_hop !=0:
        neighbors= []
        for node_id in node:
            node_visited.add(node_id)
            neighbors +=  [id for id in G.neighbors(node_id) if id not in node_visited]
        node = neighbors
        n_hop -=1
        
        if len(node) == 0 :
            return neighbors 
        
    return list(set(neighbors))

print(n_neighbor(G, 'v2', 1))

功能：

G: Networkx Graph
id : Root node Id to find neighbors
n_hop : hop length

返回：

Neighbor list

输出：

print(n_neighbor(G, 'v2', 1)) 
['v1', 'v4']

Answer 3

当你在一个图上进行广度优先搜索（BFS），从一个根节点r开始时，节点会按照离r的距离从近到远的顺序被考虑。

所以，在进行广度优先搜索的时候，你只需要记录节点的层级。想了解更多，可以查看这个链接：http://en.wikipedia.org/wiki/Level_structure。

Answer 4

找到一个节点的n个邻居最有效的方法是使用深度优先搜索。你可以在这里了解更多：http://en.wikipedia.org/wiki/Depth-first_search。下面这个函数可以返回从起始节点出发的所有邻居，适用于所有距离。不过，如果你想找到所有节点的n个邻居，直接对每个节点都使用这个函数就不是最有效的办法。更好的方法是只对每个连通部分的起始节点使用这个函数，然后根据这些起始节点来计算其他节点的n个邻居，但这样做会复杂一些。

import networkx as nx

def n_neighbor(G, start):

    #  {distance : [list of nodes at that distance]}
    distance_nodes = {}

    # nodes at distance 1 from the currently visited ones
    next_shell = G.neighbors(start)

    # set of all visited nodes
    visited=set()
    visited.add(start)

    # how fare we are from start
    distance = 0

    # until we run out of nodes
    while len(next_shell) > 0:

        # this will be the next shell
        shell_after_this = []

        # update distance
        distance += 1
        distance_nodes[distance] = []

        # update visited and distance_nodes
        for node in next_shell:
            visited.add(node)
            distance_nodes[distance].append(node)


        # compute shell_after_this
        for node in next_shell:
            # add neighbors to shell_after_this
            # if they have not been visited already
            for neighbor in G.neighbors(node):
                if neighbor not in visited:
                    shell_after_this.append(neighbor)

        # we repeat with the new_shell
        next_shell = set(shell_after_this)

    return distance_nodes


# example 
G=nx.Graph()

G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,3)
G.add_edge(2,4)
G.add_edge(3,5)
G.add_edge(5,17)
G.add_edge(2,6)

print n_neighbor(G, 1)    

Answer 5

在编程中，有时候我们需要处理一些数据，这些数据可能来自不同的地方，比如用户输入、文件或者网络请求。为了让程序能够理解这些数据，我们通常需要将它们转换成程序能处理的格式。

比如说，如果你有一个数字的字符串（像“123”），但程序需要的是一个真正的数字（123），那么你就需要把这个字符串转换成数字。这种转换的过程在编程中是很常见的。

另外，有些时候我们需要把程序中的数据转换成字符串，以便于显示给用户或者保存到文件中。比如说，如果程序计算出了一个结果是100，可能我们需要把它转换成字符串“100”，这样才能在网页上显示出来。

总之，数据的转换是编程中非常重要的一部分，它帮助我们让程序和人类之间的沟通变得更加顺畅。

import networkx as nx
G = nx.Graph()
G.add_edges_from([('v1','v2'),('v2','v4'),('v1','v3')])

def neighborhood(G, node, n):
    path_lengths = nx.single_source_dijkstra_path_length(G, node)
    return [node for node, length in path_lengths.iteritems()
                    if length == n]

print(neighborhood(G, 'v1', 1))
# ['v2', 'v3']
print(neighborhood(G, 'v1', 2))
# ['v4']