社团结构迭代快速探测算法

作     者：李慧嘉 李爱华 李慧颖 LI Hui-Jia;LI Ai-Hua;LI Hui-Ying

作者机构：中央财经大学管理科学与工程学院北京100081 清华大学自动化系北京100084 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2017年第40卷第4期

页      面：970-984页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 0839[工学-网络空间安全] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(71401194 71401188 91324203 11131009) 中央财经大学"青年英才"培育支持项目(QYP1603)资助~~ 

主　　题：社团结构 动态系统 指标函数 线性复杂度 层次结构 社交网络 

摘      要：作为复杂网络研究的重要组成部分,社团结构分析对于理解和分析现实世界中各种社会、工程和生物等系统具有非常重要的意义.该文利用动态迭代技术,提出了一种新型的社团探测技术,能够准确而快速地识别网络中的社团结构.首先引入一种动态系统,可以使社团归属从随机状态逐步收敛到最优划分,进一步利用严格的数学分析给出了社团归属在离散时间内收敛到最优的条件.该文创新性地提出了划分指标函数的一般化形式,通过选择不同的参数,可以引申到几乎所有著名的指标函数.为了使动态系统不需要任何参数选择即可完成向最优社团的收敛,文中设计了一种新颖的图生成模型,使得算法能在无参数的情况下方便高效的运行.该算法具有较高的效率,计算复杂性分析显示算法需要的时间与稀疏网络节点的数量呈线性关系.最后,文中将算法应用到人工网络和实际网络中,结果显示算法不仅具有极高的准确性,还能够高效地应用于大规模现实网络的分析和计算中.