Scale-dependent measure of network centrality from diffusion dynamics

Classic measures of graph centrality capture distinct aspects of node importance, from the local (e.g., degree) to the global (e.g., closeness). Here we exploit the connection between diffusion and geometry to introduce a multiscale centrality measure. A node is defined to be central if it breaks the metricity of the diffusion as a consequence of the effective boundaries and inhomogeneities in the graph. Our measure is naturally multiscale, as it is computed relative to graph neighborhoods within the varying time horizon of the diffusion. We find that the centrality of nodes can differ widely at different scales. In particular, our measure correlates with degree (i.e., hubs) at small scales and with closeness (i.e., bridges) at large scales, and also reveals the existence of multicentric structures in complex networks. By examining centrality across scales, our measure thus provides an evaluation of node importance relative to local and global processes on the network.

Figure 1

[(a)–(c)] Diffusion and centrality on the interval $[\mathbf{0},\mathbf{1}]$. (a) Solution of the diffusion equation (1) given a delta function at $x=0.3$. The temporal responses at three points ($x_0=0.3$, $x_1=0.5$, $x_2=0.8$) exhibit presence or absence of peaks. The thin black lines correspond to the Green's functions forming the solution (2). (b) The peak time function $t^{*}(x_0,x)$ (4) represents the time at which an overshoot is observed at position $x$ for an initial delta function at position $x_0$. The white areas correspond to nonreachable points where $t^{*}(x_0,x)=\infty$. (c) The multiscale centrality measure ${\mathcal{M}}_{\tau }\left(x_0\right)$ (7) captures the center of the interval at large scales $\tau$. [(d)–(f)] Multiscale centrality of the Zachary's karate club network. (d) The snapshot of the solution (9) of the diffusion starting with an impulse from Mr. Hi after $t=0.1$ highlights the different reachability of different parts of the network. As shown in the three insets, only certain nodes experience an overshoot. (e) Matrix of peak times $t_{ij}^{*}$ clustered and ordered according to Ward hierarchical clustering. The peak times correspond well to the standard two-way partition, whilst identifying bridge nodes between the clusters. (f) The normalized multiscale centrality (10) for three values of $\tau$ reveals the importance of bridge nodes at large scales.

Figure 2

Multiscale centrality of (a) the Karate club network and (b) the Dolphin network [23]. (i) The multiscale centrality ${\mathcal{M}}_{\tau }$ (10) for short, middling and long scales. (ii) The multiscale centrality ${\mathcal{M}}_{\tau }$ for all nodes as a function of the scale $\tau$. (iii) Spearman correlation between ${\mathcal{M}}_{\tau }$ and four common centrality measures as a function of the scale $\tau$. ${\mathcal{M}}_{\tau }$ is most correlated with betweeness centrality for Karate club network and degree centrality for Dolphin network respectively at small scales, and both are most correlated with closeness at large scales.

Figure 3

Multiscale centrality of weighted graphs obtained from Delaunay mesh triangulations on the plane. (a) Uniform grid: at small scales, ${\mathcal{M}}_{\tau }$ is highly correlated with degree, whereas at large scale ${\mathcal{M}}_{\tau }$ coincides with the center (geometric center and center of mass), thus correlated with closeness. (b) Noisy uniform grid obtained by adding a Gaussian random deviation to the positions on the grid with variance 0.03. At small scales, the centrality again reflects the degree of the nodes and at large scales, the geometric center and center of mass of the square is still well captured by ${\mathcal{M}}_{\tau }$ . (c) Inhomogeneous mass distribution obtained by adding to the grid a dense patch of nodes Gaussianly distributed around the point (0.2,0.2). At small scales, ${\mathcal{M}}_{\tau }$ correlates with the degree, with high localization at the dense added patch of nodes. At large scales, the centrality ${\mathcal{M}}_{\tau }$ is concentrated on nodes between the center of mass and the geometric center of the square due to the combined effect of the mass distribution and the effect of the domain boundaries.

Figure 4

Multiscale centrality of the European power grid network [24] and Manhattan road network [25]. (a) The European power grid exhibits a multicentric structure, which is revealed at different scales. The centrality ${\mathcal{M}}_{\tau }$ is shown at four increasing scales (i)-(iv). At small scales, local centers are found in Spain and France, then progressive larger nuclei emerge in south west France, the Paris region, the Pyrenees coalescing onto a strip stretching from Venice to Amsterdam, with a large centrality region in Germany and Switzerland. (b) The Spearman correlation of ${\mathcal{M}}_{\tau }$ with four classic centrality measures for the European power grid. (c) The Manhattan road network at four increasing scales (i)–(iv). At small scales, the major bridges and tunnels into Manhattan are most central, followed by a coagulation of centrality in midtown which then progressively shifts towards the east coast before a final central region appears stretching between midtown west and midtown east. (d) The Spearman correlation of ${\mathcal{M}}_{\tau }$ with four classic centrality measures for the Manhattan road network.

Figure 5

Multiscale centrality of the irected and and weighted neuronal network of C. Elegans. (a) The neuronal network of C. Elegans has three types of neurons: sensory (S), inter (I), and motor (M) neurons. We compute ${\mathcal{M}}_{\tau }$ for (i) the original directed network; (ii) the reverse directed network; and (iii) the undirected network where the directionality of edges is ignored. (b) We show ${\mathcal{M}}_{\tau }$ for each of those networks at large values of the scale $\tau$. The most central nodes at large scales for each of the networks are (i) FLPR (a sensory neuron); (ii) RIMR/RIML (two motor neurons); (iii) PVT (interneuron) and AQR (sensory neuron). The most central nodes at small scales $\tau$ for all three graphs (in blue) are the AVAR/L neurons. (c) The multiscale centrality averaged over the neurons of each type (S,I, M) is computed for the three networks. Interneurons are most central for all three networks at all scales. Sensory neurons only become central at large scales for the directed network, whereas motor neurons only become central at large scales for the reverse directed network. In the undirected network, neither motor nor sensory neurons are central at any scale.