郑文萍 车晨浩 钱宇华 王 杰

1(山西大学大数据科学与产业研究院 太原 030006) 2(山西大学计算机与信息技术学院 太原 030006) 3(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006) (wpzheng@sxu.edu.cn)

复杂网络分析在社会学、传染病学和生物学等领域有着广泛的应用[1-3].通常可以用图G=(V,E)表示一个复杂网络,其中V表示网络中个体的集合,E表示个体间联系的集合.社区结构(community structure)是复杂网络的重要特征之一,即一个网络可以分成若干社区,社区内节点之间连接相对紧密,社区间节点连接相对稀疏.有效的社区发现算法可以发现社会网络中的社区结构、生物网络中的蛋白质功能模块等,有助于深入研究各种类型复杂网络的功能模块及其演化特征,对准确地理解并分析复杂系统的拓扑结构及动力学特性具有十分重要的理论意义和应用价值[4-5].

目前复杂网络中的社区发现方法主要有基于图划分的聚类算法[6]、基于谱分析的聚类算法[7]、基于层次的聚类算法[8]和基于密度的聚类算法[9-10]等.Newman提出了一种基于贪心策略的快速社区发现算法(fast modularity maximization, FMM)[11],以最优化模块性为目标函数进行社区合并和更新.Blondel等人提出了BGLL算法[12],随机选择一个节点作为初始社区,迭代选择使当前社区模块性增长最大节点加入当前社区完成社区扩展过程.由于现实网络包含大量的小规模社区,网络社区内部连接数不一定比社区之间的连接数多,导致模块性不能较好地度量社区划分质量.Bai等人[13]基于……