1

我有一个无向图 A，它具有：任何两个节点之间没有多重链接，没有自连接节点，可以有一些孤立的节点（度数为 0 的节点）。

我需要遍历图 A 中节点对的所有可能组合，为不存在的链接分配某种分数（假设我的图有 k 个节点和 n 个链接，那么组合的数量应该是（k* (k-1)/2 - n) 个组合）。我分配分数的方式是基于两个组合节点之间的公共邻居节点。

例如：AD之间的分数应该是1，GD之间的分数应该是0 ... 例如：AD之间的分数应该是1，GD之间的分数应该是0 ...

最大的问题是我的图有超过 100.000 个节点，处理几乎 10^10 个组合太慢了，这是我第一次尝试接近解决方案。

我的第二个想法是，由于该算法是基于节点的公共邻居，我可能只需要查看邻居，以便我可以分配不同于 0 的分数。其余的可以确定为 0，无需计算。但这可能会重复组合。

任何接近此解决方案的想法都值得赞赏。请记住，实际网络有超过 100.000 个节点。

4

1 回答 1

0

如果将图形表示为邻接列表（而不是邻接矩阵），则可以利用图形只有 600,000 条边这一事实来减少计算时间。

V[j]让我们取一个具有邻居V[i]和的节点V[k]：

V[i] ---- V[j] ---- V[k]

要查找所有此类邻居对，您可以获取相邻节点的列表V[j]并找到这些节点的所有组合。为避免重复，您必须生成组合而不是端节点的排列，V[i]并V[k]要求i < k.

或者，您可以从 node 开始V[i]并找到距离为 2 的所有节点V[i]。让S是所有与 相邻的节点的集合V[i]。对于 中的每个节点V[j]，S创建一个路径V[i]-V[j]-V[k]，其中：

  1. V[k]毗邻V[j]
  2. V[k]不是S（避免直接连接的节点）的元素
  3. k != i（避免循环）
  4. k > i（避免重复）

我个人更喜欢这种方法，因为它在移动到下一个节点之前完成了一个节点的邻接列表。

假设您在具有约 100,000 个节点的图中有约 600,000 条边，假设边在所有节点上均匀分布，每个节点的平均度数为 12。那么每个节点的可能路径数约为10 2 . 超过 10 5个节点，总路径数量约为 10 7个，而不是完整图的理论限制 10 10 个。数量仍然很大，但比以前快了一千倍。

于 2013-09-13T18:52:22.993 回答