Localization and centrality in networks

Eigenvector centrality is a common measure of the importance of nodes in a network. Here we show that under common conditions the eigenvector centrality displays a localization transition that causes most of the weight of the centrality to concentrate on a small number of nodes in the network. In this regime the measure is no longer useful for distinguishing among the remaining nodes and its efficacy as a network metric is impaired. As a remedy, we propose an alternative centrality measure based on the nonbacktracking matrix, which gives results closely similar to the standard eigenvector centrality in dense networks where the latter is well behaved but avoids localization and gives useful results in regimes where the standard centrality fails.

Figure 1

Graphical representation of the solution of Eq. (5). The curves represent the left-hand side of the equation, which has poles at the positions of the eigenvalues ${\chi }_i$ (marked by the vertical dashed lines). The diagonal line represents the right-hand side and the points where the two cross, marked by dots, are the solutions of the equation for $z$.

Figure 2

Bar charts of centralities for three categories of node for four examples of the model network studied here, as described in the text. All plots share the same scale. Error bars are small enough to be invisible on this scale.

Figure 3

Numerical results for the inverse participation ratio $S$ as a function of hub degree $d$ for networks generated using the model described in the text with $n=1000000$ vertices and average degree $c$ ranging from 4 to 11. The solid curves are eigenvector centrality; the horizontal dashed curves are the nonbacktracking centrality. The vertical dashed lines are the expected positions of the localization transition for each curve, from Eq. (9).

Figure 4

Eigenvector and nonbacktracking centralities for the electronic circuit network from Table 1. Node sizes are proportional to centrality (and color also varies with centrality).