利用堆数据结构实现邻域重叠社团结构挖掘  

Finding Overlapping Community in Network by Using Modularity and Partition Density

作　　者：任成磊[1] 韩定定[1] 蒲鹏[1] 张嘉诚[1] 

机构地区：[1]华东师范大学信息科学技术学院,上海200241

出　　处：《复杂系统与复杂性科学》2016年第1期102-106,110,共6页Complex Systems and Complexity Science

摘　　要：基于当前复杂网络中社团划分算法普遍存在算法复杂度过高以及重叠节点挖掘不准确的局限性,提出了一种高效、快速、准确的社团划分算法。基于贪婪算法,建立最大模块度矩阵,并采用堆数据结构,划分非邻域重叠社团。通过分析局部网络的连边情况,计算邻域社团的划分密度,以准确挖掘社团间的重叠节点。新算法经过仿真分析和实证研究表明,算法复杂度降到近线性。The algorithms of detecting community in complex networks now have lots of disadvantages such as high complexity and ignorance of accurate overlapping nodes.This paper proposes a highly efficient,rapid and accurate community detection algorithm.Based on greedy algorithm,the community is divided by establishing the modularity matrix and adopting the data structure.Considering the edges between local communities,the overlapping community structure is accurately dug by computing the partition density.We evaluate our methods using both synthetic benchmarks and real-world networks,demonstrating the effectiveness of our approach.Our method runs in essentially linear time.

关 键 词：社团挖掘 邻域重叠 模块度 划分密度 时间复杂度 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]