java - 获得无向图中所有节点组合对的最佳算法(需要提高时间复杂度)

Question

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

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

例如:A-D 之间的分数应为 1，G-D 之间的分数应为 0 ...

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

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

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

Answer 1

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

让我们以一个节点V[j]为例与邻居V[i]和 V[k] :

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

要找到所有这样的邻居对，您可以使用与 V[j] 相邻的节点列表并找到这些节点的所有组合。为避免重复，您必须生成组合而不是端节点的排列 V[i]和 V[k]通过要求 i < k .

或者，您可以从节点 V[i] 开始并找到与 V[i] 距离为 2 的所有节点.让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² 的顺序。超过 10⁵ 个节点给出了大约 10⁷ 个总路径，而不是完整图的理论限制 10¹⁰。数量仍然很大，但比以前快了一千倍。