如何找到图中一组顶点的“中心”？

Question

我有一个无向、正权值、连通的图，其顶点数为V，边数为E。我还有一个顶点子集S。目前V包含约22000个顶点，E大约有23000条边，但对于更大的输入，这些数字预计会增加到约一百万。另一方面，S通常只包含少于1000个顶点，并且它们在图中相对靠近。

我想找到S的“中心”，即从中距离最远的顶点到顶点c的距离尽可能小的顶点。就像图的中心，但只适用于顶点子集。[编辑：]这也是图上的1-中心问题；更一般的k-中心问题是NP难的，但这个问题可能较容易解决。

有没有一种算法可以有效地找到这个中心？理想情况下，性能仅取决于S及其周围环境，而不取决于整个图。

我考虑同时从集合 S 的所有顶点 s_i 开始进行广度优先搜索，当所有的 s_i 都遇到了顶点 v_i时停止。但这种方法效率不高，虽然在这种情况下可能可行，但感觉应该有更好的方法。

- Thomas

---

可能比 O(|S|²) 还要糟糕，因为你的广度优先搜索可能必须经过来自 V \ S 的顶点。 - Stef

你可能会在计算机科学的 StackExchange 上找到更有见地的答案。 - Stef

你所表述的策略将需要 O(|S| * |E|) 的时间，而不是 O(|S|^2) 的时间：每次广度优先搜索需要 O(|V|+|E|)=O(|E|) 的时间，而你要进行 |S| 次。提前停止并不会改变渐进最坏情况下的运行时间。 - D.W.

我可以理解更关注实际性能而不是渐进最坏情况运行时间的想法。在这种情况下，我建议您从您的帖子中删除关于O（|S|^2）时间的声明。我是在回应那个具体的声明。如果您不想进行最坏情况分析，那么我猜您将不得不决定您想要什么类型的分析，可以做出什么假设以及如何评估答案。 - D.W.

考虑到您的并行Dijkstra方法可能足够快，您是否对近似算法感兴趣？ - David Eisenstat

Answer 1

我不知道如何分析这个算法，也没有引用资料，但它似乎可以工作。

1. 选择一个起始中心。您当前的近似应该适用于此。

2. 从当前中心计算到S的最短路径树。

3. 修剪树以使所有叶子属于S并计算其中心。

4. 如果此中心优于根，则返回步骤2。

关于此算法，我能够真正声明的两个形式属性是它总是终止并且它永远不会比起始中心更差（因为如果树的中心不是根，那么它必须是比根更好的中心，因为缺失的边可以改善它但不能改善根）。

要高效地计算树的中心，请为每个节点标记其后代中距离根的最大距离（通过按后序访问节点以线性时间完成）。然后通过具有最大标签的子节点降低树，只要它改善了半径即可。子树中的所有内容都将通过子节点的父边长度靠近；其他内容将增加相同数量的距离。

- David Eisenstat

---

我还没有时间测试这个，但是我会暂时接受它，因为它是最简单的，应该能够完成工作。一旦我尝试了这种方法，我会更新的。 - Thomas

结果证明我正确地放置了勾号。这个算法在运行时间方面优于你的另一个建议，即使我在另一个算法中将_k_设置得低至3。就输出质量而言，我需要将_k_设置为36才能从另一个算法中获得更好的结果，而此时它需要运行10倍以上的时间。 - Thomas

@Thomas 谢谢你的更新。这对我来说并不是太令人惊讶，因为另一个的重点是最坏情况的保证，但通常输入数据与对手的差距很大。 - David Eisenstat

就我个人而言，这个程序在我的输入上最多收敛于5步，通常更少。 - Thomas

@Thomas 是的，我指的是偏心率。如前所述，我们最初计算每个子树的高度。然后，当我们下降时，我们有当前候选中心点v和从v到不在v子树中的节点的最大距离（最初为零）。v的偏心率是v的高度和最大非子树的最大值。一旦我们确定了v的高度最大的子节点w，我们通过两个步骤更新最大的非子树。首先，对于v的每个子节点x（其中x ≠ w），我们将最大的非子树更新为max（最大的非子树，length（vx）+ height（x））。然后，我们通过length（vw）增加最大的非子树。 - David Eisenstat

Answer 2

这是一个近似算法，可以提供合理的时间和质量折衷曲线。第一部分由Teofilo F. Gonzalez（聚类以最小化最大簇间距离，1985）完成，但我无法即时找到第二个引文，可能因为其太薄弱而不足以成为主要结果。

令k为您愿意运行Dijkstra算法的次数（在它到达S的所有点后被截断，正如您建议的那样）。Gonzalez算法运行Dijkstra k-1次，将终端S划分为k个簇，以2倍近似的方式最小化最大簇半径。方便地，它生成k个良好分离的中心C和k-1个最短路径树作为副产品。我们再运行一次Dijkstra算法，然后选择相对于C最优的1个中心。这个中心满足以下条件：

approximate objective ≤ optimal objective + maximum cluster radius.

这里用k来量化近似因子有点棘手。关键在于有界的加倍维度，我会以欧几里得距离为例进行说明。假设我们试图找到半径为1的圆盘的1-中心。最佳解是圆盘的中心。圆盘内部最多可以有多少个半径为r的不相交球？它们的面积包含在一个半径为（1+r）的圆盘内，其面积为π（1+r）²，因此最多为（π（1+r）²）/ πr² =（1 / r + 1）²。最大群集半径将为2r，或者按照k的顺序，约为最优目标的4 /√k倍，因此k = 100将为您提供约20％最优解的解决方案。加倍维度基本上使用这个论点作为定义。

参考文献，Gonzalez算法如下：

1. 选择S中的任意一点。
2. 重复k-1次：从最近选择的点运行Dijkstra，选择S中下一个点，使得到所有先前选择的点的最小距离最大化。

然后我们再从最近选择的点运行Dijkstra一次，然后选择所选点的最优1-中心。

- David Eisenstat

Answer 3

一个想法：

让我们以一种保持其他节点距离不变的方式摆脱所有不在S中的节点。如何做到这一点：

• 对于每个不在S中的节点，删除该节点并用连接其每两个邻居节点的边替换它。如果这样的边比已连接这些节点的边要短，请进行替换。请注意，正如您提到的，这应该是合理的，因为边的数量大致等于节点的数量。
• 这不会破坏任何东西，因为它通过连接新的边使每两个节点之间的最小距离保持不变。只是移除了一些节点。
• 从度数最低的节点开始：叶子节点可以立即被剪掉（除非在S中），度为2的节点将被替换为一条单独的边（技术上是一个K2图）。任何度数大于2的节点将被K(邻居)图替代。幸运的是，您的图的平均度数似乎不是很大，因为您提到节点和边的数量相似。
• 构建最坏情况（完全图）的过程需要|V| * |E|的时间（每个节点都有需要替换的所有边，每次替换一个节点都需要更新其余的图和所有的边）。由于您的图只有约|V|条边，所以您很可能不会达到完全的|V|^|E|（|V|^3）直到更进一步的时候，当数量变得可管理时。您还需要通过合适的方式保持节点排序，所以可能会包含一些LOG(|V|)的维护 - 目标是在剩下的节点尽可能少的情况下等待完成图的合并。

这个修剪完成后，只需使用任何合理的算法找到中心，因为你只剩下来自 |S| 的节点，而 |S| 要比 |V| 小得多。

- Shamis

---

感谢您的回答。这种方法对我来说并不是很有效，原因有两个：1.由于“对于不在S中的每个节点”，性能取决于顶点的总数（比|S|要大得多），2.它假设所寻找的中心实际上是S的成员。 - Thomas

啊，我不知道中心点不需要在S内这一事实。我的理解是你要在S内寻找一个节点，同时考虑其他节点以可能缩短路径。那么我的解决方案就没用了^^。然而，至于使用所有其他顶点-其他人也这样做，因为据我所见，他们会搜索整个图。 - Shamis

只要已经到达了S中的所有顶点，就可以停止搜索。这样可以缩短搜索时间，因为S中的顶点相对较近。 - Thomas

在这种情况下，可以围绕节点取凸包，并仅在其中搜索？这可能会显著减少相关节点的数量。 - Shamis