杨春明 王玉金

(西南科技大学计算机科学与技术学院 四川绵阳 621010)

基于模块度优化的加权复杂网络社团发现算法分析

杨春明 王玉金

(西南科技大学计算机科学与技术学院 四川绵阳 621010)

社团结构是复杂网络的一种重要拓扑结构。针对加权复杂网络中的社团发现问题，在8个不同领域、不同规模的真实数据集上，从模块度、强/弱社团、聚集系数3个评估指标分析了基于模块度优化的GN算法、FN算法、CNM算法和BGLL算法在加权复杂网络社团发现的效果。研究结果表明，上述3个评估指标在加权复杂网络上的划分结果不能始终保持一致，基于优化模块度的算法更倾向于找到复杂网络中比较粗糙的社团结构，而不是精准的社团结构，其算法的泛化能力有待加强。

加权复杂网络 社团发现 模块度 聚集系数

现实中大量的复杂系统通常可用网络来描述，如互联网络、社交网络、科学家合作网络、病毒传播网络等，这些抽象出来的复杂网络通常具有小世界[1]及无标度特性[2]。复杂网络的一个重要结构特征是网络的社团(community)结构[3]，又称为群(group)或簇(cluster)，社团内部节点连接紧密，社团间连接相对稀疏，社团内部节点都具有比较相近的属性[4]。

复杂网络的社团发现研究主要用于理解网络的拓扑结构、挖掘网络的潜在意义及预测网络行为等。对无权复杂网络社团发现，主要有谱聚类方法[5]、KL(Kernighan-Lin)算法[6]、GN(Girvon-Newman)算法、FN算法[7]、CNM算法[8]、BGLL算法[9]等。

相对与无权网络，有权网络中包含了更多的网络信息，更能反映实际情况。……