连接顶点的邻居之间的最短路径长度（不是任意两个随机顶点！）

Question

我之前问了一个类似的问题，但我认为，目前尚不清楚。我有一个无向和未加权的10000顶点和5000000边缘的图形，我把它们读作python作为边缘列表。

在我的工作中，我试图从每个边缘构建一个函数，该函数取决于每个边缘上的顶点邻居之间的距离。假设我们有两个连接的顶点v1，v2代表一个边，对于v1，有n1个连接的邻居，并且还有n2个邻居连接到v2。为了构建我的函数，我需要获得n1和n2个邻居之间的距离。对于图中的所有边，该函数如下所示：

e_1*d_1 +e_1*d_2 +...+e_1*d_n+...e_m*d_1+...e_m*d_n

其中n是每条边上两个顶点的邻居数，d_n是顶点之间的距离，m是图中边的数量，e_m是该图中的最后一条边。

通常，如果我们想要获得最短路径长度，我们会考虑像Dijkstra算法或Bfs这样的图遍历，尤其是我的图是未加权的。我使用了许多函数，这些函数已经在networkx和igraph等软件包中编写，但这些函数效率不高，并且耗费了大量的时间用于图形。例如，函数shortest_paths_dijkstra()takes大约6.9小时来获得距离，因为我需要多次调用它。此外，函数all_pairs_shortest_path _length需要大约13分钟（通过将路径长度固定为截止值为3），另外16分钟用于调用图中每对邻居的距离！

正如在问题中所写，我们需要获得v1，v2的邻居之间的距离，因此最大距离是3，因为v1，v2是连接的。我觉得有一个更聪明的解决方案，通过使用路径的可能距离（在我的情况下）是0, 1, 2, 3来减少时间复杂度，因为我不需要遍历源之间的每条路径的整个图形和目标！只是我正在寻找一种巧妙的方法来获得邻居之间的距离（不是任意两个随机顶点）！

我写了这段代码，但需要花费很多时间，大约54分钟，所以效率也不高！

neighbor1 = {}
neighbor2 = {}
distance = {}
for i in list(edges.values()):
  list_of_distances = []
  neighbor1 = tuple(graph.vs[graph.neighbors(i[0], mode="all")]["name"])
  neighbor2 = tuple(graph.vs[graph.neighbors(i[1], mode="all")]["name"])
  for n2 in neighbor2:
    for n1 in neighbor1:
       if n1 == n2:
            list_of_distances.append(0)
       elif (n1 != n2) and not graph.are_connected(n1,n2):
            if ( graph.are_connected(i[0],n2) ) or ( graph.are_connected(n1,i[1])  ): 
               list_of_distances.append(2)
            elif ( not graph.are_connected(i[0],n2)  ) or ( not graph.are_connected(n1,i[1]) ):
               list_of_distances.append(3)
       else:
            list_of_distances.append(1)
  distance[tuple(i)] = list_of_distances

我想知道是否有另一种方法不需要大量的内存和时间来获得这些距离，或者是否可以修改一个图形遍历方法，如Bfs或Dijkstra，所以没有必要搜索整个绘制每次迭代的图形，只是为了做一些本地的事情（如果可以的话）。谢谢你的帮助

Answer 1

您的计算任务非常繁重，因此您的脚本工作数小时是正常的。您可以尝试将其与CUDA或类似的东西并行化，或者您可以尝试构建大型缓存（GB）。但是如果你不能或不想要，我建议你不要使用networkx / igraph函数，因为它们对你来说非常慢。没有1000000 DFS运行，您可以解决您的问题。这是Python集使用的可能解决方案之一（我认为它会比你的更快，也许不是很快）。

import networkx as nx

# Create a graph like yours
G = nx.fast_gnp_random_graph(1000, 0.05)

# Create neighbours dict
G_adj = dict(G.adjacency())
nbrs_dict = {node: {n for n in G_adj[node]} for node in G_adj}

# Result dict
distances = {}

# For every edge:
for e in G.edges:

    # Start value
    dist_value = 0

    # Get N1 and N2 neighbours
    n1_nbrs = nbrs_dict[e[0]]
    n2_nbrs = nbrs_dict[e[1]]

    # Triangles - nodes that connected to both N1 and N2
    # Every triangle value = 0
    tri = n1_nbrs & n2_nbrs
    for t in tri:

        # Get neighbours to find nodes with distance length = 2
        t_nbrs = nbrs_dict[t]

        t_in_n1 = n1_nbrs & t_nbrs
        t_in_n2 = n2_nbrs & t_nbrs

        t_not_in_n1 = n1_nbrs - t_nbrs
        t_not_in_n2 = n2_nbrs - t_nbrs

        dist_value += len(t_in_n1) + len(t_in_n2)
        dist_value += (2 * len(t_not_in_n1)) + (2 * len(t_not_in_n2))

    # Exclude all triangle nodes because we processed them all
    n1nt_nbrs = n1_nbrs - tri
    n2nt_nbrs = n2_nbrs - tri

    # Select squares - nodes with length = 1
    direct = set([])
    for n1 in n1nt_nbrs:
        nbrs = nbrs_dict[n1]
        d = nbrs & n2nt_nbrs
        for node in d:
            direct.add((n1, node))
    dist_value += len(direct)

    # Exclude squares so we have only nodes with length = 3
    n1final = n1nt_nbrs - set(e[0] for e in direct)
    n2final = n2nt_nbrs - set(e[1] for e in direct)
    dist_value += 3 * len(n1final) * len(n2final)

    # Distance for an edge
    distances[e] = dist_value

无论如何，你的问题有O(n^3)的复杂性，所以我强烈建议你尝试拆分图表。也许你有bridges或只有几个连接组件。如果您将单独处理它们，您将极大地提高速度。