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

Question

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

现在的问题是我如何在这种形式的网络中执行社区检测。通常的嫌疑人(算法)只能在未加权或不完整的网络中表现良好。主要问题是测地线到处都是相同的。

我想到了两个选择:

1. 通过在特定的“权重阈值级别”将网络切割成更小的部分
2. 或者使用层次聚类算法将整个网络变成 block 模型。但我认为“测地线术语没有变化”的问题仍然存在。

Answer 1

提出了几种方法。

Fast unfolding of communities in large networks中提出了一种简单而有效的方法。 (布隆德尔等人，2008)。它支持加权网络。摘自摘要:

We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity.

引自论文:

We now introduce our algorithm that finds high modularity partitions of large networks in short time and that unfolds a complete hierarchical community structure for the network, thereby giving access to different resolutions of community detection.

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

C++ 实现可用 here (现已维护here)。

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