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

Novel Community/Dynamic Community Optimization Algorithm

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

Community structure is one of the most important topological characteristics in the complex network,being a hot research area in different fields.A novel community detection algorithm is proposed based on edges rank and modularity optimization.Local graph is sparsificated and edges are ranked according to the similarity.Therefore,a method called the fast rank-based community detection（FRCD）by maximizing modularity and fast mergement of edges is achieved.Meanwhile the method is also extended to dynamic and real-time community detection on the basis of initial community structure,and a fast and robust dynamic community detection algorithm called the incremental dynamic community detection（IDCD）is presented.Theoretical analysis exhibit that FRCD has linear complexity for network edges.Experimental results in real-world and artificial networks demonstrate the high accuracy and good performance of the algorithm on static community detection and tracking dynamic structure of networks.