title: 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 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.
authors.affiliation: Department of Electronics and Information, Politecnico di Milano, Milano, Italy. carlo.piccardi@polimi.it
authors.forename: Carlo
authors.initials: C
authors.lastname: Piccardi
mesh_terms: D016000:Cluster Analysis; D008390:Markov Chains; D011336:Probability
references.citation: Proc Natl Acad Sci U S A. 2008 Jun 10;105(23):7907-12
references.pmid: 18303119
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Sep;74(3 Pt 2):036104
references.pmid: 17025705
references.citation: Nature. 2003 Nov 20;426(6964):282-5
references.pmid: 14628050
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2003 Jul;68(1 Pt 2):015101
references.pmid: 12935184
references.citation: Proc Natl Acad Sci U S A. 2004 Mar 2;101(9):2658-63
references.pmid: 14981240
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2003 Jun;67(6 Pt 1):061901
references.pmid: 16241255
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Feb;69(2 Pt 2):026113
references.pmid: 14995526
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Sep;76(3 Pt 2):036102
references.pmid: 17930301
references.citation: Proc Natl Acad Sci U S A. 2007 Jan 2;104(1):36-41
references.pmid: 17190818
references.citation: BMC Bioinformatics. 2006 Jan 06;7:2
references.pmid: 16398927
references.citation: Proc Natl Acad Sci U S A. 2008 Jan 29;105(4):1118-23
references.pmid: 18216267
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Aug;78(2 Pt 2):026121
references.pmid: 18850911
references.citation: PLoS One. 2010 Sep 02;5(9):
references.pmid: 20824084
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Jul;76(1 Pt 2):015102
references.pmid: 17677523
references.citation: Nature. 2001 Mar 8;410(6825):268-76
references.pmid: 11258382
references.citation: Proc Natl Acad Sci U S A. 2010 Jul 20;107(29):12755-60
references.pmid: 20615936
references.citation: Chaos. 2009 Sep;19(3):033119
references.pmid: 19791999
references.citation: Phys Rev Lett. 2010 Nov 5;105(19):198701
references.pmid: 21231202
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Dec;82(6 Pt 2):066106
references.pmid: 21230704
references.citation: Nature. 2005 Jun 9;435(7043):814-8
references.pmid: 15944704
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2011 May;83(5 Pt 2):056105
references.pmid: 21728603
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Oct;78(4 Pt 2):046110
references.pmid: 18999496
references.citation: Proc Natl Acad Sci U S A. 2006 Jun 6;103(23):8577-82
references.pmid: 16723398
references.citation: PLoS One. 2011 Apr 29;6(4):e18961
references.pmid: 21559480
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Jul;80(1 Pt 2):016118
references.pmid: 19658785
references.citation: Phys Rev Lett. 2004 Nov 19;93(21):218701
references.pmid: 15601068
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Jan;81(1 Pt 2):016103
references.pmid: 20365428