基于局部结构特征的重叠社区挖掘研究进展  

Research progress of overlapping community detection methods based on local structure

作　　者：张泽华[1] 段力畑 段富[1] 张楠[2] 

机构地区：[1]太原理工大学计算机科学与技术学院,太原030024 [2]烟台大学计算机与控制工程学院,烟台264005

出　　处：《南京大学学报（自然科学版）》2017年第3期537-548,共12页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(61503273;61403329);太原理工大学青年创新团队项目(2014TD056)

摘　　要：社区挖掘是复杂网络研究的核心内容之一.基于局部结构建模的重叠社区发现方法由于可利用局部先验知识,具有适应网络动态环境,建模速度快,可多角度呈现局部结构特征等优点,当前已成为大规模网络发现研究的前沿热点.从理论发展沿革与现实应用的视角,介绍重叠社区发现研究近来的相关研究进展.通过分析重叠社区发现研究存在的关键问题,给出基于局部结构特征的重叠社区挖掘研究框架,并对几类典型的重叠社区发现方法展开分析比较.然后进一步阐述和探讨如何面对现实超大规模网络、多态异构网络、不确定性数据、动态演化结构等方面面临的巨大挑战.最后总结并展望了基于局部结构的重叠社区发现研究的未来方向和前景.Community mining is one of the core contents of complex network research. Compared to global optimization methods, local structure based community detection models usually have the advantage of using local prior knowledge,and adapt to the dynamic network environment with rapid modeling capabilities in multi-views and so on. Nowadays such methods have become the current hot research on the large scale network. From the perspective of theoretical evolution and practical application, the paper introduces the recent research progress of overlapping community detection. Based on the analysis of the key problems in the research, this study presents the research framework of overlapping community mining based on local structure, and then compares and analyzes some typical overlapping community discovery methods, named as clique percolation methods, local expansion methods, link communities optimization methods, label propagation algorithm, community link structure based methods, which depend on the community measurements with local optimization strategy. The clique percolation can found local communities in the dense network with highly overlapping communities. And the local expansion methods independent of the global network effectively reveals the structure of local communities and can show the hierarchical and overlapping features in local. The link community optimization with natural overlaps on links can effectively deal with overlapping networks, while Label Propagation Algorithms （LPA）has good performance in computational complexity, usually suitable for community detection in large scale networks. Link prediction based methods be closely linked with structural similarity on the target network. Moreover, we discuss the issues how to face the enormous challenges of the large scale network with massive data, polymorphic heterogeneous network, complex network structure with uncertainty, and dynamic evolution and so on. Finally, the paper summarizes the future work about overlapping community detection.

关 键 词：社区挖掘 重叠社区 局部结构 复杂网络 

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