Finding and Testing Network Communities by Lumped Markov Chains
Open Access
- 3 November 2011
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 6 (11) , e27028
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 that is based on a quality threshold. By means of a lumped Markov chain model of a random walker, a quality measure called “persistence probability” is associated to a cluster, which is then defined as an “ -community” if such a probability is not smaller than . Consistently, a partition composed of -communities is an “ -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 -level allows one to immediately select the -partition with the finest decomposition. Simultaneously, the persistence probabilities quantify the quality of each single community. Given its ability in individually assessing each single cluster, this approach can also disclose single well-defined communities even in networks that overall do not possess a definite clusterized structure.Keywords
All Related Versions
This publication has 54 references indexed in Scilit:
- Finding Statistically Significant Communities in NetworksPLOS ONE, 2011
- Community Landscapes: An Integrative Approach to Determine Overlapping Network Module Hierarchy, Identify Key Nodes and Predict Network DynamicsPLOS ONE, 2010
- Stability of graph communities across time scalesProceedings of the National Academy of Sciences, 2010
- Optimal partition and effective dynamics of complex networksProceedings of the National Academy of Sciences, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences, 2008
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Computing Communities in Large Networks Using Random Walks2005