Extracting spatial information from networks with low-order eigenvectors

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.

Figure 1

Diffusion map reconstructions from the top two eigenvectors, for various kernels, with nodes colored by longitude [(a),(b),(c),(d)] and latitude [(e),(f),(g),(h)].

Figure 2

Histogram of the top 500 eigenvalues of matrix $A$ for different kernels.

Figure 3

Top eigenvector colorings for the similarity matrix $W_{ij}=\frac{M_{ij}^2}{P_i{P}_j}$.

Figure 4

Histogram of the entries in the eigenvectors ${\varphi }_1,{\varphi }_7,{\varphi }_{28}$, and ${\varphi }_{83}$ of matrix $A=D^{-1}{W}^{\left(1\right)}$.

Figure 5

Heat map of the interstate migration flows, where the rows and columns of the matrix are sorted by the ratio degrees of the states. The intensity of entry $(i,j)$ denotes, on a logarithmic scale, the similarity between states $i$ and $j$, i.e., the sum of all entries in the submatrix ${\tilde{W}}_{i,j}$ defined in Fig. (4). Table lists the top 14 states in terms of ratio degree.

Figure 6

Diffusion map reconstructions from the top two eigenvectors, for various kernels. $T_{ij}$ denotes the aggregated communication time in seconds, $N_{ij}$ the number of phone calls between cities $i$ and $j$, $R_{ij}=\frac{T_{ij}}{N_{ij}}$ the average duration of a call, and $P_i$ the population of city $i$. We normalize by the population size by defining ${\overline{N}}_{ij}=\frac{N_{ij}}{P_i{P}_j}$ and ${\overline{T}}_{ij}=\frac{T_{ij}}{P_i{P}_j}$.

Figure 7

Colorings by the top 18 eigenvectors of $A=D^{-1}{W}^{\left(3\right)}$, where $W_{ij}^{\left(3\right)}=\frac{{\overline{T}}_{ij}}{R_{ij}}=\frac{N_{ij}}{P_i{P}_j}$.