Spectral graph analysis of modularity and assortativity
Authors:
- P. Van MieghemPMP. Van Mieghem
- X. GeXGX. Ge
- P. SchummPSP. Schumm
- S. TrajanovskiSTS. Trajanovski
- H. WangHWH. Wang
- 16 November 2010
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 82 (5) , 056113
Abstract
Expressions and bounds for Newman's modularity are presented. These results reveal conditions for or properties of the maximum modularity of a network. The influence of the spectrum of the modularity matrix on the maximum modularity is discussed. The second part of the paper investigates how the maximum modularity, the number of clusters, and the hop count of the shortest paths vary when the assortativity of the graph is changed via degree-preserving rewiring. Via simulations, we show that the maximum modularity increases, the number of clusters decreases, and the average hop count and the effective graph resistance increase with increasing assortativity.Keywords
This publication has 27 references indexed in Scilit:
- Community Landscapes: An Integrative Approach to Determine Overlapping Network Module Hierarchy, Identify Key Nodes and Predict Network DynamicsPLOS ONE, 2010
- Community detection in graphsPhysics Reports, 2010
- Epidemic spreading in weighted scale-free networks with community structureJournal of Statistical Mechanics: Theory and Experiment, 2009
- Cascades on correlated and modular random networksPhysical Review E, 2008
- Limited resolution in complex network community detection with Potts model approachThe European Physical Journal B, 2007
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Statistical mechanics of community detectionPhysical Review E, 2006
- Comparing community structure identificationJournal of Statistical Mechanics: Theory and Experiment, 2005
- Modularity from fluctuations in random graphs and complex networksPhysical Review E, 2004
- Finding and evaluating community structure in networksPhysical Review E, 2004