Boost图库：有没有内置BGL社区检测一个整洁的算法？

Question

人在那里使用BGL大型生产服务器？

• 多少节点没有网络组成的呢？
• 你如何处理community detection
• BGL有没有很酷的方式来检测社区？
• 有时两个社区可能一起通过一个或两个边链接，但这些边缘是不可靠的，可以消失。有时根本没有边缘。

可能有人对如何解决这一问题上作简短发言。 请打开我的脑海，激励我。

到目前为止，我已经成功地制定出如果两个节点是在一个小岛上（在社区）的，以免昂贵的方式 ，但现在我需要找出其中的不同海岛两个节点彼此最接近。我们只能最小限度地使用不可靠的地理数据。

如果我们形象地把它比作一个大陆和岛屿，并把它拿出来的社会距离上下文。我想弄清楚哪两块土地在一个水体中最接近。

Answer 1

我已经将BGL用于具有数百万个节点的图形，但是您可以使用的图形大小取决于您尝试运行的算法。您可以快速计算节点之间的距离。根据您的数据，有4种最短路径算法是最适用的：（单对点，对于所有点对，稀疏和密集图，...）。

至于社区检测，没有任何专门针对BGL的算法（但也许您在完成项目时可以贡献一个算法）。有几种算法可能有助于构建社区检测算法。max-flow/min-cut算法通常用于社区检测（如果两个节点之间可能存在大量流量，那么它们可能位于同一个社区中，如果没有多少流量，则最小切割可能代表社区之间的道路）。还有一些启发式命令来排列图的节点以减少bandwidth。构成“社区”的节点可能在这样的排序中彼此接近。

Answer 2

据我所知BGL没有任何算法专门为社区发现。

通过“孤岛”你的意思是断开的子？

此外，图形不具有“距离”的任何概念。

这种“社会距离”是，你将不得不定义的东西。一旦你完成了大部分工作就完成了。

有你链接到页面上列出的多种方法，其中大多数的只需要你定义有点像“距离”的度量，然后把你定义成算法。

@大卫Nehme

图表没有边缘的权重只有大约连通，他们没有距离的概念。如果你想谈论一个网络，那么你可以谈论距离。但是没有边权重的图没有任何距离，除非你想假设所有边的隐含边权重为1。但这只是将图形变成网络。

而且，他是在谈论两个不图之间的距离。为了对此进行建模，必须引入节点间距离的外部概念，与边缘距离分开。