一种新的社区／动态社区优化方法

摘要：

社区结构作为复杂网络的重要拓扑特性之一，成为当前的研究热点。本文提出了一种基于边排序和模块度优化的社区发现方法。该方法首先对初始的静态网络进行稀疏化，然后在稀疏化后的网络上依据边的重要程度对边进行排序，给出了一种模块度最大化、快速边合并的社区发现方法（Fast rank‐based community detection ，FRCD）。在初始网络社区划分结果的基础上，将该方法推广到动态、实时社区划分上，给出了一种快速、鲁棒的动态社区划分方法（Incremental dynamic community detec‐tion ，IDCD）。理论分析表明FRCD相对于边具有线性时间复杂度。在实际和人工网络上的实验结果均表明，本文提出的方法无论在静态网络社区划分还是在动态网络社区追踪上都优于已有方法。

关键词：社区发现、模块度、边排序、动态性

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金61473030，61370129资助项目；北京市自然科学基金4112046资助项目；北京市科委Z131110002813118资助项目；中央高校基本科研业务费专项基金K15JB00070，2014JBM031资助项目；北大方正集团有限公司数字出版技术国家重点实验室开放课题资助项目。

在线出版日期：2016-01-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1215-1224