Finding and testing network communities by lumped Markov chains

Abstract

Identifying communities (or clusters), namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. Yet, there is a lack of formal criteria for defining communities and for testing their significance. We propose a sharp definition which is based on a significance threshold. By means of a lumped Markov chain model of a random walker, a quality measure called "persistence probability" is associated to a cluster. Then the cluster is defined as an "$\alpha$-community" if such a probability is not smaller than $\alpha$. Consistently, a partition composed of $\alpha$-communities is an "$\alpha$-partition". These definitions turn out to be very effective for finding and testing communities. If a set of candidate partitions is available, setting the desired $\alpha$-level allows one to immediately select the $\alpha$-partition with the finest decomposition. Simultaneously, the persistence probabilities quantify the significance of each single community. Given its ability in individually assessing the quality of each cluster, this approach can also disclose single well-defined communities even in networks which overall do not possess a definite clusterized structure.

References in corpus (16)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• On the Topological Properties of the World Trade Web: A Weighted Network Analysis
• When are networks truly modular?
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Partitioning and modularity of graphs with arbitrary degree distribution
• Community structure of complex software systems: Analysis and applications

Cited by in corpus (15)

• Random walks and diffusion on networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
• Rich-cores in networks
• Complexity, Centralization, and Fragility in Economic Networks
• Synwalk -- Community Detection via Random Walk Modelling
• Multi-attribute community detection in International Trade Network
• An integrative dynamical perspective for graph theory and the study of complex networks
• Generalized Markov stability of network communities
• Communities as Well Separated Subgraphs With Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
• Entrograms and coarse graining of dynamics on complex networks
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Metrics for network comparison using egonet feature distribution
• On Finding the Community with Maximum Persistence Probability
• An egonet-based approach to effective weighted network comparison