基于局部紧耦合结构的模块性优化社区检测方法

Modularity optimization method for community detection based on local close-knit structures

利用局部紧耦合结构提升社区检测的模块性优化质量.首先,定义了4类边缘紧耦合结构,并提出了一种具有线性复杂度的边缘紧耦合结构挖掘算法.其次,分别选择k-clique,k-clan,k-plex结构作为核心紧耦合结构,并以长结构优先和短结构优先2种策略将边缘与核心紧耦合结构合并.然后,将合并后的局部紧耦合结构融入模块性优化过程,提出了一种NFN算法.该算法将每个局部紧耦合结构初始化为独立社区,不断凝聚模块性增量最大的2个社区,直至找到预定义数量的社区.6个真实数据集上针对外部指标和内部指标的实验结果均表明,相比于传统的FN算法,NFN算法能发现更高质量的社区.在参数设置方面,长结构优先策略优于短结构优先策略,且采用k-clique结构作为核心紧耦合结构优于采用其他结构.因此,长结构优先策略结合k-clique成为NFN算法的最佳参数组合.

Local close-knit structures are used to improve the quality of modularity optimization in community detection.First,four kinds of periphery close-knit structures are defined,and an algorithm for mining periphery close-knit structures with linear complexity is presented.By selecting k-clique,k-clan,and k-plex as core close-knit structures,two strategies including long-structure-first and short-structure-first are employed for merging periphery with core structures.Thus,a novel algorithm named new Fast Newman （NFN）is proposed by incorporating merged local structures into the modularity op-timization process.In particular,each local close-knit structure is initialized as an isolated community, and then two communities are merged to maximize the increase of modularity.This process is repeated until the pre-defined number of communities is discovered.The experimental results in terms of both internal and external validities on six real-world social networks demonstrate that compared with the traditional Fast Newman（FN）algorithm,the NFN algorithm can find communities in better quality. Moreover,the long-structure-first strategy outperforms the short-structure-first strategy,and employing k-clique as core close-knit structures is better than other structures.Therefore,the long-structure-first strategy with k-clique is the best parameter setting for the NFN algorithm.