如何找到图中顶点子集的"center"？
How to find the "center" of a subset of vertices in a graph?
我有一个无向、正加权、连通图，顶点 V 和边 E。我还有一个顶点子集 S。现在 V 包含大约 22000 个顶点和 E 大约 23000 个边，但对于更大的输入，这些预计会增加到大约一百万个。另一方面，S 通常包含少于 1000 个顶点，并且它们在图中相对靠近。
我想找到 S 的“中心”，意思是 V 中的一个顶点 c 到 S 中最远顶点的距离为尽可能小。就像图表上的 graph center but only for a subset of vertices. [Edit:] It's also a 1-center problem；更一般的 k-center 问题是 NP-hard 但这个问题可能更容易。
有没有算法可以高效地找到这个中心？理想情况下，性能仅取决于 S 及其周围环境，而不取决于整个图。
我考虑过同时从 S 中的所有顶点 s_i 开始广度优先搜索，当所有 s_i 遇到顶点 v_i 时停止]，但这并不过分有效。这种情况下应该是可行的，但感觉可能还有更好的办法。
这是一个近似算法，应该提供一个不错的时间质量权衡曲线。第一部分归功于 Teofilo F. Gonzalez（Clustering to minimize the maximum intercluster distance, 1985），但我找不到第二个副手的引用，可能是因为它太薄而不能成为主要结果。
设 k 是您愿意 运行 Dijkstra 算法的次数（t运行 在它达到所有 S 之后，如您所建议）。 Gonzalez 的算法 运行s Dijkstra k − 1 次将终端 S 划分为 k 个簇，以 2-近似最小化最大簇半径。方便地，它作为副产品生成 k 个分离良好的中心 C 和其中 k-1 个的最短路径树。我们再 运行 Dijkstra 一次，然后选择关于 C 的最优 1-center。这个中心满足
approximate objective ≤ optimal objective + maximum cluster radius.
这里用 k 来量化近似因子有点棘手。关键是有界的倍增维度，我将暂时假设欧几里德距离来说明这一点。假设我们试图找到半径为 1 的圆盘的 1 中心。最佳值是圆盘的中心。可以有多少个以圆盘为中心的不相交的半径为 r 的球？它们的面积包含在半径为 (1+r) 的圆盘内，圆盘的面积为 π(1+r)²，因此最多 (π(1+r)²)/πr² = (1/r + 1)²。最大簇半径为 2r，或者以 k 为单位，大约是最佳 objective 的 4/√k 倍，因此 k = 100 将为您提供大约 20% 的最佳解决方案。倍维基本上就是用这个说法来定义的
作为参考，冈萨雷斯的算法是
选择S中的任意点
重复k − 1次：运行 Dijkstra从最近选择的点开始，选择S中的下一个点，使到所有之前选择的点的最小距离最大化。
然后我们 运行 Dijkstra 从最近选择的点再一次 select 所选点的最佳 1 中心。
我不知道如何分析这个算法，也没有引用，但看起来它可能有效。
选择一个起始中心。您当前的近似值应该适用于此。
计算从当前中心到S的最短路径树。
修剪树，使所有叶子都属于 S 并计算其中心。
如果这个中心比根更好，回到第2步。
关于这个算法我可以真正声明的两个正式属性是它总是终止并且它永远不会比起始中心差（因为如果树的中心不是根，那么它一定是更好的center than root, because the missing edges can improve it but not the root).
要有效地计算树的中心，请使用到其所有后代根的最大距离标记每个节点（通过按 post 顺序访问节点在线性时间内）。然后通过具有最大标签的 child 下降到树中，只要它提高了半径。 child 子树中的所有内容都将靠 child 的 parent 边的长度靠近；其他一切都会以相同的数量进一步发展。
一个想法：
让我们以保持其他节点距离不变的方式摆脱所有不在 S 中的节点。怎么做：
- 对于不在 S 中的每个节点，删除该节点并用连接其每两个邻居的边替换它。如果这样的边比已经连接这些节点的边短，则替换它。 请注意这应该是合理的，因为您提到边的数量与节点的数量大致相同。
- 这应该不会破坏任何东西，因为它通过用新边连接它们来保持每两个节点之间的最小距离相同。它只是删除了一些节点。
- 从度数最低的节点开始：可以立即切割叶子（除非在 S 中），度数为 2 的节点将被替换为单条边（技术上是 K2）。 deg > 2 的任何节点都将被替换为 K(neighbors)。幸运的是，你图中的平均度数似乎没有你提到的节点和边数相似那么大。
- 最坏情况的解构，即完整图需要 |V| * |E|（每个节点都有您需要替换的所有边，每次替换节点时，您都会更新图形的其余部分和所有边）。你的情况应该便宜得多，因为你的图表只有 ~|V|边缘，所以你很可能不会得到完整的 |V|^|E| (|V|^3) 直到更远的地方，当计数变得易于管理时。您还希望通过这种方式对节点进行排序，因此可能会包含一些 LOG(|V|) 维护 - 目标是等待合并完整的图形，直到剩余的节点尽可能少。
修剪完成后，只需使用任何合理的算法找到中心，因为您将只有来自 |S| 的节点剩余和|S|比|V|小很多。
我有一个无向、正加权、连通图，顶点 V 和边 E。我还有一个顶点子集 S。现在 V 包含大约 22000 个顶点和 E 大约 23000 个边，但对于更大的输入，这些预计会增加到大约一百万个。另一方面，S 通常包含少于 1000 个顶点，并且它们在图中相对靠近。
我想找到 S 的“中心”，意思是 V 中的一个顶点 c 到 S 中最远顶点的距离为尽可能小。就像图表上的 graph center but only for a subset of vertices. [Edit:] It's also a 1-center problem；更一般的 k-center 问题是 NP-hard 但这个问题可能更容易。
有没有算法可以高效地找到这个中心？理想情况下，性能仅取决于 S 及其周围环境，而不取决于整个图。
我考虑过同时从 S 中的所有顶点 s_i 开始广度优先搜索，当所有 s_i 遇到顶点 v_i 时停止]，但这并不过分有效。这种情况下应该是可行的，但感觉可能还有更好的办法。
这是一个近似算法，应该提供一个不错的时间质量权衡曲线。第一部分归功于 Teofilo F. Gonzalez（Clustering to minimize the maximum intercluster distance, 1985），但我找不到第二个副手的引用，可能是因为它太薄而不能成为主要结果。
设 k 是您愿意 运行 Dijkstra 算法的次数（t运行 在它达到所有 S 之后，如您所建议）。 Gonzalez 的算法 运行s Dijkstra k − 1 次将终端 S 划分为 k 个簇，以 2-近似最小化最大簇半径。方便地，它作为副产品生成 k 个分离良好的中心 C 和其中 k-1 个的最短路径树。我们再 运行 Dijkstra 一次，然后选择关于 C 的最优 1-center。这个中心满足
approximate objective ≤ optimal objective + maximum cluster radius.
这里用 k 来量化近似因子有点棘手。关键是有界的倍增维度，我将暂时假设欧几里德距离来说明这一点。假设我们试图找到半径为 1 的圆盘的 1 中心。最佳值是圆盘的中心。可以有多少个以圆盘为中心的不相交的半径为 r 的球？它们的面积包含在半径为 (1+r) 的圆盘内，圆盘的面积为 π(1+r)²，因此最多 (π(1+r)²)/πr² = (1/r + 1)²。最大簇半径为 2r，或者以 k 为单位，大约是最佳 objective 的 4/√k 倍，因此 k = 100 将为您提供大约 20% 的最佳解决方案。倍维基本上就是用这个说法来定义的
作为参考，冈萨雷斯的算法是
选择S中的任意点
重复k − 1次：运行 Dijkstra从最近选择的点开始，选择S中的下一个点，使到所有之前选择的点的最小距离最大化。
然后我们 运行 Dijkstra 从最近选择的点再一次 select 所选点的最佳 1 中心。
我不知道如何分析这个算法，也没有引用，但看起来它可能有效。
选择一个起始中心。您当前的近似值应该适用于此。
计算从当前中心到S的最短路径树。
修剪树，使所有叶子都属于 S 并计算其中心。
如果这个中心比根更好，回到第2步。
关于这个算法我可以真正声明的两个正式属性是它总是终止并且它永远不会比起始中心差（因为如果树的中心不是根，那么它一定是更好的center than root, because the missing edges can improve it but not the root).
要有效地计算树的中心，请使用到其所有后代根的最大距离标记每个节点（通过按 post 顺序访问节点在线性时间内）。然后通过具有最大标签的 child 下降到树中，只要它提高了半径。 child 子树中的所有内容都将靠 child 的 parent 边的长度靠近；其他一切都会以相同的数量进一步发展。
一个想法：
让我们以保持其他节点距离不变的方式摆脱所有不在 S 中的节点。怎么做：
- 对于不在 S 中的每个节点，删除该节点并用连接其每两个邻居的边替换它。如果这样的边比已经连接这些节点的边短，则替换它。 请注意这应该是合理的，因为您提到边的数量与节点的数量大致相同。
- 这应该不会破坏任何东西，因为它通过用新边连接它们来保持每两个节点之间的最小距离相同。它只是删除了一些节点。
- 从度数最低的节点开始：可以立即切割叶子（除非在 S 中），度数为 2 的节点将被替换为单条边（技术上是 K2）。 deg > 2 的任何节点都将被替换为 K(neighbors)。幸运的是，你图中的平均度数似乎没有你提到的节点和边数相似那么大。
- 最坏情况的解构，即完整图需要 |V| * |E|（每个节点都有您需要替换的所有边，每次替换节点时，您都会更新图形的其余部分和所有边）。你的情况应该便宜得多，因为你的图表只有 ~|V|边缘，所以你很可能不会得到完整的 |V|^|E| (|V|^3) 直到更远的地方，当计数变得易于管理时。您还希望通过这种方式对节点进行排序，因此可能会包含一些 LOG(|V|) 维护 - 目标是等待合并完整的图形，直到剩余的节点尽可能少。
修剪完成后，只需使用任何合理的算法找到中心，因为您将只有来自 |S| 的节点剩余和|S|比|V|小很多。