Correlation-Based Community Detection

Abstract

Mining community structures from the complex network is an important problem across a variety of fields. Many existing community detection methods detect communities through optimizing a community evaluation function. However, most of these functions even have high values on random graphs and may fail to detect small communities in the large-scale network (the so-called resolution limit problem). In this paper, we introduce two novel node-centric community evaluation functions by connecting correlation analysis with community detection. We will further show that the correlation analysis can provide a novel theoretical framework which unifies some existing evaluation functions in the context of a correlation-based optimization problem. In this framework, we can mitigate the resolution limit problem and eliminate the influence of random fluctuations by selecting the right correlation function. Furthermore, we introduce three key properties used in mining association rule into the context of community detection to help us choose the appropriate correlation function. Based on our introduced correlation functions, we propose a community detection algorithm called CBCD. Our proposed algorithm outperforms existing state-of-the-art algorithms on both synthetic benchmark networks and real-world networks.

References in corpus (25)

• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Fast algorithm for detecting community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Mixing patterns in networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Detecting the overlapping and hierarchical community structure of complex networks
• Predicting Missing Links via Local Information
• Higher-order organization of complex networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Limits of modularity maximization in community detection
• Normalized Mutual Information to evaluate overlapping community finding algorithms
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• All scale-free networks are sparse
• Community detection for correlation matrices
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Covariance, correlation matrix and the multi-scale community structure of networks
• A testing based extraction algorithm for identifying significant communities in networks