面向大规模应用层拓扑的社团发现技术

摘要

社团发现是复杂网络研究领域里一个极具挑战性的方向。特别地,对于现实世界中许多规模巨大的应用层拓扑,一些社团发现算法因为计算复杂度过高而不适用。另一些社团发现算法的实际性能还有待评估。为此,提出了可用于衡量社团发现算法实际应用价值的三个指标:(1)可扩展性,衡量算法能处理的应用层拓扑的规模;(2)准确度,衡量社团划分结果好坏;(3)敏感度,衡量社团划分结果的一致程度。在7个大规模的现实世界应用层拓扑图上,对三个针对大规模网络的社团发现算法(CNM算法、Wakita算法和Louvain算法)进行了比较分析。实验结果表明,Louvain算法在可扩展性上最优且所得划分结果准确度最高,CNM算法在敏感度上表现最好。

关键词