Extracting spatial information from networks with low-order eigenvectors
Authors:
- Mihai CucuringuMCMihai Cucuringu
- Vincent D. BlondelVBVincent D. Blondel
- Paul Van DoorenPDPaul Van Dooren
Preprint
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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Uncovering space-independent communities in spatial networksProceedings of the National Academy of Sciences, 2011
- Urban gravity: a model for inter-city telecommunication flowsJournal of Statistical Mechanics: Theory and Experiment, 2009
- Eigenplaces: Analysing Cities Using the Space–Time Structure of the Mobile Phone NetworkEnvironment and Planning B: Planning and Design, 2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Geographical dispersal of mobile communication networksPhysica A: Statistical Mechanics and its Applications, 2008
- Manifold parametrizations by eigenfunctions of the Laplacian and heat kernelsProceedings of the National Academy of Sciences, 2008
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion mapsProceedings of the National Academy of Sciences, 2005
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Irregular and fractal resonators with Neumann boundary conditions: Density of states and localizationPhysical Review E, 1997