Selection of Centrality Measures Using Self-consistency and Bridge Axioms

The number of network centrality measures studied in the literature exceeds 400 [1] and new measures appear every year. This diversity needs to be structured. The main means of structuring it is to establish a correspondence between the measures and their properties, some of which can be treated as axioms. The purpose of this paper is to advance this work by studying two natural axiomatic conditions, namely, the Self-consistency and Bridge axioms, which are closely related to some kernels and a certain class of kernel-based centrality measures. We establish a sufficient condition for the Bridge axiom, a necessary and sufficient condition for Self-consistency, and indicate centralities, some of which are well known and others are new, that satisfy these axioms.

Very often, centrality is identified with structural importance or influence [64, 80, 43, 65, 56, 57]. However, there are kinds of importance that are not reducible to centrality. Say, in a chain of moving people modeled by a path graph, the most important actors may be the leader and the trailer, i.e., the least central end elements of the chain, while the central elements may not be of particular importance. For another case where the key players are peripheral rather than central, see [77]. Thus, importance of network nodes is a broader concept than centrality.

Anyway, each point centrality index measures some structural capital (cf. [49]) of the nodes. It turns out that the types of capital accounted for by the centralities that satisfy the Bridge axiom on the one hand and by centralities satisfying Self-consistency and Monotonicity on the other hand are fundamentally different, so that these conditions are incompatible, provided that the Equivalence axiom is assumed. Similarly, the Bridge axiom is incompatible with another positive responsiveness axiom called Transit monotonicity. In terms of another taxonomy [10], these axioms are related to different types of nodal statistics: path-based for the Bridge axiom and walk-based for Self-consistency.

The axiomatic approach commences when we transition from examining the properties of specific objects to examining the properties in and of themselves. At this stage, some of the properties become requirements, and the objective becomes the search for objects that satisfy these requirements or their combinations.

Axiomatic study of centrality measures was initiated by Sabidussi [66] (whose starting point was the analysis of the Degree and Closeness centralities) and continued by Nieminen [61, 60] and others. A good review of early work is [13]. Among the papers published later or not mentioned in [13], interesting axioms and results can be found, in particular, in [63, 3, 42, 53, 12, 31, 36, 6, 67, 73, 72, 11, 10, 71, 79].

In many cases, the object of axiomatization is the procedure for assigning the most central node in a network [46, 78, 59], which implicitly characterizes the corresponding centrality measure.

In this paper, we focus on the Self-consistency and Bridge axioms, both of which are ordinal in nature. The first states that centrality measures must reward nodes for having neighbors with high centrality. The second one requires the measures to always reward the bridge end-node for the larger size of the component it belongs to after removing the bridge.

In the case of directed graphs that express paired comparisons, Self-consistency appeared in [25, 26, 29, 44, 32, 34]; in [33] it was applied to reference networks; in the case of undirected graphs, we find it in [6] under the name of Structural consistency. It strengthens Preservation of neighborhood-inclusion [67], whose directed graph version goes back to Preservation of cover relation [58].

The Bridge axiom was proposed in [73] to characterize the Closeness centrality; in [71] it was strengthened to Majority comparison; in [52], the Ratio property, another strengthening of the Bridge axiom, was presented.

In addition to the Self-consistency and Bridge axioms, the class of positive responsiveness axioms contains a number of monotonicity conditions, the study of which has a long history. We use a Monotonicity axiom similar to those proposed in [31, 11] and in [23, 30, 12] for directed graphs. Transit monotonicity is a natural strengthening of Monotonicity, which is incompatible with the Bridge axiom.

The Bridge and Self-consistency axioms are satisfied by certain kernel-based centralities. In this paper, we present several new classes of such centralities and illustrate the difference between their representatives. The corresponding kernels and some related centralities have been introduced by different authors; the references to their works are provided in Section 3.

PageRank is a centrality measure that has attracted a lot of attention. We show that, when applied to undirected networks, it violates most of the conditions under consideration and explain this phenomenon.

The paper is organized as follows. After introducing the basic notation in Section 2, in Section 3 we consider several families of centralities defined using graph kernels. In Section 4, the Bridge and Self-consistency axioms are introduced. Section 5 presents a sufficient condition for the Bridge axiom as well as a number of measures that satisfy it. In Section 6, we prove a necessary and sufficient condition for Self-consistency and present centralities that meet it. Section 7 discusses simple general requirements for centrality measures. In Section 8, we consider the axioms of Monotonicity and Transit monotonicity and prove that the addition of them is sufficient to ensure the properties of Section 7 and to form conditions incompatible with the Bridge axiom. The final Section 9 contains some interpretations of the results obtained and discusses some features of PageRank.

Let $G=(V,E)$ be an undirected unweighted graph with node set $V=V(G)$ and edge set $E=E(G).$ The order of $G$ is $|V|=n.$ Graph nodes will be labeled with $u,v,w,u_{i},v_{i}$, etc., numbers $0,1,2,\ldots,$ or names: Medici, Pazzi, etc. We consider graphs with $n>1,$ without loops and multiple edges. Since some centrality measures under study are applicable only to connected graphs, we confine ourselves to them.

Nodes $u$ and $v$ of $G$ are neighbors iff $\{u,v\}\in E(G).$ Let $N_{u}$ denote the set of neighbors of node $u.$

The adjacency matrix of $G$ is denoted by $A=A(G)=(a_{uv})_{n\times n}$: $a_{uv}=1$ when $u$ and $v$ are neighbors and $a_{uv}=0,$ otherwise. Neighborhood is a symmetric relation, so $A$ is symmetric. Let $\rho(A)$ be the spectral radius of $A.$

The degree $d_{u}$ of a node $u$ is the number of neighbors of $u$: $d_{u}=|N_{u}|.$ The vector of node degrees is $\bm{d}=(d_{1},\ldots,d_{n})^{T}=A\bm{1},$ where $\bm{1}=(1,\ldots,1)^{T}.$ A leaf is a node that has exactly one neighbor. Nodes $u$ and $v$ are equivalent in $G$ if there exists an automorphism¹¹1An automorphism of $G$ is a permutation $\sigma$ of $V(G)$ such that for any $u,v\in V(G),$ $\{u,v\}\in E(G)\Leftrightarrow$ $\{\sigma(u),\sigma(v)\}\in E(G)$. of $G$ that takes $u$ to $v$ ; in this case we write $u\sim v.$

The Laplacian matrix of $G$ is

where $\mathop{\mathrm{diag}}(\bm{x})$ is the diagonal matrix with vector $\bm{x}$ on the diagonal.

The union $G=G_{1}\cup G_{2}$ of arbitrary graphs $G_{1}$ and $G_{2}$ is defined by: $V(G)=V(G_{1})\cup V(G_{2})$ and $E(G)=E(G_{1})\cup E(G_{2})$.

Given a graph $G,$ a centrality measure (or centrality; sometimes, point centrality) $f\!:V(G)\to{\mathbb{R}}$ associates a real number $f(v)$ with each node $v\in V(G)$. For every $v\in V(G)$, $f(v)$ depends only on the graph structure and the position of $v$ in it [80]. For simplicity, we reflect the connection of $f$ with $G$ in the notation only when two or more graphs are considered simultaneously. Various conceptions of centrality are quite diverse. In this regard, there is no generally accepted definition of centrality that would semantically distinguish it from other types of point structural measures. A few simple attempts to make such a distinction are discussed in Section 7.

When a centrality measure $f$ on $G$ is fixed, we will write $u\succ v$ and $u\simeq v$ as abbreviations for $f(u)>f(v)$ and $f(u)>f(v)$, respectively. Moreover, if, for instance, $V=\{1,\ldots,7\},$ then $(\{1,6\},\{2,3,4\},5,7)$ is an example of centrality ranking of nodes $1$ to $7$ in which $f(1)=f(6)>f(2)=f(3)=f(4)>f(5)>f(7).$

In this section, we present several families of centrality measures.

Let $d(u,v)$ be the shortest path distance [18] between nodes $u$ and $v$ in a graph, i.e., the length of a shortest path between $u$ and $v.$ Two popular²²2For example, in [2, p. 1], the authors come to the conclusion that in the infection source identification problem, “a combination of eccentricity and closeness… generally performs better than several state-of-the-art source identification techniques, with higher accuracy and lower average hop error”. One more popular distance based measure is the Harmonic closeness $f(u)=\sum_{v\neq u}(d(u,v))^{-1}$. distance based centrality measures are the [Shortest path] Closeness [7, 8]

and [Shortest path] Eccentricity [7, 45]

The heuristics behind Closeness is that the most central node should have the minimum sum of distances from all other nodes. By adopting Eccentricity, we establish that the most central node minimizes the radius of the “ball” centered at that node and containing all other nodes.

General classes of Closeness and Eccentricity centralities are defined by (2) and (3) with $d(u,v)$ being arbitrary distances for graph nodes. In the literature, several classes of such distances and, more generally, dissimilarity measures have been proposed (see, e.g., [20, 4]). Substituting them in (2) and (3) provides centralities with varying properties. Many of the alternative distances and dissimilarity measures are defined via graph kernels. Let us consider a few of them.

1. The parametric Katz [51] kernels (also referred to as Walk [28] or Neumann diffusion [38] kernels) are defined as

with $0<t<(\rho(A))^{-1}.$

2. The Communicability kernels [37, 39] are

Two other classes of kernels are defined similarly through the Laplacian matrix (1).

3. The Forest kernels, or regularized Laplacian kernels [24, 74] are

4. The Heat kernels are the Laplacian exponential diffusion kernels [54]

By Schoenberg’s theorem [68, 69], if matrix $P=(p_{uv})$ is a kernel (i.e., is positive semidefinite), then it produces a Euclidean distance $d(u,v)$ by means of the transformation

where $\frac{1}{2}$ is the scaling factor. Thereby $G$ has an exact representation consistent with $P$ in Euclidean space. A coordinate form of this representation can be found using multidimensional scaling.

Thus, all Walk, Communicability, Forest, and Heat kernels with appropriate parameter values give rise to distances whose substitution into (2) and (3) yields Closeness and Eccentricity centralities. We denote them by Closeness(Kernel) and Eccentricity(Kernel) with the corresponding kernels substituted.

Furthermore, if $P_{n\times n}=(p_{uv})$ determines a proximity measure (which means that for any $x,y,z\in V,$  $p_{xy}+p_{xz}-p_{yz}\leq p_{xx}$, and this inequality is strict whenever $z=y$ and $y\neq x$), then [27] transformation

provides a distance function that satisfies the axioms of a metric. The Forest kernel with any $t>0$ produces a proximity measure, while kernels in the remaining three families do so when $t$ is sufficiently small [4]. The centralities obtained from a specific Proximity measure by transformation (7) and substitution of the resulting distance into (2) and (3) will be denoted by Closeness${}^{*}($Proximity$)$ and Eccentricity${}^{*}($Proximity$)$, respectively.

Moreover, if $P$ represents a strictly positive transitional measure on $G$ (i.e., $p_{xy}\,p_{yz}\leq p_{xz}\,p_{yy}$ for all $x,y,z\in V(G)$ with equality $p_{xy}\,p_{yz}=p_{xz}\,p_{yy}$ whenever every path in $G$ from $x$ to $z$ visits $y$), then transformation

produces [19, 20] a proximity measure. In this case, (7) applied to $\hat{P}=(\hat{p}_{uv})$ reduces to

and generates [20] a cutpoint additive distance $d(u,v),$ viz., such a distance that $d(u,v)+d(v,w)=d(u,w)$ whenever $v$ is a cutpoint between $u$ and $w$ in $G$ (or, equivalently, whenever all paths from $u$ to $w$ visit $v$). The centralities obtained from any strictly positive ​Transitional​_Measure by substituting distance (8) into (2) and (3) will be denoted by Closeness${}^{*}($$\log$Transitional​_Measure$)$ and Eccentricity${}^{*}($$\log$Transitional​_Measure$)$, respectively.

Since the Walk and Forest kernels determine [19] strictly positive transitional measures, (8) transforms them into cutpoint additive distances. Using (2) and (3) we obtain Closeness${}^{*}(\log$Forest$)$, Closeness${}^{*}(\log$Walk$)$ and the corresponding Eccentricity${}^{*}(\cdot)$ centrality measures.

Thus, the above results allow us to define Closeness and Eccentricity centrality measures obtained by substituting, among others, the:

• •

  Forest kernel;

• •

  Heat kernel;

• •

  logarithmic Forest kernel;

• •

  logarithmic Walk kernel;

• •

  logarithmic Heat kernel, and

• •

  logarithmic Communicability kernel

transformed by (6) or (7) into (2) and (3). These centralities were used in a culling survey [22] with parameter $t=1$ for the Forest, Heat, and Communicability kernels and $t=(\rho(A)+1)^{-1}$ for the Walk kernel.

Note that the authors of [50] examined the Closeness^∗(Forest) centrality and observed that the order of node importance induced by forest distances on some simple graphs was consistent with their intuition. Their conclusion was that “forest distance centrality has a better discriminating power than alternate metrics such as betweenness, harmonic centrality, eigenvector centrality, and PageRank”.

In addition to the above approaches, kernels and proximity/similarity measures can yield centralities without converting to distances. An example is the Estrada subgraph centrality [37]. For a node $u,$ it is equal to the diagonal entry $p^{\operatorname{Comm}}_{uu}(t)$ of the Communicability kernel, so we denote it by Communicability$(K_{ii}).$ Similarly, Walk$(K_{ii})$ is the measure $p^{\operatorname{Walk}}_{uu}(t),$ $u\in V$ determined by the diagonal entries of the Walk kernel.

An alternative is to sum the off-diagonal row elements of a kernel matrix. For example, Communicability($K_{ij}$) and Walk($K_{ij})$ are the centralities defined by $f^{t}(u)=\sum_{v\neq u}p^{\operatorname{Comm}}_{uv}(t)$ and $f^{t}(u)=\sum_{v\neq u}p^{\operatorname{Walk}}_{uv}(t),$ $u\in V,$ respectively.

Finally, Total communicability [9] is calculated by summing all row entries of the Communicability kernel: $f^{t}(u)=\sum_{v\in V}p^{\operatorname{Comm}}_{uv}(t)=(P^{\operatorname{Comm}}(t)\hskip 0.70007pt\bm{1})_{u}$; it can be described [35] in terms of “potential gain”. The Total walk measure $f^{t}(u)=\sum_{v\in V_{\mathstrut}}p^{\operatorname{Walk}}_{uv}(t)=(P^{\operatorname{Walk}}(t)\hskip 0.70007pt\bm{1})_{u}$ is order equivalent to the famous Katz centrality [51] $f^{t}(u)=((P^{\operatorname{Walk}}(t)-I)\bm{1})_{u}$, which we consider in Section 6.

Let us compare 16 kernel-based measures with the parameters mentioned above and the classical Closeness and Eccentricity centralities by examining how they act on ten simple graphs generated using the procedure described in [22] (Fig. 1). The Closeness, $K_{ii}$, $K_{ij},$ and Total measures give node $0$ in $G_{1}$ a higher centrality than node $1$, as shown in Fig. 1 by $0\succ 1$. Each Eccentricity measure assigns the same (minimal) centrality to all the diameter ends³³3If $d:V\times V\to{\mathbb{R}}_{+}$ is a distance (or more generally a dissimilarity measure) for the nodes of $G$, then $\max_{u,v\in V}d(u,v)$ is referred to as the corresponding diameter of $G$, while the nodes $u$ and $v$ that maximize $d(u,v)$ are the diameter ends. of a graph. As a result, the Eccentricity measures assign the same centrality to nodes 0 and 1 of $G_{1}$, which is shown as $0\simeq 1$. The Shortest path eccentricity sets $0\simeq 2$ in $G_{2}$, whereas the other Eccentricities set $2\succ 0$. Eccentricity(Forest) with $t=1$ assigns the highest centrality to both $4$ and $5$ in $G_{5}$, the others set $5\succ 4$. Turning to Closeness measures, a singularity of the Shortest path closeness is that it equalizes the centrality of $0$ and $5$ in $G_{6}$, while its competitors set $0\succ 5$. Furthermore, all logarithmic Closeness measures in this test set suggest $5\succ 2$ in $G_{6}$, while the other measures establish $2\succ 5.$ By looking at the separating graphs, the reader can judge which measures offer the most reasonable rankings.

The axioms in this section determine the relation between the centrality values of a pair of nodes in a graph of a special structure. As mentioned above, the measures under study assign centrality to nodes based solely on the graph structure. The Equivalence axiom is a partial embodiment of this idea (cf. [66, axiom A3]).

All measures under consideration satisfy axiom⁴⁴4We use the notation AE so as not to confuse this axiom with the edge set $E$ of a graph. AE; it will be assumed by default.

Among the most appealing axioms characterizing various classes of reasonable centrality measures are those of an ordinal nature. Such axioms allow one to compare the centrality of some nodes, but they do not indicate how to calculate the centrality values. In this sense, they are not fingerprints of particular centrality indices.

Positive responsiveness is a type of axiom, which is of primary importance in many axiomatic constructions. The template of these axioms is: “an increase in input (making a node more central from some point of view) leads to an increase in output (i.e., raises its centrality value or rank)”. Now we present two axioms of this kind. In the next two sections, we will find centrality measures that satisfy them.

Recall that a bridge in a graph is an edge whose deletion increases the number of graph’s connected components. The following axiom [73] relates the centrality of the end-nodes of any bridge.

A strengthening of this axiom is the Ratio property [52], which holds when for a positive $f,$ under the same premise, $f(u)/f(v)=|V_{u}|/|V_{v}|.$

The idea behind the second axiom is quite different. One may assume that the vector of centrality values of the neighbors of any node $u$ carries a lot of information about the centrality of $u$ itself (cf. Consistency in [36]). A more specific form of this idea is that “the higher the centrality values of a node’s neighbors, the higher the centrality of the node itself”.

This is in line with the justification given by Bonacich and Lloyd [16] to the Eigenvector centrality, a measure satisfying (see Section 6 below) the axiom we are approaching now: “The eigenvector is an appropriate measure when one believes that actors’ status is determined by those with whom they are in contact. This conception of importance or centrality makes sense in a variety of circumstances. Social status rubs off on one’s associates. Receiving information from knowledgeable sources adds more to one’s own knowledge. However, eigenvectors can give weird and misleading results when misapplied.”

This idea is exactly embodied in the Self-consistency axiom. For directed graphs, it was used in [25, 26, 29, 44, 32, 34, 33], in the case of undirected graphs, in [6].

Both the Bridge and Self-consistency axioms belong to the class of positive responsiveness axioms, however, the positivity requirement in the premise of Self-consistency is not objective: it is positivity in terms of $f$ itself. This implies that whenever $f$ satisfies axiom S and the values of $\bar{f}$ are ordered oppositely to those of $f$, it holds that $\bar{f}$ also satisfies S. Thus, Self-consistency equally welcomes both centrality and peripherality measures. Consequently, while the sole axiom S allows in some cases to conclude that $f(u)=f(v),$ it never implies $f(u)>f(v).$ In particular, a centrality that states $f(u)=f(v)$ for all $u,v\in V,$ trivially satisfies axiom S for any graph. That is why Self-consistency is usually combined with other axioms that specify centrality enhancers in terms of graph structure, not just reflections of neighbors’ centrality. These axioms include the edge-monotonicity conditions discussed in Section 8.

In the following two sections, we present several results on the centrality measures that satisfy the Bridge or Self-consistency axiom.

In the statements of this section, we use the notion of cutpoint additive distance and the Closeness${}^{*}(\log$Forest$)$ and Closeness${}^{*}(\log$Walk$)$ measures introduced in Section 3.

The Connectivity centrality [52] of vertex $u$ is equal to the number of permutations $\pi=(\pi_{1},\ldots,\pi_{|V|})$ of $V(G)$ such that $(i)$ $\pi_{1}=u$ and $(ii)$ for each $j\in\{2,\ldots,|V|-1\},$ the induced subgraph of $G$ with node set $\{\pi_{1},\ldots,\pi_{j}\}$ is connected.

Similarly, other strictly positive transitional measures [19] and cutpoint additive distances also produce centralities that satisfy the Bridge axiom.

To formulate a necessary and sufficient condition for Self-consistency, we introduce two definitions.

In the following definition, a centrality vector associated by a centrality measure $f$ with a graph $G$ having $V(G)=\{1,\ldots,n\}$ is a vector $\bm{x}=(x_{1},\ldots,x_{n})^{T}$ such that $x_{u}=f(u),$ $u\in V(G).$

In Definition 6.2, $\{x_{w}\!:\,w\in N_{u}\}$ is the multiset of the components of $\bm{x}$ that correspond to the neighbors of node $u$ in $G.$ If a centrality vector has a supporting neighborhood representation, then the centrality of each node is uniquely (and increasingly) determined by the centralities of its neighbors. A related concept of monotone implicit form appeared earlier in [26] and was used in [29, Theorem 12].

Lemma 6.3 will be used to prove the following statements, which involve five centrality measures; we now recall their definitions using the notation introduced in Section 2.

For a connected graph $G$ of order $n,$ vector $\bm{x}=(x_{1},\ldots,x_{n})^{T}$ presents:

• •

  the Katz centrality [51] if

  $$\bm{x}=\sum_{k=1}^{\infty}(tA)^{k}\hskip 0.70007pt\bm{1}=((I-tA)^{-1}-I)\hskip 0.70007pt\bm{1},$$

  (13)

  where $t\in{\mathbb{R}}$ is a parameter such that $0<t<(\rho(A))^{-1};$

• •

  the Bonacich centrality [15] with real parameters $\alpha$ and $\mbox{{\small$\beta$}}>0$ if $\bm{x}$ satisfies the system of equations

  $$x_{u}=\sum_{w\in N_{u}}(\mbox{{\small$\alpha$}}+\mbox{{\small$\beta$}}x_{w}),\quad u=1,\ldots,n;$$

  (14)

• •

  the Generalized degree centrality [31] if $\bm{x}$ satisfies the system of equations

  $$(I+\mbox{{\small$\alpha$}}L)\bm{x}=\bm{d},$$

  (15)

  where $\mbox{{\small$\alpha$}}>0$ is a real parameter;

• •

  the Eigenvector centrality [55, 14] if $\bm{x}$ is positive and satisfies the equation

  $$A\bm{x}=\rho(A)\hskip 0.70007pt\bm{x};$$

  (16)

• •

  the PageRank centrality [17] if $\bm{x}$ is positive and satisfies the equation

  $$\bm{x}=\left(\mbox{{\small$\alpha$}}A^{T}(\mathop{\mathrm{diag}}(A\bm{1}))^{-1}+(1-\mbox{{\small$\alpha$}})J\right)\bm{x},$$

  (17)

  where $J=\frac{1}{n}\bm{11}^{T},$ while $\mbox{{\small$\alpha$}}\in{\mathbb{R}}$ is the damping factor (or teleportation parameter) satisfying ${0<\mbox{{\small$\alpha$}}<1}.$ In the case of undirected graphs considered in this paper, $A^{T}=A.$

It should be noted that substituting $\mbox{{\small$\alpha$}}=1$ in (17) yields the Seeley centrality [70] whose scores are proportional to the node degrees in the undirected case. Generalized degree centrality results by applying the Generalized row sum method [23], whose score vector is proportional to $\bm{x}=(I+\mbox{{\small$\alpha$}}L)^{-1}\bm{s},$ where $\bm{s}$ is the vector of row sums in a matrix of paired comparisons, to the adjacency matrix $A$ with row sum vector $\bm{d}.$ Bonacich centrality is a version of Katz centrality, therefore the name Katz-Bonacich centrality can often be found.

To prove that a centrality measure satisfies Self-consistency, it suffices to find its supporting neighborhood representation, as we did, e.g., for the Katz centrality. Disproving this hypothesis reduces to giving a refuting example in the form of a pair of nodes in some graph that violates Self-consistency. For many measures, the well-known network of Florentine ruling families (Fig. 3) can help with this, as we show in Lemma 6.7 and Proposition 6.9.

Let $f$ be a centrality measure on a graph $G.$ For $k\in{\mathbb{N}}$ such that $1<k<n,$ we say that two $k$-tuples $(u_{1},\ldots,u_{k})$ and $(v_{1},\ldots,v_{k})$ each consisting of distinct nodes of $G$ are $f$ order equivalent iff for any $i,j\in\{1,\ldots,k\},$ $\mathop{\rm sign}\nolimits(f(u_{i})-f(u_{j}))=\mathop{\rm sign}\nolimits(f(v_{i})-f(v_{j})).$

The following proposition demonstrates that Lemma 6.7 can be quite useful in proving the violation of Self-consistency.

Note that Table 1 in [22] provides additional information on the violation of axiom S by centrality measures.

The best example of a “central” node is the center of a star of order more than $2.$ Formally, a star of order $n$ is a graph with one node (the center) having degree $n-1$ and $n-1$ nodes having degree $1.$ The edges of a star are sometimes called rays.

According to Freeman [41], “one general intuitive theme seems to have run through all the earlier thinking about point centrality in social networks: the point at the center of a star […] is the most central possible position”.

An example of a centrality measure that violates the star condition is given in [22, Section 1].

Self-consistency is a rather strong axiom, however, as was noted in Section 4, it is not self-sufficient and requires some accompanying axioms. One of its peculiarities is that it only applies to nodes of the same degree. Therefore, it does not imply the star condition. As distinct from it, the Bridge axiom implies this condition.

However, axiom B does not imply that the centrality of all leaves of a star is the same, which is immediate from Self-consistency (or from AE).

Roy and Tredan [65], trying to capture the intuition behind the concept of centrality, claim that for a path graph with nodes $1,\ldots,n$, where each node $u$ such that ${1<u<n}$ is linked to $u-1$ and $u+1,$ it is (converting to our notation) “hard to imagine a centrality $f$ such that, given a node $u$ $(u\neq\frac{n+1}{2}),$ we have $f(u)\not\in[f(u-1),f(u+1)]$”.

Clearly, under AE and $n>2$ the path centripetal condition is stronger than the RT condition. Proposition 7.5 states that the path centripetal condition follows from axioms B and AE.

It is all the more remarkable that PageRank, one of the most popular⁷⁷7To quote [76, p. 12530], “PageRank centrality is probably the most well-known and frequently used measure”; see also [5]. centrality measures, according to Roy and Tredan is “hard to imagine” because it violates the RT condition.