title: Spectral characterization of hierarchical network modularity and limits of modularity detection.
abstract: Many real world networks are reported to have hierarchically modular organization. However, there exists no algorithm-independent metric to characterize hierarchical modularity in a complex system. The main results of the paper are a set of methods to address this problem. First, classical results from random matrix theory are used to derive the spectrum of a typical stochastic block model hierarchical modular network form. Second, it is shown that hierarchical modularity can be fingerprinted using the spectrum of its largest eigenvalues and gaps between clusters of closely spaced eigenvalues that are well separated from the bulk distribution of eigenvalues around the origin. Third, some well-known results on fingerprinting non-hierarchical modularity in networks automatically follow as special cases, threreby unifying these previously fragmented results. Finally, using these spectral results, it is found that the limits of detection of modularity can be empirically established by studying the mean values of the largest eigenvalues and the limits of the bulk distribution of eigenvalues for an ensemble of networks. It is shown that even when modularity and hierarchical modularity are present in a weak form in the network, they are impossible to detect, because some of the leading eigenvalues fall within the bulk distribution. This provides a threshold for the detection of modularity. Eigenvalue distributions of some technological, social, and biological networks are studied, and the implications of detecting hierarchical modularity in real world networks are discussed.
authors: School of Physics, University of Sydney, Sydney, New South Wales, Australia. sarkar@physics.usyd.edu.au
authors: Somwrita
authors: S
authors: Sarkar
authors: James A
authors: JA
authors: Henderson
authors: Peter A
authors: PA
authors: Robinson
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008962:Models, Theoretical
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Nov;80(5 Pt 2):056114
references: 20365050
references: Proc Biol Sci. 2004 Dec 7;271 Suppl 6:S477-81
references: 15801609
references: Proc Natl Acad Sci U S A. 2002 Jun 11;99(12):7821-6
references: 12060727
references: PLoS Comput Biol. 2012;8(2):e1002391
references: 22383870
references: PLoS Biol. 2008 Jul 1;6(7):e159
references: 18597554
references: Nat Rev Neurosci. 2009 Mar;10(3):186-98
references: 19190637
references: Science. 2002 Aug 30;297(5586):1551-5
references: 12202830
references: Proc Biol Sci. 2003 Nov 7;270 Suppl 2:S186-8
references: 14667378
references: Proc Natl Acad Sci U S A. 2007 Jan 2;104(1):36-41
references: 17190818
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Apr;83(4 Pt 2):046114
references: 21599247
references: Phys Rev Lett. 2009 Sep 4;103(10):108104
references: 19792345
references: Front Neuroinform. 2009 Oct 30;3:37
references: 19949480
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Aug;64(2 Pt 2):026704
references: 11497741
references: Front Neurosci. 2010 Dec 08;4:200
references: 21151783
references: Phys Rev Lett. 2012 May 4;108(18):188701
references: 22681123