Centrality measures in networks

For more discussion and references on the distinction between various forms of influence and social capital see Jackson (2020).

For instance, there are settings in which some attributes of nodes (e.g., size) may make them more central or influential, and so anonymity is inappropriate (e.g., see Jackson and Pernoud (2019)). To keep the discussion uncluttered, we focus on the anonymous measures, but the main points that we make extend to weighted versions of centrality measures.

This is somewhat reminiscent of König et al. (2014) who show that many centrality rankings coincide in nested-split graphs, which have a strong hierarchical form. Trees admit more variation, and so the characterization here provides new insight, especially as it helps us understand when nodal statistics coincide.

Some centrality measures proscribe self-loops and so we can adopt the convention that \(g_{ii}=0\); but again, the main results do not require such an assumption.

We define centrality measures as cardinal functions, since that is the way they are all defined in the literature, and are typically used in practice. Of course, any cardinal measure also induces an ordinal ranking, and sometimes cardinal measures are used to identify rankings.

Jackson (2008, Chapter 2.2) provides detailed history and references.

The more standard approach has to be to use the inverse of the distance as in Sabidussi (1966), so that a higher number indicates increased “closeness”, while this contrasts with the earlier definition of Bavelas (1950).

Decay centrality is also defined for \(\delta \notin [0,1]\), but then the interpretation of it as capturing decay is no longer valid.

In the limit, as \(\delta \rightarrow 0\), this places weight only on shortest paths, and then becomes closer to decay centrality, at least in trees.

\(\textbf{1}\) denotes the n-dimensional vector of 1s, and \(\textbf{I}\) is the identity matrix. Invertibility holds for small enough \(\delta\) (less than the inverse of the magnitude of the largest eigenvalue).

In a variation proposed by Bonacich there is a second parameter \(\beta\) that rescales: \(\textbf{c}^{KB} ({\textbf{g}}, \delta , \eta ) = (\textbf{I} - \delta {\textbf{g}})^{-1} \beta {\textbf{g}} \textbf{1}.\) Since the scaling is inconsequential, we ignore it.

\(\lambda ^{\max }({\textbf{g}})\) is positive when \({\textbf{g}}\) is nonzero (recalling that it is a nonnegative matrix), the associated vector is nonnegative, and for a connected network the associated eigenvector is positive and unique up to a rescaling (by the Perron-Frobenius Theorem).

This is related in spirit to basic epidemiological models (e.g, see Bailey (1975)), as well as the cascade model of Kempe et al. (2003) that allowed for thresholds of adoption (so that an agent cares about how many neighbors have adopted). A variation of the cascade model leads to a centrality measure introduced by Lim et al. (2015) called cascade centrality, which is related to the communication centrality of Banerjee et al. (2013) and the decay centrality of Jackson (2008). Diffusion centrality differs from these other measures in that it is based on walks rather than paths, which makes it easier to relate to Katz–Bonacich centrality and eigenvector centrality as discussed in Banerjee et al. (2013) and formally shown in Banerjee et al. (2019). Nonetheless, diffusion centrality is representative of a class of measures built on the premise of how much diffusion one gets from various nodes, with variations in how the process is modeled (e.g., see Bramoullé and Genicot (2018)). These are also used as inputs into other measures, such as that of Kermani et al. (2015), which combine information from a variety of centrality measures.

Note that they work directly with a weighted directed network. Thus, their \(\lambda _1=\delta \lambda ^{\max }({\textbf{g}})\).

See Ercsey-Ravasz et al. (2012) for some truncated measures.

This concept is first defined in Nieminen (1973) in discussing a directed centrality notion, and he refers to the neighborhood statistic as the subordinate vector.

The entries of the s’s may not sum to one, so this is not always a form of stochastic dominance, but it is defined analogously when the s’s have the same sum.

If \(L=\infty\), then when writing \(s_{i}^{\ell +1},\ldots ,s_{i}^{L},0,\ldots , 0\) below simply ignore the trailing 0’s.

It also implies monotonicity, but since we use monotonicity to establish the aggregator function on which additivity is stated, we maintain it as a separate condition in the statement of the theorem.

For smaller \(\delta\) diffusion centrality coincides with Katz–Bonacich centrality, and so exactly at the inverse of the largest eigenvalue, Katz–Bonacich and eigenvector centrality converge. This presumes that there is a unique first eigenvector, which holds if the adjacency matrix is primitive (e.g., see Jackson (2008)). Bonacich (2007) discusses some interesting properties of eigenvector centrality and how it can differ on signed and other networks, which violate these conditions.

Alternatively, we could define a closeness statistic, \(cl_i({\textbf{g}})= (cl_i^1({\textbf{g}}),\ldots , cl_i^\ell ({\textbf{g}}),\ldots ,cl_i^{n-1}({\textbf{g}}))\), is the vector such that \(cl_i^\ell ({\textbf{g}}) = \frac{n_i^\ell ({\textbf{g}}) }{\ell }\) for each \(\ell =1,2,\ldots ,n-1\), tracking nodes at different distances from a given node i, weighted by the inverse of those distances. and add another row. But this would build some of the weighting into the nodal statistics, which is cleaner to separate, pedagogically.

Without the restriction that \(L=n-1\) one can get additional statistics that repeat entries—for instance instead of having the neighborhood statistics \((n_i^1({\textbf{g}}), n_i^2({\textbf{g}}), n_i^3({\textbf{g}}), \ldots , n_i^{n-1}({\textbf{g}}))\), one can also get other statistics such as \((n_i^1({\textbf{g}}), n_i^1(g), n_i^2(g), n_i^2(g), n_i^3(g), n_i^3(g),\ldots , n_i^{n-1}(g), n_i^{n-1}(g))\) which duplicates entries.

Garg’s paper was never completed, and so the axiomatizations are not full characterizations and/or are without proof. Nonetheless some of the axioms in his paper are of interest.

König et al. (2014) prove that degree, closeness, betweenness and eigenvector centrality generate the same ranking on nodes for nested-split graphs, which are a very structured hierarchical form of network (for which all nodal statistics will provide the same orderings, and so the techniques here would provide an alternative proof technique). As noted above, Sadler (2022) investigates situations in which ordinal centrality measures coincide.

The other conditions guarantee that all leaves’ distances from the root differ by no more than one from each other. However, a line with an even number of nodes shows that there will be no well-defined root node that is more central than other nodes, and such examples are ruled out by this condition.

Note that this condition cannot be in conflict with the previous one, as it would violate the ordering of k and l. This latter condition only adds to the definition when i and j have the same immediate predecessor.

Without this condition, there are examples of trees that violate being a monotone hierarchy because of the leaf condition, but still have all nodes being comparable in terms of their neighborhood structures.

Proposition 2 shows a reversal of the partial order \(\succeq\). If the trees are irregular in having closer nodes have lower degree and farther nodes having higher degree, then one can get a reversal of \(\succ\), so that \(s_i \succ s_j\) and \(s^{\prime }_j \succ s^{\prime }_i\).

Even though the Shapley value satisfies an additivity axiom, it is an additivity across value functions and not across nodal statistics; and so does not translate here.

Note, for instance, that a convex combination of nodal statistics generates a different centrality measure from a convex combination of the measures, for instance. This opens interesting questions for future research.

It would generally make sense to have the \(\beta _\ell\) be a non-increasing function of \(\ell\). The presence of the \(\alpha _{\ell }\)s ensures that there is no excessive penalty for having \(s_i^\ell =0\) for some \(\ell\).

Note that even the ordering produced by this class of measures is equivalent to ordering nodes according to \(\sum _{\ell =1}^{L} \beta _{\ell } \log (\alpha _{\ell } + s_{i}^{\ell })\). This is an additive form, with nodal statistics \(\beta _{\ell } \log (\alpha _{\ell } + s_{i}^{\ell })\). This shows that it can be challenging to escape the additive family. Nonetheless, this is a new and potentially interesting family prompted by our analysis.

In addition, diffusion centrality has \(T=5\) in all of the simulations.

See Schoch et al. (2017) for some discussion of how correlation varies with network structure.