Extracting spatial information from networks with low-order eigenvectors
- 8 March 2013
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 87 (3)
Abstract
We consider the problem of inferring meaningful spatial information in networks from incomplete information on the connection intensity between the nodes of the network. We consider two spatially distributed networks: a population migration flow network within the US, and a network of mobile phone calls between cities in Belgium. For both networks we use the eigenvectors of the Laplacian matrix constructed from the link intensities to obtain informative visualizations and capture natural geographical subdivisions. We observe that some low-order eigenvectors localize very well and seem to reveal small geographically cohesive regions that match remarkably well with political and administrative boundaries. We discuss possible explanations for this observation by describing diffusion maps and localized eigenfunctions. In addition, we discuss a possible connection with the weighted graph cut problem, and provide numerical evidence supporting the idea that lower-order eigenvectors point out local cuts in the network. However, we do not provide a formal and rigorous justification for our observations. DOI: http://dx.doi.org/10.1103/PhysRevE.87.032803 ©2013 American Physical SocietyKeywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Uncovering space-independent communities in spatial networksProceedings of the National Academy of Sciences, 2011
- Redrawing the Map of Great Britain from a Network of Human InteractionsPLOS ONE, 2010
- Spectral graph analysis of modularity and assortativityPhysical Review E, 2010
- Optimal map of the modular structure of complex networksNew Journal of Physics, 2010
- Community detection in graphsPhysics Reports, 2010
- Spectral tripartitioning of networksPhysical Review E, 2009
- Eigenplaces: Analysing Cities Using the Space–Time Structure of the Mobile Phone NetworkEnvironment and Planning B: Planning and Design, 2009
- Analysis of the structure of complex networks at different resolution levelsNew Journal of Physics, 2008
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000