完整和加权网络中的社区检测

Question

我确实有一个完整的网络图，每个顶点都相互连接，它们只在不同的权重形式上有所不同。一个示例网络将是：一个贸易网络，其中每个国家都以某种方式相互连接，并且仅以不同的交易量形式存在差异。

现在的问题是我如何能够以这种形式的网络执行社区检测。通常的嫌疑人（算法）只能在未加权或不完整的网络中执行。主要问题是测地线无处不在。

两个选项走进了我的脑海：

1. 剪切网络成小块，通过一定的“重量阈值水平”
2. 或者使用聚类算法把整个网络切断他们成块模型。但我认为“测地术语不会有差异”这个问题仍将存在。

Answer 1

提出了几种方法。

在Fast unfolding of communities in large networks（Blondel等人，2008）中提出了一种简单而有效的方法。它支持加权网络。摘要摘要如下：

我们提出一种简单的方法来提取大型网络的社区结构。我们的方法是基于模块化 优化的启发式方法。它被证明在计算时间方面优于所有其他已知社区的检测方法。此外，通过所谓的 模块化测量，所检测社区的质量 非常好。

从纸张报价：

我们现在介绍一下我们的算法，发现大型网络的高度模块化分区 在很短的时间，并且展现一个完整的 层次社会结构的网络，从而给 访问不同的社区检测解决方案。

所以它应该适用于完整的图形，但你应该更好地检查它。

C++实现可用here（现在维护here）。

您的其他想法 - 使用权重阈值 - 可能被证明是一个很好的预处理步骤，特别是对于不会分割完整图的算法。我相信最好将它设置为权重的某个百分位数（例如中位数）。