Overlapping Community Detection by Local Community Expansion
16
Citation
28
Reference
20
Related Paper
Citation Trend
Abstract:
Community structure is the key aspect of complex network analysis and it has important practical significance. While in real networks, some nodes may belong to multiple communities, so overlapping community detection attracts more and more attention. But most of the existing overlapping community detection algorithms increase the time complexity in some extent. In order to detect overlapping community structures in complex network more effectively, we propose a novel overlapping community detection method by local community expansion called OCDLCE. The proposed algorithm firstly partitions the network into small local communities using the local structural information, and then merges these communities to the final overlapping community structures. We present the concept of community connectivity as the criterion of community combination in the second stage of the proposed algorithm. The experimental results on both synthetic and real networks demonstrate that our algorithm improves the community detection performance, and at the same time, its time efficiency is better than the state-of-the-art methods.Keywords:
Local Community
Community structure detection has great importance in finding the relationships of elements in complex networks. This paper presents a method of simultaneously taking into account the weak community structure definition and community subgraph density, based on the greedy strategy for community expansion. The results are compared with several previous methods on artificial networks and real world networks. And experimental results verify the feasibility and effectiveness of our approach.
Network Structure
Cite
Citations (0)
Modularity
Scope (computer science)
Clique percolation method
Local Community
Cite
Citations (0)
Communities,especial overlapping communities in complex networks are significant in many fields such as information spreading and recommending,public opinion controlling,and commercial marketing.Overlapping communities detecting is attracting increasing attentions since some nodes may naturally belong to several groups in real-world networks.This paper proposed an overlapping community detecting algorithm based on two phase strategies:initial community extracting and community merging.In extracting phase,a node with maximal degree and its tight neighbors are selected as an initial community,and nodes tight with the community are also included.In merging phase,two communities are merged if the modularity gets larger after merging.Three real-world complex networks including a large-scale one were used to evaluate the algorithm.Experimental results demonstrate that the proposed algorithm is efficient for detecting overlapping communities in complex networks.
Modularity
Clique percolation method
Cite
Citations (3)
The identification of communities is significant for the understanding of network structures and functions. Since some nodes naturally belong to several communities, the study of overlapping community structures has attracted increasing attention recently, and many algorithms have been designed to detect overlapping communities. We propose a new algorithm. The main idea is first to find the core of a community by detecting maximal cliques and then merging some tight community cores to form the community. Experimental results on two real networks demonstrate that the present algorithm is more accurate for detecting overlapping community structures, compared with some well-known results and methods.
Identification
Clique percolation method
Cite
Citations (20)
Clique
Cite
Citations (8)
Community detection plays an essential role in understanding network topology and mining underlying information. A bipartite network is a complex network with more important authenticity and applicability than a one-mode network in the real world. There are many communities in the network that present natural overlapping structures in the real world. However, most of the research focuses on detecting non-overlapping community structures in the bipartite network, and the resolution of the existing evaluation function for the community structure’s merits are limited. So, we propose a novel function for community detection and evaluation of the bipartite network, called community density D. And based on community density, a bipartite network community detection algorithm DSNE (Density Sub-community Node-pair Extraction) is proposed, which is effective for overlapping community detection from a micro point of view. The experiments based on artificially-generated networks and real-world networks show that the DSNE algorithm is superior to some existing excellent algorithms; in comparison, the community density (D) is better than the bipartite network’s modularity.
Modularity
Clique percolation method
Cite
Citations (6)
Community detection is an important task with great practical value for understanding the structure and function of complex networks. However, in many social networks, a node may belong to more than one community. Thus, the detection of overlapping community is more significant. The local expansion algorithm using seeds to find overlapping communities is becoming increasingly popular, but how to choose suitable seeds and expand the local communities effectively is still a great challenge. In this paper, we propose a new overlapping community detection algorithm based on node-weighting (OCDNW). The main idea of the algorithm is to find a good seed and then greedily expand it based on an improved community quality metric. Finally it optimizes the community structure to ensure the quality of community partitioning. Experimental results on synthetic and real world networks prove that the proposed algorithm can detect overlapping communities successfully and outperform other state-of-the-art methods.
Value (mathematics)
Cite
Citations (5)
Network communities represent mesoscopic structure for understanding the organization of real-world networks, where nodes often belong to multiple communities and form overlapping community structure in the network. Due to non-triviality in finding the exact boundary of such overlapping communities, this problem has become challenging, and therefore huge effort has been devoted to detect overlapping communities from the network.
Triviality
Disjoint sets
Network Structure
Cite
Citations (25)
Social networks are large-scale and dynamic and have brought great challenges to traditional community detection algorithms. Local community detection algorithms are good solutions to these problems which obtain a local community by expanding from a seed. A new definition of community is given via combining node structural similarities and traditional definitions of community,and a new definition of local modularity is proposed by introducing a scale parameter. Furthermore,A multi-scale local community detection algorithm is proposed based on the local modularity and is applied to local overlapping community detection. The node structural similarity has a better effect,and is chosen and applied to this algorithm. The comparison experiments with other local community detection algorithms in real networks show that the proposed algorithm is effective.
Modularity
Similarity (geometry)
Local Community
Clique percolation method
Cite
Citations (1)
In this paper, a simple but efficient method of overlapping community detection is presented using local community gravitation in social networks. Given a high-quality, non-overlapping partition generated by existing methods, this proposed method identifies the overlapping nodes from their surrounding partitioned communities according to their local community gravitation, with low computational complexity. Our experiments on synthetic networks and real-world networks demonstrate that the proposed algorithm is better than other algorithms in terms of the general quality.
Cite
Citations (1)