title: Constant communities in complex networks.
abstract: Identifying community structure is a fundamental problem in network analysis. Most community detection algorithms are based on optimizing a combinatorial parameter, for example modularity. This optimization is generally NP-hard, thus merely changing the vertex order can alter their assignments to the community. However, there has been less study on how vertex ordering influences the results of the community detection algorithms. Here we identify and study the properties of invariant groups of vertices (constant communities) whose assignment to communities are, quite remarkably, not affected by vertex ordering. The percentage of constant communities can vary across different applications and based on empirical results we propose metrics to evaluate these communities. Using constant communities as a pre-processing step, one can significantly reduce the variation of the results. Finally, we present a case study on phoneme network and illustrate that constant communities, quite strikingly, form the core functional units of the larger communities.
authors: Dept. of Computer Science & Engg., Indian Institute of Technology, Kharagpur, India - 721302.
authors: Tanmoy
authors: T
authors: Chakraborty
authors: Sriram
authors: S
authors: Srinivasan
authors: Niloy
authors: N
authors: Ganguly
authors: Sanjukta
authors: S
authors: Bhowmick
authors: Animesh
authors: A
authors: Mukherjee
references: Proc Natl Acad Sci U S A. 2002 Jun 11;99(12):7821-6
references: 12060727
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Dec;70(6 Pt 2):066111
references: 15697438
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Aug;72(2 Pt 2):027104
references: 16196754
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Feb;69(2 Pt 2):026113
references: 14995526
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Apr;81(4 Pt 2):046106
references: 20481785
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Jul;80(1 Pt 2):016118
references: 19658785
references: Sci Rep. 2012;2:336
references: 22468223
references: Proc Natl Acad Sci U S A. 2010 Jul 20;107(29):12755-60
references: 20615936
references: Nature. 1998 Jun 4;393(6684):440-2
references: 9623998
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Nov;80(5 Pt 2):056117
references: 20365053
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Nov;72(5 Pt 2):056135
references: 16383716
references: Proc Natl Acad Sci U S A. 2008 Jan 29;105(4):1118-23
references: 18216267
references: Phys Biol. 2011 Oct;8(5):055010
references: 21832797
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Jun;81(6 Pt 2):066118
references: 20866489
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2003 Dec;68(6 Pt 2):065103
references: 14754250