提高图表的图书馆：是否有一个整洁的算法进BGL为社会检测?

Question

任何人使用BGL大生产服务器？

• 有多少节点网络组成的呢？
• 你怎么处理 社会检测
• 不BGL有任何酷的方式来检测社区？
• 有时候两个社区可能会被连接在一起由一个或两个边缘，但这些边缘是不可靠的和可以消失。有时候，没有边缘。

有人能说简单地谈谈如何解决这个问题。请打开我的头脑和激励着我。

迄今为止我设法工作，如果两个节点上的一个小岛(社区) 在一个以免昂贵的方式，但现在我需要的工作，这两个节点上独立的岛屿是最接近。我们只能做最小的使用不可靠的地理数据。

如果我们形象地把它比作一个大陆和岛和把它拿出来的社会距离上下文。我想要找出这两位土地是最近的一起跨越的水体。

Answer 1

我已经使用的BGL用图表以百万计的节点，但是大小的图表可以使用取决于什么样的算法，你正在尝试运行。你可以快速的计算之间的距离的节点。有4个最短路径算法是最适用取决于你的数据：(单对点，对于所有对点，稀疏和密集的图表,...).

作为社会检测，没有任何算法内置入BGL专门为，(但是，也许你可以贡献一一个当你完成了你的项目)。有一些算法，可能有助于建立一个社区的探测的算法。的 最大流/分钟切 算法通常用在社会检测(如果有大量的流动可能在两个节点之间，那么它们很可能在相同的社会，如果没有多少流动，然后分钟切的是，可能代表之间的道路的社区).还有启发式以节点的曲线图，以减少 带宽.节制了"社区"可能相互接近这样一个排序。

Answer 2

据我所知BGL没有任何具体算法为社会检测。

通过"岛屿"你的意思是一个断开子?

此外，图表中没有任何概念的距离.

这种'社会的距离'是什么，你都要有定义。一旦你已经做了很大一部分工作已经完成。

有许多方法上列出的网页链接到，大多数的这些只需要你定义的东西就像一个距离指标，然后插入您的定义纳入的算法。

@David Nehme

图无边缘权只有连通，他们有没有概念的距离。如果你想谈谈一个网络，然后您可以谈谈的距离。但一个图与没有边缘权不具有任何距离，除非你想要承担隐含的边缘重量的1为所有的边缘。但这真的只是把图形成一个网络。

此外，他谈论之间的距离两个断开图表。模型这个，你必须引进外部的概念，为节点之间的距离、独立的从边缘的距离。