我有一个包含 2000 万用户和这些人之间联系的数据库。如何在编程 中以最有效的方式证明“六度分离”的概念？
问问题
4297 次
4 回答
11
您只想测量图形的直径。 这正是找出图中最远连接节点之间分离的指标。
Google上有很多算法， Boost graph也是。
于 2009-06-12T20:41:38.503 回答
4
您可能可以将图形放入内存中（表示每个顶点都知道其邻居列表）。
然后，从每个顶点n，您可以运行广度优先搜索（使用队列）到 6 的深度并计算访问的顶点数。如果不是所有的顶点都被访问过，那么你就证明了这个定理。在其他情况下，继续下一个顶点n。
这是 O(N*(N + #edges)) = N*(N + N*100) = 100N^2，如果用户平均有 100 个连接，这对于 N=2000 万来说并不理想。我想知道上述库是否可以以更好的时间复杂度计算直径（一般算法为 O(N^3)）。
单个顶点的计算是独立的，因此它们可以并行完成。
一点启发式：从度数最低的顶点开始（更好的机会反驳定理）。
于 2009-06-12T21:14:38.703 回答
2
我认为最有效的方法（最坏的情况）几乎是 N^3。建立一个邻接矩阵，然后取该矩阵 ^2、^3、^4、^5 和 ^6。查找图中从矩阵 0 到矩阵 ^ 6 的任何条目。
启发式地，您可以尝试挑出子图（仅通过相对较少数量的“桥”节点连接到其他集群的大群人），但绝对不能保证您会拥有任何子图。
于 2009-06-12T21:30:07.433 回答
2
好吧，已经给出了更好的答案，但是我想我会使用Floyd-Warshall所有对最短路径算法，即 O(n^3)。我不确定图形直径算法的复杂性，但它“听起来”像这样也是 O(n^3)。如果有人知道，我想澄清一下。
On a side note, do you really have such a database? Scary.
于 2009-06-15T10:18:59.780 回答