Adjustable reach in a network centrality based on current flows

Centrality, which quantifies the “importance” of individual nodes, is among the most essential concepts in modern network theory. Most prominent centrality measures can be expressed as an aggregation of influence flows between pairs of nodes. As there are many ways in which influence can be defined, many different centrality measures are in use. Parametrized centralities allow further flexibility and utility by tuning the centrality calculation to the regime most appropriate for a given purpose and network. Here we identify two categories of centrality parameters. Reach parameters control the attenuation of influence flows between distant nodes. Grasp parameters control the centrality's tendency to send influence flows along multiple, often nongeodesic paths. Combining these categories with Borgatti's centrality types [Borgatti, Soc. Networks 27, 55 (2005)], we arrive at a classification system for parametrized centralities. Using this classification, we identify the notable absence of any centrality measures that are radial, reach parametrized, and based on acyclic, conserved flows of influence. We therefore introduce the ground-current centrality, which is a measure of precisely this type. Because of its unique position in the taxonomy, the ground-current centrality differs significantly from similar centralities. We demonstrate that, compared to other conserved-flow centralities, it has a simpler mathematical description. Compared to other reach-parametrized centralities, it robustly preserves an intuitive rank ordering across a wide range of network architectures, capturing aspects of both the closeness and betweenness centralities. We also show that it produces a consistent distribution of centrality values among the nodes, neither trivially equally spread (delocalization) nor overly focused on a few nodes (localization). Other reach-parametrized centralities exhibit both of these behaviors on regular networks and hub networks, respectively. We compare the properties of the ground-current centrality with several other reach-parametrized centralities on four artificial networks and seven real-world networks.

Figure 1

High and low grasp centralities. The figures depict the current of random walkers used to calculate the conditional current betweenness and the conditional resistance closeness from [3]. This is demonstrated on the (weighted) kangaroo interaction network from [21, 22]. Line thickness is proportional to current magnitude. A unit current flows from the source node (large, green) to the target node (large, red). Dashed lines indicate negligible current ($<0.01$ units). (a) At high grasp (low ${\mathrm{\Pi }}_D$), the current takes advantage of many parallel paths. (b) At low grasp (high ${\mathrm{\Pi }}_D$), the current follows only the shortest weighted path from the source to the target.

Figure 2

The ground-current centrality (right) as a multinode generalization of the resistance-closeness centrality (left). The ground-current centrality of a node $i$ is given as a function of the finite ground conductances (shown in light gray), by the currents flowing from that node to the ground node $g$ when a unit voltage is introduced between node $i$ and $g$. The exogenous ground-current centrality ${\tilde{\mathbf{M}}}_{ij}^{\mathrm{GCC}}$ is equivalent to the removal of the (dotted) connection between $i$ and and $g$. Ignoring the voltage sources, the left side of the figure illustrates the resistor-network interpretation of the network $\mathcal{N}$, while the right side illustrates the modified network ${\mathcal{N}}_g$.

Figure 3

High and low reach in the exogenous ground-current centrality. This is demonstrated on the (weighted) kangaroo interaction network from [21, 22]. Compare the grasp behavior of the conditional current betweenness in Fig. 1. Line thickness for edges $(k,l)$ indicates the product of the normalization factor $\tilde{\alpha }$ from Eq. (3) and the edge current magnitude $I_{k\to l}^i$, where the current flow results from a unit potential difference between the source node $i$ (large, green) and the ground node $g$ (not pictured). For readability, the line thickness is proportional to the square root of $\tilde{\alpha }{I}_{k\to l}^i$. Dashed lines indicate negligible current: $\tilde{\alpha }{I}_{k\to l}^i<0.0001$. All connections to ground have conductance ${\mathrm{\Pi }}_C$ and, because this is the exogenous centrality variant $\left(\tilde{\mathbf{M}}\right)$, every node other than the source node is connected to ground. Node $j$'s final contribution to $i$'s centrality is $\tilde{\alpha }{\tilde{\mathbf{M}}}_{ij}^{\mathrm{GCC}}=\tilde{\alpha }{I}_{j\to g}^i$. (a) At high reach (low ${\mathrm{\Pi }}_C$), the current spreads out to every node. Though the currents $I_{k\to l}^i$ are very small at this parameter value, the normalization factor results in non-negligible influences $\tilde{\alpha }{\tilde{\mathbf{M}}}_{ij}^{\mathrm{GCC}}$. In accordance with Table 2, the current to ground is the same at every node. (b) At low reach (high ${\mathrm{\Pi }}_C$), the current flows only along edges adjacent to the source, weighted by the edge conductance; see Table 2.

Figure 4

Intermediate reach in the exogenous ground-current centrality. See the caption to Fig. 3 for explanatory details. The reach is demonstrated on the (weighted) Florida power-grid network from [4, 30]. In this version of the network, the weights are readable from the figure: they are inversely proportional to the Euclidean distance between nodes. When the reach is high (${\mathrm{\Pi }}_C$ is low), the currents spread to nodes at large weighted distance from the voltage source. In this regime (e.g., at ${\mathrm{\Pi }}_C=0.1$), the amount of current flowing to ground from each node is approximately identical. As the reach decreases (${\mathrm{\Pi }}_C$ increases to, e.g., 5.0), the ground currents are no longer identical. The currents along edges far from the voltage source are diminished and, at very low reach (e.g., ${\mathrm{\Pi }}_C=500$), only currents to the voltage source's nearest neighbors remain.

Figure 5

The subdivided star network ${\mathcal{S}}_{\{1,2,3,4,6,8\}}$. We compare only the centralities of the large, labeled nodes. However, all 26 nodes are accounted for in the adjacency matrix. The node labels indicate the number of edges in the “spoke” terminated by that node, e.g., one must traverse four edges to move from $n_0$ to $n_4$. The weights are chosen to make the total weighted graph distance along the spoke equal to unity: here $D_{n_0{n}_1}=D_{n_0{n}_2}=D_{n_0{n}_3}=D_{n_0{n}_4}=D_{n_0{n}_6}=D_{n_0{n}_8}=1$. All edges within a spoke have the same length, and thus the same weight. (The edge weights are inversely proportional to the Euclidean distances in the figure.) For example, the six edges between $n_0$ and $n_6$ have weight 6. Because edge weights are inverse to weighted edge distances, $6\times (1/6)=D_{n_0{n}_6}=1$. There is one exception to the previous rules: a long edge $(n_0,n_{\mathrm{long}})$, where $d_{n_0{n}_{\mathrm{long}}}=1$ and $D_{n_0{n}_{\mathrm{long}}}=1000$.

Figure 6

Selected values of $\tilde{\alpha }{\tilde{\mathbf{M}}}^{\mathrm{COM}}$ for the ${\mathcal{S}}_{\{1,2,5,10,18,30\}}$ network. The same data are plotted on (a) log-linear and (b) log-log scales. Note that the normalization factor $\tilde{\alpha }$ depends on ${\mathrm{\Pi }}_T$. Without $\tilde{\alpha }$, the $\tilde{\mathbf{M}}$ values become unmanageably large. The Katz centrality is qualitatively similar, but with convergence failure at high reach (low values of ${\mathrm{\Pi }}_T$). At high reach, the COM fails to reproduce the intuitive HCC ranking of the ${\tilde{\mathbf{M}}}_{n_0{i}^{\mathrm{p}}}$.

Figure 7

Selected values of $\tilde{\alpha }{\tilde{\mathbf{M}}}^{\mathrm{GCC}}$ for the ${\mathcal{S}}_{\{1,2,5,10,18,30\}}$ network. The same data are plotted on (a) log-linear and (b) log-log scales. Note that the normalization factor $\tilde{\alpha }$ depends on ${\mathrm{\Pi }}_c$. Without $\tilde{\alpha }, \tilde{\mathbf{M}}$ values go to zero at small ${\mathrm{\Pi }}_c$. The inset in (b) shows the detailed behavior of the curves at high reach (low ${\mathrm{\Pi }}_C$), where the values for all peripheral nodes $i^{\mathrm{p}}$ become indistinguishable well before ${\tilde{\mathbf{M}}}_{n_0{n}_{\mathrm{long}}}$ achieves the same value. At all parameter values, the ground-current centrality reproduces the HCC's intuitive centrality ordering on the ${\tilde{\mathbf{M}}}_{n_{0}i}$.

Figure 8

Closed Cayley trees with degree $k$ and $n$ generations.

Figure 9

Exogenous centrality values for the closed Cayley tree with $k=3$ and $n=7$. In this network, all nodes at a given generation are equivalent, so there are only eight unique data points. The parameter values for each centrality are chosen to give the largest possible spread in the centrality values of the generations (ground-current: ${\mathrm{\Pi }}_C=0.010$, communicability: ${\mathrm{\Pi }}_T=0.202$, PageRank: ${\mathrm{\Pi }}_{\mathrm{PRC}}=1.055$). As discussed in the text, the Katz and PageRank centralities are identical on this network. The communicability values are similar but not equal to the Katz values. The horizontal line indicates the value of $1/N$, which coincides with the normalized degree centrality values on this network.

Figure 10

The weighted bottleneck network with length 5: $\mathcal{B}(L=5)$. All but two of the edges have unit lengths. The two edges forming the bottleneck have lengths of 10. They are depicted as thick lines in the figure.

Figure 11

Normalized (a) betweenness and (b) closeness results on $\mathcal{B}(L=15)$. Each nonwhite pixel corresponds to a node of $\mathcal{B}(L=15)$. For readability, the color scale is chosen such that the maximum centrality value (at given $\mathrm{\Pi }$) is black and the minimum nearly white. The (normalized) centrality values corresponding to these colors are reported for every $\mathrm{\Pi }$. A completely white region in the subfigures indicates a lack of network nodes in that location.

Figure 12

Communicability centrality on $\mathcal{B}(L=15)$. The full range of parameters is shown, in the sense that increasing or decreasing their values does not alter the image. The parameters are equally spaced on a log scale. For comparison, the red-bordered subfigure illustrates the centrality on the isolated $L=15$ lattice, using a maximum reach ${\mathrm{\Pi }}_T$ value for that network, so that decreasing ${\mathrm{\Pi }}_T$ does not alter the image. See the caption to Fig. 11 for details.

Figure 13

PageRank centrality on $\mathcal{B}(L=15)$. See the caption to Fig. 11 for details. Here the red-bordered subfigure illustrates the centrality on the isolated $L=15$ lattice at very low reach.

Figure 14

Ground-current centrality on $\mathcal{B}(L=15)$. See the caption to Fig. 11 for details.

Figure 15

Vole trapping network [34, 35]. The black nodes are those in the top 5% of betweenness rank. The gray nodes are, at high reach, those in the top 5% exogenous communicability centrality (equivalently, eigenvector centrality) rank. They are the two nodes with the highest weighted degree and some of their high-degree neighbors.

Figure 16

(a) Exogenous communicability centrality on the unweighted Florida power-grid network. (b) Exogenous ground-current centrality on the unweighted Florida power-grid network. The black curves correspond to nodes in the top 5% of betweenness rank. All the curves above the dashed red line correspond to nodes in the top 5% of (a) exogenous communicability and (b) exogenous ground-current centrality rank. See the text for details.

Figure 17

(a) Exogenous communicability centrality on the vole network [34, 35]. (b) Exogenous ground-current centrality on the vole network. For details, see the text and the caption to Fig. 16. The black lines correspond to the black nodes in Fig. 15.

Figure 18

Fractions of high-betweenness nodes among nodes with high (a) exogenous communicability, (b) exogenous PageRank Centrality, and (c) exogenous ground-current centrality. The fraction in (a) is equal to zero at all parameter values for both the vole network and the kangaroo network. The fraction in (b) is equal to zero at all parameter values for the kangaroo network. The crosses in (c) depict the fractions of high-betweenness nodes among nodes with high harmonic closeness centrality (HCC). These are always less than or equal to the highest fractions obtained by the ground-current centrality.

Figure 19

(a) The $\mathrm{IPR}$ of ${\tilde{c}}^{\mathrm{COM}}$ and (b) the Gini coefficient of ${\tilde{c}}^{\mathrm{COM}}$ for our example networks. The IPR is plotted on a log scale. The network labeled “circuit” is the electrical circuit network 838 from the ISCAS 89 benchmark set. The low-reach (scaled $\mathrm{\Pi }\approx 1$) results are equivalent to those of the degree centrality. The high-reach results (scaled $\mathrm{\Pi }\approx 0$) results are equivalent to those of the eigenvector centrality.

Figure 20

(a) The $\mathrm{IPR}$ of ${\tilde{c}}^{\mathrm{GCC}}$ and (b) the Gini coefficient of ${\tilde{c}}^{\mathrm{GCC}}$ for our example networks. See the caption to Fig. 19. Crosses represent the values of the nonbacktracking centrality (NBC) [14], based on the Hashimoto matrix [45].