An Axiom System for Feedback Centralities

1 Introduction

The question how to assess the importance of a node in a network has puzzled scientists for decades [Boldi and Vigna, 2014]. While the first methods, called centrality measures, have been proposed in social science in 1950s, in the last two decades centrality analysis has become an actively developed field in computer science, physics and biology [Brandes and Erlebach, 2005; Newman, 2005]. As a result, with a plethora of measures proposed in the literature, the choice of a centrality measure is harder than ever.

Feedback centralities form an especially appealing class of centrality measures. These measures assess the importance of a node recursively by looking at the importance of its neighbors or, in directed graphs, direct predecessors. Such an assumption is desirable in many settings, e.g., in citation networks where a citation from a better journal value more [Pinski and Narin, 1976] or in the World Wide Web where a link from a popular website can significantly increase the popularity of our page [Kleinberg, 1999].

Chronologically the first feedback centralities were Katz centrality and Katz prestige, proposed by Katz [1953]. Arguably, the most classic feedback centrality is Eigenvector centrality proposed by Bonacich [1972]. In turn, the most popular feedback centrality is PageRank designed for Google search engine [Page et al., 1999]. These four classic centralities, while based on the same principle, differ in details which leads to diverse results and often opposite conclusions.

∗Contact Author

In recent years, the axiomatic approach has attracted attention in the literature [Boldi and Vigna, 2014; Bloch et al., 2016]. This approach serves as a method to build theoretical foundations of centrality measures and to help in making an informed choice of a measure for an application at hand. In the axiomatic approach, the measure is characterized by a set of simple properties, called axioms. A number of papers use the axiomatic approach to characterize feedback centralities. Katz prestige was considered by Palacios-Huerta and Volij [2004] and by Altman and Tennenholtz [2005]. Kitti [2016] proposed algebraic axiomatization of Eigenvector centrality. Dequiedt and Zenou [2014] and W˛ as and Skibski [2018] proposed joint axiomatization of Eigenvector and Katz centralities. Recently, W ˛ as and Skibski [2020] proposed an axiomatization of PageRank.

While these results are a step in the right direction, most papers focus only on one or two feedback centralities. In result, each paper proposes a collection of axioms dedicated for the considered centrality, but poorly fitted to other measures. As a consequence, these characterizations based on different axioms do not help much in capturing the differences and similarities between various centrality concepts.

In this paper, we propose an axiom system for four classic feedback centralities. Our system consists of seven axioms. Locality, Edge Deletion, Node Combination are general axioms satisfied by all four centralities. Edge Compensation and Edge Multiplication concern modification of one node and its incident edges. Cycle and Baseline specify centralities in simple borderline graphs. For this set of axioms, we show that each of four feedback centralities is uniquely characterized by a set of 5 axioms: 3 general ones, one one-nodemodification axiom and one borderline axiom (see Table 1).

2 Preliminaries

In this paper, we consider directed weighted graphs with node weights and possible self-loops.

2.1 Graphs

A graph is a quadruple, G = (V, E, b, c), where V is the set of nodes, E is the set of ordered pairs of nodes called edges and b and c are node and edge weights: b : V → R≥0 and c : E → R>0. We assume that node weights are non-negative and edge weights are positive. The set of all possible graphs is denoted by G.

For a graph G, the adjacency matrix is defined as follows: A = (au,v)u,v∈V , where au,v = c(v, u) if (v, u) ∈ E and au,v = 0, otherwise. A real value r is an eigenvalue of a matrix A if there exists a non-zero vector x ∈ RV such that Ax = rx; such vector x is called an eigenvector. The principal eigenvalue, denoted by λ, is the largest eigenvalue.

An edge (u, v) is an outgoing edge for node u and an incoming edge for node v. For v, the set of its incoming edges is denoted by Γ-v (G) and outgoing edges by Γ+v (G). The total weight of outgoing edges, called the out-degree, is denoted by deg+v (G): deg+v (G) = ∑e∈Γ+v (G) c(e). For any x, graph G is x-out-regular if the out-degree of every node equals x: deg+v (G) = x for every v ∈ V . A graph is out-regular if it is x-out-regular for some x.

A walk is a sequence of nodes ω = (ω(0), . . . , ω(k)) such that every two consecutive nodes are connected by an edge: (ω(i), ω(i +1)) ∈ E for every i ∈ {0, . . . , k -1} and k ≥ 1. The walk is said to start at ω(0) and end at ω(k) and the length, |ω|, of a walk is defined to be k. The set of all walks of length k will be denoted by Ωk(G). If there exists a walk that starts in u and ends in v, then u is called a predecessor of v and v is called a successor of u. If the length of this walk is one, i.e., (u, v) ∈ E, then nodes are direct predecessors/successors. For node v, the set of predecessors of v is denoted by P(v) and the set of successors of v by S(v). The graph is strongly connected if there exists a walk between every two nodes, i.e., if S(v) = V for every node v ∈ V .

A strongly connected graph such that every node has exactly one outgoing edge is called a cycle graph.

Let us introduce some shorthand notation that we will use throughout the paper. For an arbitrary function f : A → X and a subset B ⊆ A, function f with the domain restricted to set B will be denoted by fB and to set A \ B: by f-B. If B contains one element, i.e., B = {a}, we will skip parenthesis and simply write fb and f-b. Also, for a constant x, we define x · f as follows: (x · f)(a) = x · f(a) for every a ∈ A. Furthermore, for two functions with possibly different domains, f : A → X, f ′ : B → X, we define f + f ′ : A ∪ B → X as follows: (f + f ′ )(a) = f(a) + f ′ (a) if a ∈ A ∩ B, (f + f ′ )(a) = f (a) if a ∈ A \ B and (f + f ′ )(a) = f ′ (a) if a ∈ B \A for every a ∈ A∪B. In particular, (b-v +2bv) are node weights obtained from b by doubling weight of node v. For two graphs, G = (V,E, b, c),G′ = (V ′ ,E′ , b′ , c′ ) with V ∩ V ′ = ∅, their sum G + G′ is defined as follows: G + G′ = (V ∪ V ′ , E ∪ E′ , b + b′ , c + c′ ).

2.2 Feedback Centralities

A centrality measure is a function F that given a graph G = (V, E, b, c) and a node v ∈ V returns a real value, denoted by Fv(G). This value, called a centrality of a node, is assumed to be non-negative and represents the importance of node v in graph G.

The class of feedback centralities aims to assess the importance of a node by looking at the importance of its direct predecessors. We consider four classic feedback centralities.

Eigenvector centrality. According to Eigenvector centrality [Bonacich, 1972], the importance of a node is proportional to the total importance of its direct predecessors:

This system of recursive equations has multiple solutions. Hence, some additional normalization condition is usually assumed to make a solution unique (e.g., the sum of centralities of all nodes is assumed to be 1 or |V |). In this paper, we use a normalization more consistent with other feedback centralities-we discuss it in the next section. The Eigenvector centrality is usually defined only for strongly connected graphs. We relax this assumption by considering also sums of strongly connected graphs with the same principal eigenvalue. 1 We denote the class of all such graphs by G EV .

Katz centrality. Katz [1953] proposed an alternative to Eigenvector centrality that adds a basic importance to each node. This shifts the emphasis from the total importance of its direct predecessors to their number. Formally, for a decay factor a ∈ R≥0, Katz centrality is defined as follows:

For a fixed a, Katz centrality is uniquely defined for graphs with λ < 1/a. We denote the class of such graphs by GK(a) .

Katz prestige. In Eigenvector and Katz centralities, the whole importance of a node is "copied" to all its direct successors. In turn, in Katz prestige [Katz, 1953], also called Seeley index or simplified PageRank, a node splits its importance equally among its successors. Hence, the importance of predecessors is divided by their out-degree. Formally, Katz prestige is defined as follows:

Similarly to Eigenvector centrality, this system of equations does not imply a unique solution. We will discuss our normalization condition in the next section. Katz prestige is usually defined only for strongly connected graphs. In our paper, we relax this assumption and consider sums of strongly connected graphs; we denote the class of all such graphs by GKP .

1 Note that we cannot allow for the sum of arbitrary graphs. It is because if one of the graphs has a smaller principle eigenvalue, then Eigenvector centralities of all its nodes would be zero.

PageRank. Page et al. [1999] was proposed tomodifyKatz prestige by adding a basic importance to each node. In this way, for a decay factor a ∈ [0, 1), PageRank is uniquely defined for all graphs as follows:

2.3 Walk Interpretations of Feedback Centralities

In this section we show how PageRank's random-walk interpretation from [W ˛ as and Skibski, 2020] can be extended for all four feedback centralities. These interpretations result in unique definitions of Eigenvector centrality and Katz prestige consistent with Katz centrality and PageRank.

Consider a spread of some entity (money, virus, information, probability of visit etc.) through a network. At the beginning, at time t = 0, each node has some initial amount equal to its node weight. Then, in each step the whole entity is multiplied by a scalar a, which is a parameter of the process, and then moved to direct successors. Here, we consider two variants of the process: distributed and parallel. In the distributed process, the entity is spread among the outgoing edges. In the parallel process, the entity is duplicated and moved along all edges. Specifically, when the entity is moved along an edge (u, v) it is either

• multiplied by c(u, v)/ deg+u (G) (distributed process), or
• multiplied by c(u, v) (parallel process).

As an example, consider a surfer on the World Wide Web. Node weights correspond to the probability that the surfer starts surfing from a specific page and weights of edges represent the number of links from one page to another. A link is chosen by the surfer uniformly at random which means the process is distributed. Finally, parameter a is the probability that the surfer stops surfing altogether. In result, the "entity" is the probability that the surfer visits a specific page at some time.

Consider the distributed process with parameter a. The amount of entity in node v at time t equals:

Now, if a < 1, PageRank is the total amount of entity in node v through the whole process:

We know that this sum converges, because a < 1. Now, if a = 1, the sum does not converge, as the amount of entity in the network does not change over time. In such a case we can look at the average amount of entity in node v. In this way we get the definition of Katz prestige:

Hence, Katz prestige is the stationary distribution of the process multiplied by the sum of node weights.

Let us turn our attention to the parallel process with parameter a. The amount of entity in node v at time t equals:

Now, if a < 1/λ, Katz centrality is the total amount of entity in node v through the whole process:

This sum converges, because a < 1/λ. Now, if a = 1/λ, the sum does not converge. In such a case, Eigenvector centrality can be obtained as the average amount of entity in node v:

It can be shown that Equations (5)-(8) indeed satisfy recursive equations from Equations (1)-(4). Hence, from now on, we will use Equations (5)-(8) as the definitions of all four centralities.

3 Axioms

In this section, we present seven axioms used in our axiomatic characterization.

All centrality measures except for PageRank are defined only for a subclass of all graphs. Hence, for them we will consider restricted versions of our axioms. Specifically, an axiom restricted to class G ∗ is obtained by adding an assumption that all graphs appearing in the axiom statement belong to G ∗ . In this way, we obtain a weaker version of the axiom.

Most of our axioms are invariance axioms. They identify simple graph operations that do not affect centralities of all or most nodes in a graph. The last two axioms serve as a borderline: they specify centralities in very simple graphs. We use three axioms proposed in the axiomatization of PageRank by W ˛ as and Skibski [2020]. Instead of the remaining three axioms, we use Locality and Node Combination which are more meaningful for considered classes of graphs.

Before we proceed, let us introduce an operation of proportional combining of two nodes used in one of the axioms. Proportional combining differs from a simple merging of nodes as it preserves the significance of outgoing edges. Take a centrality measure F , graph G = (V, E, b, c) and two nodes u, w ∈ V . Graph C F u→w (G) is a graph obtained in two steps:

• scaling weights of outgoing edges of u and w proportionally to their centralities: multiplying weights of outgoing edges of u by Fu(G)/(Fu(G) + Fw(G)) and w by Fw(G)/(Fu(G) + Fw(G)); and
• merging node u into node w, i.e., deleting node u, transferring its incoming and outgoing edges to node w and adding the weight of node u to node w.

See Figure 1 for an illustration.

We are now ready to present the first three axioms satisfied by all feedback centralities.

Locality (LOC): For every graph G = (V, E, b, c) and graph G′ = (V ′ , E′ , b′ , c′ ) s.t. V ∩ V ′ = ∅:

Edge Deletion (ED): For every graph G = (V, E, b, c) and edge (u, w) ∈ E:

Node Combination (NC): For every graph G = (V,E, b, c) and nodes u,w ∈ V s.t. deg+u (G) = deg+w (G) = deg+s (G) for every s ∈ S(u) ∪ S(w):

Locality and Edge Deletion are standard axioms from the literature. Locality, proposed in [Skibski et al., 2019], states that the centrality of a node depends solely on the part of the graph a node is connected to. In other words, removing part of the graph not connected to a node does not affect its centrality. Edge Deletion, proposed in [W˛ as and Skibski, 2020] for PageRank, states that removing an edge from the graph does not affect nodes which cannot be reached from the start of the edge. Node Combination is a new axiom. Assume two nodes u, w ∈ V and their successors have the same outdegree, but possibly different centralities. Node Combination states that in a graph obtained from proportional combining of u into w, the centrality of w is the sum of centralities of both nodes and centralities of other nodes do not change. This property is characteristic for feedback centralities which associate a benefit from an incoming edge with the importance of a node this edge comes from. We note that PageRank, Katz prestige and Katz centrality satisfy also the axiom without the assumption about equal out-degrees of successors. However, it is necessary for Eigenvector centrality.

Our next two axioms concern a modification of one node: its weight and weights of its incident edges.

Edge Multiplication (EM): For every graph G = (V, E, b, c), node u ∈ V , constant x > 0:

Edge Compensation (EC): For every graph G = (V,E, b, c), node u ∈ V , constant x > 0, b′ = b-u + bu/x and c′ = c-Γ±u (G)\{(u,u)} + cΓ-u (G)\{(u,u)}) /x + cΓ+u (G)\{(u,u)} · x:

Edge Multiplication, proposed in [W ˛ as and Skibski, 2020], states that multiplying weights of all outgoing edges of node u by some constant does not affect centralities. This means that the absolute weight of edges does not matter, as long as the proportion to other outgoing edges of a node is the same. This property is satisfied by both PageRank and Katz prestige. However, it is not satisfied by Eigenvector and Katz centralities, as it increase the importance of modified edges x times. For them, we propose a similar axiom: Edge Compensation. In this axiom, not only weights of outgoing edges of u are multiplied by a constant, but at the same time weights of incoming edges and the node itself are divided by the same constant. Edge Compensation states that this operation decreases the importance of u x times, but at the same time does not affect the importance of other nodes. See Figure 2 for an illustration.

Finally, the last two axioms concern simple borderline cases.

Baseline (BL): For every graph G = (V,E, b, c) and an isolated node v ∈ V it holds Fv(G) = b(v).

Cycle (CY): For every out-regular cycle graph G = (V,E, b, c) it holds Fv(G) = ∑u∈V b(u)/|V | for every v ∈ V .

Baseline, proposed in [W˛ as and Skibski, 2020], states that the centrality of a node with no incident edges is equal to its baseline importance: its node weight. Baseline is satisfied by PageRank and Katz centrality. However, it does not make sense for strongly connected graphs. Cycle, proposed as the borderline case for Eigenvector centrality and Katz prestige, considers the simplest strongly connected graph: a cycle. Specifically, if weight of all edges in a cycle graph are equal, then centralities of all nodes are also equal. Moreover, Cycle normalizes the sum of centralities to be equal to the sum of node weights. See Figure 3 for an illustration.

As we will show, these seven axioms are enough to obtain the axiomatizations of all four feedback centralities.

4 Main Results

In this section, we present our main results: We show that if a centrality satisfies three general axioms (LOC, ED and NC), one of the one-node-modification axioms (EM or EC) and one of the borderline axioms (BL or CY) then it must be one of the four feedback centralities.

The full proofs can be found in the extended version of the paper. 2 Here, we present the main ideas behind them.

First, consider Katz prestige and Eigenvector centrality.

Theorem 1. A centrality measure defined on GKP satisfies LOC, ED, NC, EM and CY if and only if it is Katz prestige (Equation (6)).

Theorem 2. A centrality measure defined on G EV satisfies LOC, ED, NC, EC and CY if and only if it is Eigenvector centrality (Equation (8)).

We begin by showing that Katz prestige and Eigenvector centrality are equal for strongly connected out-regular graphs. Then, we prove that both centralities satisfy the corresponding axioms. Hence, it remains to prove the uniqueness of both axiomatizations.

Let F be a centrality measure defined on G EV or GKP that satisfied LOC, ED, NC and CY. First, we show that F is equal to both centralities for strongly connected out-regular graphs. We divide it into two steps:

• First, we consider strongly connected out-regular graphs with rational proportion of weights of every two edges.
• Then, we consider arbitrary strongly connected outregular graphs.

These proofs are based on the following observation: for every strongly connected out-regular graph G with rational proportion of weights of its edges it is possible to construct a cycle graph G∗ , from which G can be obtained using proportional combining. As a result, if some centrality measure satisfies CY and NC, then it is uniquely defined on graph G.

We will present this construction on the graph G from Figure 4. Node weights are arbitrary, but we assume they sum up to 1. This graph is x-out-regular. In such graphs, it can be shown that Katz prestige of any node is rational; in this graph we have: KPv1 (G) = 2 13 , KPv2 (G) = KPv3 (G) = 3 13 , KPv4 (G) = 4 13 and KPv5 (G) = 1 13 .

Now, let us define an impact of an edge (u, v), denoted by I(u, v), as Katz prestige of node u multiplied by c(u, v)/ deg+u (G). Impacts of edges are depicted in graph G′ in Figure 4. For example, I(v4, v1) = Kv4 (G) · 1/2 = 2/13.

2 https://arxiv.org/pdf/2105.03146.pdf

Clearly, the total impact of outgoing edges of every node is equal to its Katz prestige. Also, from the Katz prestige recursive equation (Equation (3)), we see that the total impact of incoming edges of every node is also equal to its Katz prestige. We will use this fact later on. What is also important impacts are rational; let N be the least common multiple of all denominators of edge impacts. For graph G we have N = 13.

Based on the notion of impact we create a multigraph G′′ (a graph in which multiple edges exist between a pair of nodes). This multigraph is obtained by replacing edge (u, v) from the original graph by N · I(u, v) edges. For example, in our sample graph edge (v4, v1) with impact I(v4, v1) = 2/13 is replaced by two edges from v4 to v1. Now, the key observation is that every node in the multigraph G′′ has the same number of incoming and outgoing edges (as the total impact of its incoming edges equals the total impact of its outgoing edges). Hence, from Euler's theorem, we know that in G′′ there exists an Euler cycle-a walk that visits every edge exactly once and is a cycle: starts and ends in the same node.

Graph G∗ in Figure 4 is a cycle graph corresponding to some Euler cycle in graph G′′ . Here, nodes vi, v′i , . . . correspond to node vi in G′′ . We define node weights in a way that nodes corresponding to node vi sum up to b(vi). The construction of the cycle graph is complete.

Let us determine the number of nodes in G∗ . In graph G′′ node vi has N ·KPvi (G) outgoing edges. Hence, in G∗ there are N · KPvi (G) nodes corresponding to node vi. Since the sum of Katz prestige of all nodes in G is equal to the sum of node weights, i.e., 1, we get that there are N nodes in graph G∗ . In our example, there are indeed 13 nodes in G∗ and 4 nodes correspond to node v4.

Now, from CY, we know that according to F every node in G∗ has the same centrality equal to 1/N. It is easy to verify that if we merge using proportional combining for every node vi all nodes corresponding to vi we will obtain graph G. Based on NC this implies that node vi has centrality in G equal to N · KPvi (G) · 1/N = KPvi (G) which concludes the proof.

So far, we considered out-regular graphs and four axioms: LOC, ED, NC and CY. Here is where the proof splits:

• If F satisfies EM, then it is equal to Katz prestige for every graph; it is easy to see that every graph can be made out-regular if we divide weights of outgoing edges of every node by its outdegree.
• If F satisfies EC, then it is equal to Eigenvector centrality for every graph; here, more detail analysis is required, as the EC operation changes weights of both outgoing and incoming edges.

Now, let us turn our attention to PageRank and Katz centrality. We have the following results:

Theorem 3. A centrality measure defined on G satisfies LOC, ED, NC, EM and BL if and only if it is PageRank for some decay factor a (Equation (5)).

Theorem 4. A centrality measure defined on GK(a) satisfies LOC, ED, NC, EC and BL if and only if it is Katz centrality for some decay factor a (Equation (7)).

It is easy to check that both centralities satisfy their corresponding axioms. Let us focus on the proof of uniqueness.

The key role in our proof will be played by semi-outregular graphs which is a class of graphs in which all nodes except for sinks (nodes with no outgoing edges) have equal out-degrees. Most lemmas described below applies only to semi-out-regular graphs.

Let F be a centrality measure defined on G or GK(a) that satisfies LOC, ED, NC, BL and EM or EC. First, we show several technical properties of F that we use later in the proof: Node Combination generalized to all semi-out-regular graphs, minimal centrality equal to the node weight, linearity with respect to node weights and existence of a constant aF such that Fv({u, v}, {(u, v)}, b, c) = aF · b(u) if b(v) = 0 and c(u, v) = 1.

Next, we show that the profit from edge (u, v) for node v depends only on its weight and the centrality and out-degree of node u; moreover, if F satisfies EM or EC, then this profit is equal to the profit in PageRank or Katz centrality.

To this end, for x, y, z > 0, y ≤ z, we define a profit function pF (x, y, z) as follows:

where bx (u) = x, bx (v) = bx (w) = 0, cy,z (u, v) = y and cy,z (u,w) = z - y (if z = y, then we remove edge (u,w) from the graph). To put in words, value pF (x, y, z) is the profit from an incoming edge with weight y that starts in node with centrality x and out-degree z in the smallest such graph possible: with three nodes and two edges. It is easy to check that if F satisfies EM, then pF (x, y, z) = aF · x · y/z as PageRank and if F satisfies EC, then pF (x, y, z) = aF · x · y as Katz centrality.

Now, it remains to prove that the profit from any edge (u, v) equals pF (Fu, c(u, v), deg+u (G)). More precisely, we prove that:

First, we consider nodes without a self-loop only. We prove the thesis by induction over the number of incoming edges.

Let us illustrate the scheme of this proof on graph G from Figure 5. Consider node v and pick one incoming edge, say (u, v). First, we create graph G′ in which we extract from node u all its outgoing edges and attach them to a new node u′ with weight Fu(G). To keep the out-degree of u unchanged, we add a new node w with an edge from u. Using NC, it can be shown that Fv(G′ ) = Fv(G) and Fu′ (G′ ) = Fu(G).

In the second step, we split v into two nodes with the same outgoing edges, but disjoint incoming edges: v′ has one edge (u′ , v′ ), and v has the remaining edges. From NC we know that Fv(G) = Fv(G′′ ) +Fv′ (G′′ ). Since v has less incoming edges in G′′ than in G, we can use the inductive assumption. Hence, it remains to determine the centrality of v′ in G′′ .

To this end, observe that only u′ is the predecessor of v′ . Hence, from ED, removing all outgoing edges of other nodes does not affect the centrality of v. Also, from LOC, removing nodes other than u′ and its direct predecessors does not change the centrality of v. Hence, we can focus on graph G∗ . Using NC we can merge all of the nodes in G∗ except for u′ and v′ . In this way, we get a graph with three nodes and two edges, so we have Fv′ (G′′ ) = pF (Fu(G), c(u, v), deg+u (G)) what we needed to prove.

Next, we relax the assumption that the node does not have a self-loop. Finally, using EM or EC we get uniqueness for PageRank and Katz centrality.

5 Conclusions

We proposed the first joint axiomatization of four classic feedback centralities: Eigenvector centrality, Katz centrality, Katz prestige and PageRank. We used seven axioms and proved that each centrality measure is uniquely characterized by a set of five axioms. Our axiomatization highlights the similarities and differences between these measures which help in making an informed choice of a centrality measure for a specific application at hand.

There are many possible directions of further research. It would be interesting to extend our axiomatization to Degree centrality and Beta measure which constitute the borderline cases of feedback centralities. Another direction is considering centrality measures based on random walks, such as RandomWalk Closeness or Decay. Also, several axioms considered in our paper can form a basis for the first axiomatization of distance-based centrality measures for directed graphs.

Acknowledgments

This work was supported by the Polish National Science Centre grant 2018/31/B/ST6/03201.