数据分析之图算法: 基于Spark和Neo4j

114

｜

第

6

章

Louvain

模块度算法诞生于

2008

年，是最快的一种基于模块度的算法。除发现社团外，它

还揭示了不同尺度上的社团层级结构，这对于理解不同粒度的网络结构非常有用。

通过将簇内连接的密度与平均值或随机样本进行比较，

Louvain

模块度算法可以量化评估

将某个节点分配给某个群组是否恰当。这种度量社团分配的指标称为

模块度

。

6.6.1

　通过模块度进行基于质量的分组

模块度是一种发现社团的技术，它将图分割为更粗粒度的模块（或簇），然后度量本次分

组的强度。与仅仅查看簇内连接的集中度不同，该方法将簇内关系密度与簇间关系密度进

行比较。模块度是度量这些分组质量的指标。

模块度算法首先实现社团的局部优化，然后再实现全局优化，使用多组迭代来测试不同分

组方法并且增加粗粒度。这种策略可以识别社团的层级结构，比较全面地认识整体结构。

然而，所有模块度算法都存在以下两个缺点：

•

它们将较小的社团合并成较大的社团；

•

当多个分割选项出现相似的模块度时，可能会出现停滞，形成局部极点并阻碍进一步

处理。

更多相关信息，请参阅

Benjamin H. Good

、

Yves-Alexandre de Montjoye

和

Aaron Clauset

的

论文“

Performance of Modularity Maximization in Practical Contexts

”。

Louvain

模块度算法首先对所有节点的模块度进行局部优化，找到若干小社团；然后将每

个小社团分组到更大的联合集团，之后重复第一步，直到达到全局最优为止。 ...