0

给定一个有几百万条边的有向图，我试图为每个节点找到：

  1. 邻居的邻居列表（我们称他们为two_nei）。

  2. 每个two_nei（称为cn）的公共邻居的数量。

我处理这个问题的方法是：

  1. 创建一个dict以每个节点为键，一个list包含所有邻居作为值（neighbor_dictionary）。

  2. 创建一个dict以每个节点为键，一个list包含所有邻居的邻居（two_nei对于这个节点）作为值（second_dictionary）。

  3. 现在我想为图中的每个节点创建一个list（因为不知道该做什么） 。dict这些字典中的每一个都将包含每个two_nei节点作为键，值将是它们拥有的公共邻居的数量。

如您所见，这很容易变得复杂。我相信在 python 中有一种更简单、更优雅的方法来做到这一点。我是一个数学专业的人，我没有上过数据结构和算法方面的课程，但我相信我们可以使用队列来解决这个问题。

任何帮助将不胜感激。

4

2 回答 2

2

这是一个函数，它返回图中两个节点的共享第二邻居的数量。它使用networkx作为图表。根据每个节点中的数据量以及图的连接密集程度，这可能不起作用，因为它会在内存中创建潜在的大集合。

def num_shared_second_neighbors(graph, node1, node2):
    """Number of second neighbors shared by node1 and node2 in graph."""
    return len(set(second_neighbors(graph, node1)).intersection(set(second_neighbors(graph, node2))))

def second_neighbors(graph, node):
    """Yield second neighbors of node in graph.
    Neighbors are not not unique!
    """
    for neighbor_list in [graph.neighbors(n) for n in graph.neighbors(node)]:
        for n in neighbor_list:
            yield n

该函数second_neighbors是一个生成器，它通过执行简单的图遍历来生成节点的非唯一第二个邻居。该函数num_shared_second_neighbors仅返回两个节点的秒邻居集合交集的节点数。

于 2012-06-24T04:06:54.043 回答
0

这是您使用NetworkX编写的所需功能：

1. 邻居的邻居列表

def get_second_neighbors(graph, node) -> list:
    """
    Returns a list of unique second neighbors for a given node in the graph.
    """
    return [second_neighbor 
            for first_neighbor in graph.neighbors(node)
            for second_neighbor in graph.neighbors(first_neighbor) 
            if second_neighbor != node])

2.共享邻居数

def get_num_shared_neighbors(graph, node1, node2) -> int:
    """
    Returns a number of second neighbors shared by node1 and node2 in the graph.
    """
    return len(set.intersection(set(get_second_neighbors(graph, node1)), 
                                set(get_second_neighbors(graph, node2))))

我希望列表理解使它优雅且易于理解。

于 2021-04-15T04:36:18.870 回答