基于局部优化的社区发现方法研究现状

Review on Community Detection Methods Based on Local Optimization

文章介绍了社交网络背景下社区的定义以及主要的社区划分评价指标;根据不同的局部优化策略,将基于局部优化的社区发现方法分为局部扩展优化、派系过滤、标签传播、局部边聚类优化4类进行对比分析。基于局部扩展优化的社区发现方法能有效揭示局部社区结构,能提取有意义的局部聚类信息,如层次性和重叠性,对于大规模且动态变化的在线社交网络,在线社区的形成由于依赖局部的交互而表现出更强自治能力,因此局部扩展优化社区发现方法为在线社区挖掘提供了一个非常有效的途径。派系过滤方法由于其严格的社区结构定义能有效发现有结合力的局部社区以及高度重叠社区。标签传播算法在计算复杂度上有着明显的优势,适用于大规模社交网络中的社区挖掘。而基于局部边聚类使社区发现方法能很好地处理网络中的重叠节点。最后,文章对社区发现存在的一些问题和未来的研究做出展望:快速是社区发现方法的一个基本要求和发展趋势;精确性是社区发现技术的一个重要研究方向;综合的分析系统有助于为众多的社区发现技术和方法提供综合、客观的分析和评价;社交网络的动态演化特征给社区发现提出了更高要求和更多挑战。

An important mesoscopic feature of social networks is that community structure is often associated with organizational and functional characteristics of the underlying networks. Uncovering this community structure is an important research direction of social network analysis, it is very important for the analysis and understanding of structure attributes and group characteristics of social networks. Recently, considerable methods have been proposed for community detection. And these methods may fall into two categories： global-based and local-based. The global-based methods partition the whole network from the global perspective, requiring complete knowledge and information of the entire network. Currently, the global methods mainly include graph partitioning, hierarchical clustering, modularity optimization, model-based methods, and so on. Nevertheless, there are some limitations in global methods. Firstly, global-based methods usually divide the whole network into communities with the aid of prior knowledge such as the network size and community number, which are usually unavailable and unpredictable in advance for huge and evolving networks. Secondly, for the large-scale and dynamic social networks, it is computationally expensive to adopt existing global approaches. The last but not the least, global methods, for network structure itself, fail to detect overlapping attribute of community fundamentally in social network. Local methods identify communities based on the local structure information and local community metric in social network analysis. The basic idea behind local approaches is that communities are essentially local structures, involving the nodes belonging to the communities themselves plus at most an extended neighborhood of them. Such structures are widespread in online social networks. Compared with global methods, local ones show strong adaptability for current social networks with increasing large scale, complexity, and dynamic nature. What is more, they are efficient to reveal local community characteristics with local knowledge of a network. Many local-based methods have been proposed to detect community structures, such as Luo Wang Promislow （LWP）, Lancichinetti Fortunato Method（LFM）, Clique Percolation Method （CPM）, Label Propagation Algorithm （LPA）, and so on. This paper aims to give a survey on community detection methods based on local optimization. We first introduce community definitions in the context of social network, as well as evaluation indexes. Then we classify these methods and compare them to local optimization methods emphatically. The main local methods are classified into four categories according to diverse optimization approaches： local expansion optimizing（LEO）, clique percolation method （CPM）, label propagation algorithms （LPAs）, and local link clustering（LLC）. LEO methods usually detect community from a source vertex by using a local optimization of a certain metric. CPMs explore overlapping communities on a large scale, which define a community as union of all k-cliques. LPAs adopt label propagation technique which identifies the densely connected groups of nodes by forming a consensus on a unique label. LLC methods regard communities as groups of links rather than nodes and naturally incorporate overlap while revealing hierarchical organization. The survey performs special analysis on the performance and differences in these methods in terms of their methodological principies. It presents a comparative discussion of several popular methods. Comparative study shows that local expansion optimizing methods are efficient to detect hierarchical and overlapping local community structure. In online social network, the formation of community mainly rely on local interaction and show strong autonomy So local expanding methods are efficient for mining local online communities. Clique percolation methods can finding cohesive local communities and highly overlapping communities because of their strict community definition. Furthermore, label propagation algorithms show distinctive advantages in term of computational complexity, which are suitable for detecting communities in large-scale networks. In addition, local link clustering methods can naturally incorporate overlapping nodes while revealing hierarchical organization of social network. At last, the paper discusses some key problems and challenges in community detection, as well as potential future research directions.