Boost Graph Library:BGL内置了一个用于社区检测的简洁算法吗？

Question

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

• 您的网络包含多少个节点？
• 你如何处理社区检测
• BGL有没有很酷的方法来检测社区？
• 有时两个社区可能通过一条或两条边连接在一起,但这些边缘不可靠并且可能逐渐消失.有时根本没有边缘.

有人可以简单地谈谈如何解决这个问题.请敞开心扉,激励我.

到目前为止,我已经设法解决了两个节点是否在岛上(在社区中)以最昂贵的方式,但现在我需要弄清楚不同岛上的哪两个节点彼此最接近.我们只能极少使用不可靠的地理数据.

如果我们比喻它与大陆和岛屿比较,并把它从社会距离背景中拿出来.我想弄清楚哪两块土地最接近水体.

Answer 1

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

至于社区检测,BGL中没有专门为此设置的任何算法(但也许你可以在完成项目时贡献一个).有一些算法可能有助于构建社区检测算法.的最大流/最小割算法通常在社区检测中使用(如果有两个节点之间的可能的大量流的,则它们可能是在相同的小区,如果没有太多的流量,则分 - 切割可能代表社区之间的道路).还有启发式方法来命令图的节点以减少带宽.构成"社区"的节点可能在这样的排序中彼此接近.