获取图中最近的邻居的最佳方法是什么？

Question

我需要计算一些其值由以下无效的伪python代码给出的值：

def foo(a,b):
   tmp = 0
   for i in graph.nodes():
       for j in graph.nodes():
          tmp += c
          if (i and j are neighbors):
              tmp += a - c
          elif (i and j are next-neighbors):
              tmp += b - c
   return tmp

换句话说，给定所有节点对，foo = a *（E =边数）+ b *（EE =不是邻居但有一个公共邻居的对数）+ c *（N（N-1 ）/ 2-EE-E）。

我试图考虑某种广度优先搜索，但我没有。

编辑：更多信息

• 该图不是静态的。我不断添加和删除边，所以我不能只计算一次。我必须不断更新“下一个邻居的名单”。
• 我将图形存储为邻接矩阵。

Answer 1

这是一个大概的主意。但是首先，要有一些假设：1.无向图2.恒定顶点数

您的图形不断变化。因此，您需要有效地更新邻居（边缘）和第二邻居的数量。第一个是琐碎的，所以让我们看一下第二个邻居。

根据@Patrick的建议，让我们使用A^2，然后看看如何可以高效地更新它，而不必每次都从头开始重新计算它。 A^2_ij是从i到的长度为2的路径的数量j，请记住，它也会有对角线条目，因为从顶点到自身始终存在长度为2的路径。如果您拥有A^2，则可以轻松计算第二邻居的数量，因此让我们A^2在图表变化时将所有更新都保留在内存中。

如何有效更新A^2：

添加/删除边时，将A通过B仅具有两个条目的矩阵进行更改。假设我们要添加（而不是移除）一条边。然后(A+B)^2 = A^2 + AB + BA + B^2。

假设添加的边为(i,j)。

• B^2是琐碎的：(B^2)_ii = (B^2)_jj = 1，其余为0。
• AB = transpose(BA)因此，我们只需要计算二者之一即可BA。事实证明，行i的BA是行j的A和行j的BA是行i的A，剩下的就是零。同样，计算速度很快。

去除边缘将是相似的。

您只需要计算第二个邻居的数量，因此无需计算A^2每个步骤中有多少个非零非对角线条目，通过进行一些额外的工作，您可以计算A^2添加时非零条目的数量变化AB + BA。

编辑

整个事情用另一种语言解释：

让我们跟踪矩阵中任意两个顶点之间的两个长度的路径M。当我们在i和之间添加（删除）一条边时j，长度为2的路径的数量将在i和的所有邻居j以及j和的所有邻居之间增加（减少）一个i，因此在每次更改时M很容易及时更新O(n)图形。