Axiomatization of the PageRank Centrality

1 Introduction

PageRank, introduced almost 20 years ago by Page et al. [1999], had a huge contribution to the way the current Internet looks like. While originally proposed to assess the importance of web pages in Google search engine, PageRank has quickly became one of the standard method of assessing the importance of nodes in complex networks-it is used to highlight cancer genes in proteomic data [Iván and Grolmusz, 2010], find the most influential users in the Twitter social network [Weng et al., 2010], and evaluate the prestige of journals based on the citation network [Bollen et al., 2006].

In the network science terminology, PageRank is a centrality measure-given a network (graph), it assigns to every node a number reflecting its importance [Brandes and Erlebach, 2005; Costa et al., 2007; Grando et al., 2016]. The standard centrality measures include the degree centrality that counts the number of links of a node, closeness centrality that assesses a node based on the average distance from other nodes, and betweenness centrality that focus on the number of shortest paths that goes through a given node [Freeman, 1979]. These measures significantly rely on the number of links that a given node has. Clearly, such an approach is undesirable in the context of web pages, where the cost of creating a link is marginal. As noted by Page et al. [1999], "any evaluation strategy which counts replicable features of web pages is prone to manipulation."

That is why PageRank was built upon the eigenvector centrality [Bonacich, 1972]. This centrality is defined recursively as the solution of the following equality: "centrality of a node is proportional to the sum of centralities of nodes pointing toward it" [Newman, 2010]. Intuitively, the eigenvector centrality is similar to the degree centrality with the difference PageRank introduces two important changes to the definition of the eigenvector centrality. First of all, the centrality of every neighbour, before being summed, is divided by its out-degree, i.e., the number of its edges. Thus, a centrality of a particular node is spread among successors, and not added to each node independently. In that way, the role of a node is limited by its importance. Second of all, each node is assigned an additional weight, regardless of incoming edges. These weights can represent, for example, how well a given web page matches the desirable criteria [Haveliwala, 2002]. Node weights greatly affect the behaviour of the value; in fact, a version of PageRank without node weights, called "a slightly simplified version of the PageRank" by Page et al. [1999], has worse computational properties and is hard to define for some graphs [Langville and Meyer, 2011].

Although PageRank has been proven to be an effective tool in various settings, the theoretical analysis of its properties is lacking. Given the plethora of alternative centrality measures that have been proposed in the literature [Koschützki et al., 2005], it is important to answer the question: how does PageRank differ from other similar measures? In other words, what properties characterize PageRank?

We answer this question by proposing an axiomatization of PageRank based on five simple axioms: (1) Foreseeability, states that the centrality depends solely on predecessors, and not successors of a node. (2) Outgoing Homogeneity states that multiplying weights of outgoing edges of a particular node does not affect centralities in the graph. (3) Monotonicity states that adding an edge to the graph should increase a centrality of its end-node. (4) Merging states that if edges of two nodes are equally important, then merging both nodes does not affect centralities of others. Finally, (5) Dummy Node implies that a node without any edges should have a centrality equal to its weight. We prove that PageRank is the only centrality measure that satisfies all the above axioms.

To date, the original, general form of PageRank has not been axiomatized. There exist two axiomatizations of the simplified version of PageRank without node weights. Palacios-Huerta and Volij [2004] studied four properties of the Invariant method, which is this version of PageRank adapted to the setting of scientific journal citation network. Altman and Tennenholtz [2005] characterized PageRank for graphs with unweighted edges and nodes. Moreover, only the ranking of nodes is axiomatized, and not the absolute values. Since weights of nodes significantly affect the value, many of the properties proposed in these papers do not work for the original, general version. 1

2 Preliminaries

In this section, we introduce basic definitions and notations.

Graphs: In this paper, we consider directed graphs with possible loops with weighted edges and nodes. Formally, a graph is an ordered 4-tuple, G = (V,E, β, ω), where V is the set of its nodes with the weight function β : V → R≥0 and E ⊆ V × V is the set of its edges with the weight function ω : E → R>0. For convenience, we will assume that ω(e) = 0 if e ̸∈ E. If β(v) = 1 for every v ∈ V , we will denote it by 1. Analogously, if ω(e) = 1 for every e ∈ E, we will also denote it by 1. The set of all graphs for a given set of nodes V is denoted by G V and the set of all possible graphs is denoted by G.

An edge (u, v) is an outgoing edge for the node u which is the start of this edge and an incoming edge for its end, node v. If u = v, the edge is called a loop. The set of outgoing edges from v is denoted by Γ+G(v), and from U by Γ+G(U):

Analogously, the set of incoming edges to v is denoted by Γ-G(v), and to U by Γ-G(U). Also, we define Γ±G(v) = Γ+G(v) ∪ Γ-G(v). A node without any outgoing edges is called a sink.

The out-degree of a node is the sum of weights of its outgoing edges, i.e., deg+G(v) = ∑e∈Γ+G(v) ω(e). Analogously, the in-degree is the sum of weights of its incoming edges.

A walk is an ordered set of k > 1 nodes, p = (v1, . . . , vk), such that every pair of consequent nodes form an edge, i.e., (vi, vi+1) ∈ E for every i ∈ {1, . . . , k - 1}. If additionally, the last and the first nodes form an edge, i.e., (vn, v1) ∈ E, then a walk is a cycle. The length of a walk is a number of nodes in p minus 1. By ΩG(u, v) we will denote the set of all walks in G between u and v, i.e., such that u is its first node, and v is the last one.

If there exists a walk from u to v, then v is called a successor of u and u is a predecessor of v. The set of all predecessors of v is denoted by PG(v):

Consider graph G = (V,E, β, ω). For a subset of nodes, U ⊆ V , we define β[U] : U → R≥0 as β[U](v) = β(v), ∀v ∈ U. Analogously, for a subset of edges, M ⊆ E, we define ω[M] : M → R>0 as ω[M](e) = ω(e), ∀e ∈ M.

For a subset of nodes, U ⊆ V , a subgraph induced by U is a graph obtained from G by removing nodes V \ U and their edges:

1 More in detail, only one of our axioms (Merging) is similar to axiom 3.4 (collapsing) from Altman and Tennenholtz [2005]. Other axioms, most of which rely on linearity of the simplified version of PageRank, could not be easily extended to the general version.

where E[U] = {(u, v) ∈ E : u, v ∈ U}. Similarly, for a subset of edges, M ⊆ E, a subgraph induced by M, denoted by G[M], is a graph obtained from G by removing edges from E \ M and nodes without edges:

where V [M] = {v ∈ V : M ∩ Γ±G(v) ̸= ∅}. Observe that if A ⊆ B ⊆ V or A ⊆ B ⊆ E, then G[A] = (G[B])[A]. For a subset of edges, E′ ⊆ E, we also use a shorthand notation: G - E′ = (V, E \ E′ , β, ω[E \ E′ ]).

Graph G = (V,E, β, ω) is called a cycle graph if V = {v1, . . . , vn} and E = {(v1, v2), . . . , (vn-1, vn), (vn, v1)}.

An in-tree is a tree with edges directed towards its root. Formally, G = (V, E, β, ω) is an in-tree with the root v ∈ V , if |Γ+G(v)| = 0, |Γ+G(u)| = 1 for every V \ {u}, and there exists no cycle in G. In an in-tree, for every u ∈ V there exists a unique walk from u to v; we denote its length by h(u). Also, we assume that h(v) = 0.

Graph operations: Consider two graphs G = (V,E, β, ω) and G′ = (V ′ , E′ , β′ , ω′ ).

We say that G′ is isomorphic to G if there exist a bijection, f : V → V ′ , such that E′ = {(f(s), f(t)) : (s, t) ∈ E}, β′ (s) = β(f -1 (s)) for every s ∈ V ′ , and ω′ (s, t) = ω(f -1 (s), f -1 (t)) for every (s, t) ∈ E′ .

The sum of G and G′ is defined as follows:

where (ω+ω′ )(e) = ω(e)+ω′ (e) and (β+β′ )(v) = β(v)+ β′ (v), assuming β(v)=0 for v ̸∈ V and β′ (v) = 0 for v ̸∈ V ′ . By multiplying graph G by a scalar, c ∈ R>0, we get

Merging node u with v results in a graph where β(v) = β(v) +β(u) and edges of u are "added" to node v. Formally, consider a function f : V → V \ {u} that maps both u and v into v: f(u) = f(v) = v, and f(w) = w for every w ∈ V \ {u, v}. Consequently, from merging u with v we obtain the graph G′ = (V \ {u}, E′ , β′ , ω′ ), where:

• E′ = {(f(s), f(t)) : (s, t) ∈ E},
• β′ (s) = ∑q∈f -1 (s) β(q) for every s ∈ V \ {u}, and
• ω′(s, t)= ∑p∈f -1(s),q∈f -1(t)ω(p, q) for every (s, t)∈E′.

An example can be seen in Figure 1, where graph G4 is obtained from G5 by merging node u with v.

PageRank: A centrality measure, F : G V →RV≥0 , is a function which assigns to every graph G and its node v a real value, denoted by Fv(G).

PageRank [Page et al., 1999], is a centrality measure, parametrised by a ∈ (0, 1), defined by the following recursive formula:

for every v ∈ V . It can be easily proved that for a given value of a there exist exactly one vector PR(G) for any graph G [Bianchini et al., 2005].

The PageRank centrality was proposed to determine the importance of web pages on the Internet. In this setting, nodes are referred to as pages, outgoing edges are named links, and incoming edges-backlinks.

To illustrate the way the PageRank centrality works, the authors proposed the model of a random surfer. In this model, the importance of each page is the stationary probability of this page being visited by a random surfer in an infinite walk on the entire network. In each step of this walk, the surfer clicks on a random link on the page he is; thus, while being on page v, he moves to the page u with the probability ω(v, u)/deg+G(v). However, with some probability, 1 - a, the surfer "gets bored", breaks his walk and start again from an indeterminate node. In such a case, he chooses each node, u, with the probability β(u). 2

As can be seen from the random surfer model, weights β can represent known preferences of the surfer over pages in the network. In lack of additional information, the uniform distribution can be chosen.

3 Our Axioms

In this section, we present our five axioms. In explanations, we will often use the web page terminology.

Our first axiom states that the importance of a page should depend not on its links (outgoing edges), but on the backlinks (incoming ones). Analogously, the importance of pages linking to our page should depend on their backlinks. In result, Foreseeability states that we can "foresee" a centrality of a page based on all predecessors and their links.

Note that Forseseeability takes into account also links of the predecessors, as the importance of a specific link of a predecessor (in particular, the one linking to our page) depends on the existence of other links.

Our second axiom, Outgoing Homogeneity, states that an importance of a given page should not depend on the absolute number of its links. This important property laid at the foundation of PageRank. In the graph setting, it means that multiplying the weights of the outgoing edges of any node by a constant should not affect anyone's centrality. 3

2 This interpretation is valid if ∑v∈V β(v) = 1-a. However, if the equation does not hold, the values can be easily scaled.

3 This axiom is similar to invariance with respect to reference intensity-a property defined in an axiomatic approach to scientific journal positioning introduced by Palacios-Huerta and Volij [2004].

Outgoing Homogeneity (OH): For G = (V,E, β, ω), v ∈ V and s > 0 if

Monotonicity states that if a page receives an additional backlink from a site that has non-zero popularity (which means it is sometimes visited) its importance increases. 4

Monotonicity (MON): For G = (V, E, β, ω) and u, v ∈

V such that (u, v) ̸∈ E and Fu(G) > 0:

For our next axiom, Merging, consider a situation in which two pages are being merged into one, preserving links and backlinks of both pages. The axiom states that as long as the proportion of importance to the number of links on both pages is the same (i.e., links on both pages are equally important), merging both pages does not change their combined importance or the importance of other pages.

then for the graph, G′ , obtained from G by merging node u with v, Fv(G′ ) = Fv(G) + Fu(G) and Fs(G′ ) = Fs(G) for every s ∈ V \ {u, v}.

For nodes u, v with outgoing edges and positive centralities condition (2) simply means that the ratio of their out-degree is equal to the ratio of their centrality, i.e.: deg+G(u)/ deg+G(v) = Fu(G)/Fv(G).

Our last axiom, Dummy Node, considers a simple borderline case-if there exists a page without any links nor backlinks, then its centrality is equal to its weight.

Dummy Node (DN): For G ∈ G V and v ∈ V :

We conclude this section with the theorem that states the PageRank centrality satisfies all above axioms.

Theorem 1. The PageRank centrality for any constant a ∈ (0, 1) satisfies FOR, OH, MON, MRG and DN.

Proof. Due to space constraints, we will omit several proofs in the paper.

4 A similar axiom under the same name was proposed by both Sabidussi [1966] and Skibski et al. [2016].

4 Uniqueness of the PageRank Centrality

This section is devoted to proving Theorem 12, which states that each centrality measure that satisfies our five axioms is a PageRank centrality (for some constant a).

We begin with simple properties implied by our axioms.

Proposition 2. Let F be a centrality measure that satisfies FOR, OH, MON, MRG and DN. For an arbitrary graph, G = (V, E, β, ω), the following statements are true:

1. (Locality 5 ): For every G′ ∈ G V ′ such that V ∩ V ′ = ∅ and v ∈ V it holds that Fv(G+G′ ) = Fv(G).
2. (Anonymity 6 ): If G′ is isomorphic to G with isomorphism f, then Fv(G) = Ff(v)(G′ ) for every v ∈ V .
3. (Zero Nodes): Fv(G) = 0 if and only if β(v) = 0 and β(u) = 0 for every u ∈ PG(v).
4. (Removing Zero Nodes): If V0 = {v ∈ V : Fv(G) = 0} and v ∈ V \ V0, then Fv(G[V \ V0]) = Fv(G).
5. (Homogeneity): F(c ·G) = c ·F(G) for every c ∈ R>0.

As we will show in Theorem 12, our axioms imply that a centrality measure is the PageRank centrality parametrised by an arbitrary constant a ∈ (0, 1) (equation (1)). The following lemma characterizes constant a.

Lemma 3. Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN. There exists a constant, a ∈ (0, 1), such that for every graph, G = (V,E, β, ω), if node v ∈ V forms an isolated loop, i.e., Γ±G(v) = {(v, v)}, then:

Proof. Consider graph ˆG = ({u}, {(u, u)}, 1, 1). Let us define a = 1 - 1/Fu( ˆG): in this way, we get that Fu( ˆG) = 1/(1 - a). From Homogeneity (Proposition 2e) and OH:

for an arbitrary β and ω. Now, from Locality (Proposition 2a) and Anonymity (Proposition 2b) we get that for every graph, G = (V, E, β, ω), and every node, v ∈ V , such that Γ±G(v) = {(v, v)} it holds that Fv(G) = β(v)/(1 - a).

It remains to prove that a ∈ (0, 1). Since 1/Fu( ˆG) > 0, we have a < 1. From MON and DN:

which implies that a > 0. This concludes the proof.

We will say that F satisfies axioms with constant a if it satisfies Fu({u}, {(u, u)}, 1, 1) = 1/(1 - a).

In our proof, we will focus on the following class of graphs.

Definition 1. (F-normalised graphs) For a centrality measure, F, graph G ∈ G V is F-normalised if for every v ∈ V , its out-degree equals its centrality, i.e., deg+G(v) = Fv(G).

5 Skibski et al. [2016] proposed this property as one of the axioms for the attachment and degree centralities.

6 It was one of the axioms proposed by Sabidussi [1966].

Observe that in a F-normalised graph each pair of nodes satisfies equation (2). Moreover, if F satisfies MRG, then merging any two nodes results in an F-normalised graph.

In what follows, we show that if F satisfies all our axioms, then every graph, G ∈ G V , can be transformed into an Fnormalised graph, ˜G, in which centralities of nodes from V are the same as in G, i.e.: Fv(G) = Fv( ˜G) for every v ∈ V .

We will construct this graph in three steps. (1) First, if needed, we add a new node and incoming edges to it to make sure that each node with a positive centrality has at least one outgoing edge (function f +). (2) Second, we remove all of the outgoing edges of the nodes with a zero centrality (function f -). (3) Finally, we adjust the weights of the edges to level out-degree with centrality (function f ∗ ).

Definition 2. (F-normalisation) For a centrality measure, F, and a graph, G, F-normalisation of G is graph ˜G = (f ∗ ◦ f - ◦ f +)(G), where f +, f -, f ∗ : G → G are functions defined for every graph G = (V, E, β, ω) as follows:

• f +(G) = (V ∪ {˜ v}, E ∪ E′ , β′ , ω′ ), where
• E′ = {(u, ˜ v) : Γ+G(u) = ∅, Fu(G) > 0}∪{(˜ v, ˜ v)}, - β′ (˜ v) = 0 and β′ (v) = β(v) for v ∈ V , and - ω′ (e) = 1 for e ∈ E′ and ω′ (e) = ω(e) for e ∈ E. if |E′ | > 1, and f +(G) = G, otherwise.
• f -(G) = G- {(u, v) ∈ E : Fu(G) = 0}; and
• f ∗ (G)=(V,E, β, ω′ ), where ω′ (u, v)=ω(u, v) Fu(G) deg+G(u) for every (u, v) ∈ E.

The following lemma states that F-normalisation is indeed F-normalised and it preserves the centralities of the nodes.

Lemma 4. Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN. For every graph G ∈ G V , its Fnormalisation ˜G is F-normalised and Fv( ˜G) = Fv(G) for every v ∈ V .

Proof. Let us consider an arbitrary graph G = (V, E, β, ω). Fix v ∈ V . First, we will show that functions f +, f -, and f ∗ do not modify the centrality of v.

Consider function f +. Let V ′ = {u ∈ V : Γ+G(u) = ∅, Fu(G) > 0} denotes the set of sinks with positive centrality in G. If V ′ = ∅, then f +(G) = G. Assume otherwise. Clearly, nodes from V ′ are not among the predecessors of v in G. In result, adding a new node, ˜ v, and edges between V ′ and ˜ v does not affect the set of predecessors and the set of their edges. Thus, FOR implies Fv(G) = Fv(f +(G)).

Consider function f -. Observe that removing all outgoing edges from nodes with zero centrality is equivalent to removing those nodes and adding them back again as isolated nodes. Therefore, from Zero Nodes and Removing Zero Nodes (Propositions 2c and 2d) we get Fv(G) = Fv(f -(G)).

Consider function f ∗ . Immediately from OH we get that Fv(G) = Fv(f ∗ (G)).

Finally, we argue that graph ˜G = f ∗ (f -(f +(G))) is Fnormalised. Consider graph G′ = f -(f +(G)). Since we proved that Fv(G′ ) = Fv(f +(G)) = Fv(G), we know that Fv(G′ ) = 0 if and only if Γ+G′(v) = ∅. In result, after applying function f ∗ , we get that deg+˜G(u) = Fu(G′ ) = Fu( ˜G). Thus, ˜G is F-normalised.

To make use of the class of F -normalised graphs we show that it forms a vector space, i.e., it is closed under addition and scalar multiplication.

Lemma 5. (Linearity) Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN. For every two Fnormalised graphs G, G′ ∈ G V and c ∈ R>0, graphs G+G′ and c · G are F -normalised and

Proof (Sketch). In a nutshell, we construct the graph G+G′ by creating an independent copy of graph G′ , denoted ˆG′ , and merging all pairs of corresponding nodes in G + ˆG′ . From Locality and Anonymity (Proposition 2a and 2b), we get that Fv(G) = Fv(G + ˆG′ ) and Fv(G′ ) = Ff(v)(G + ˆG′ ) for an isomorphism f between G′ and ˆG′ . Now, MRG implies Fv(G + G′ ) = Fv(G + ˆG′ ) + Ff(v)(G + ˆG′ ). Also, by looking at the out-degree in graph G+G′ , we get that G+G′ is F -normalised.

For c · G, the result simply follows from Homogeneity (Proposition 2e).

In the following definition, we propose a new class of graphs, called out-unity graphs. As we will show in Lemma 11, F-normalised out-unity graphs form a basis of all F-normalised graphs without sinks.

Definition 3. (Out-Unity Graphs 7 ) A graph G ∈ G V is an out-unity graph if every node v ∈ V has exactly one outgoing edge. The set of all such graphs will be denoted by:

Observe that each out-unity graph consists of one or more disconnected cycles with in-trees attached to their nodes. See Figure 2 for an example. Furthermore, we note that if centrality measure satisfies OH, then the edge-weight function does not affect the centrality of any node.

Corollary 6. Let F be a centrality measure that satisfies OH. Then, for every out-unity graph G = (V,E, β, ω) ∈ OUG: F (G) = F (V, E, β, 1).

In the remainder of this section, we will prove that if F satisfies our axioms, then it is the PageRank centrality. Specifically:

7 W ˛ as and Skibski [2018] studied similar Unity Graphs with single incoming (not outgoing) edge for every node when discussing other feedback centralities-eigenvector and Katz centralities.

• In Theorem 10 we show that if G is an out-unity graph, then F(G) = PR(G). We do it by first showing that:
• if G contains an in-tree, then we can change the weight of its root and remove its other nodes, preserving the centralities of the remaining nodes in G (Lemma 7).
• if G is an in-tree, F(G) = PR(G) (Lemma 8).
• if G is a cycle graph with a positive weight in only one of its nodes, then F(G) = PR(G) (Lemma 9).
• In Lemma 11, we show that every F-normalised graph without sinks can be deconstructed into several Fnormalised out-unity graphs.
• In Theorem 12, by combining Theorem 10 and Lemma 11, we show that F(G) = PR(G) for every graph G ∈ G.

In the following two lemmas we consider in-trees.

Lemma 7. Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN. For a graph, G ∈ G V , if G′ ∈ G V ′ is an in-tree with root v such that V ∩ V ′ = {v}, then:

Lemma 8. Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN with constant a. If graph G = G V is an in-tree, then for every u ∈ V , it holds that:

Now, we move to simple cycle graphs.

Lemma 9. Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN. For every cycle graph G = (V,E, β, ω) such that β(v1) = 1 and β(vi) = 0 for every i ∈ {2, . . . , n}, it holds:

Proof. It is easy to check the equality for PageRank. Thus, we will focus on proving that Fvi (G) = ai-1 /(1 - an ).

Roughly speaking, we will consider graphs consisted of a cycle with a simple in-tree attached to one of its nodes (as graph Gn in Figure 3). Then, using two different methods we will obtain a cycle graph: (1) by removing an in-tree and (2) by merging respective nodes. From Lemma 7 and MRG, this will imply our thesis.

To simplify the notation, we assume vn+1 = v1 and will use both symbols interchangeably. For every k ∈ {1, . . . , n} and nodes Tk = {t1, . . . , tk} we construct a graph Gk in which nodes V form the same cycle and nodes Tk ∪ {vk+1} compose an in-tree with vk+1 as its root, i.e.:

where βk(t1) = 1 and βk(u) = 0 for any u ∈ V ∪ Tk \ {t1} and ωk is such that Gk is F-normalised (for an example with k = n = 3 see Figure 3). From Lemma 8 we know that the centrality of in-tree formed by Tk ∪ {vk+1} is equal to ak .

Now, to use Lemma 7, let us consider graph G′k (see Figure 3), defined as

Then, Fu(G′k ) = Fu(Gk) for every u ∈ V . Now, notice that both G′k and G are cycle graphs with n nodes among which only one have positive weight. Thus taking graph (1/ak )G′k and adjusting its edge weights we can obtain a graph isomorphic to G. Therefore, from Corollary 6, Anonymity (Proposition 2b) and Homogeneity (Proposition 2e) we have

On the other hand, consider sequentially merging nodes tk, . . . , t1 with vk, . . . , v1 in the graph Gk. This way, we obtain graph ˆG = (V, E, β, ˆω) for some ˆω, i.e., a graph that differs (or may differ) from G only in weights of edges. Thus, from MRG and Corollary 6 we get:

As Ft1 (Gn) = 1, from FOR and DN, equation (3) yields Fvk+1 (G) = ak Fv1 (G) for k ∈ {1, . . . , n-1} and Fv1 (G) = 1 + anFv1 (G) which concludes the proof.

As every out-unity graph is consisted of one or more cycles with possible in-trees attached to their nodes, Lemmas 79 are enough to characterize centrality measure on out-unity graphs.

Theorem 10. Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN. For every F-normalised out-unity graph G ∈ OUG, F (G) = PR(G).

Proof (Sketch). Let us fix graph G = (V,E, β, ω) and a node, v ∈ V . We will show that Fv(G) = PRv(G). If v does not belong to any cycle, then it is a part of an in-tree. Thus, from FOR and Lemma 8 the thesis follows.

Assume otherwise, and let C ⊆ V be a subset of nodes such that v ∈ C and G[C] is a cycle graph. By using Lemma 7 and Lemma 8 we can construct graph G′ = (C,E[C], β′ , ω[C]) such that Fv(G) = Fv(G′ ) for every v ∈ C. From Corollary 6 and Linearity (Lemma 5) we can split G′ into |C| graphs, β′u · G′u , where graph G′u for every u ∈ C is a cycle graph where only node u has a positive weight equal to 1. From Lemma 9 we know that Fv(G′u ) = PRv(G′u ) and as Linearity (Lemma 5) also holds for PageRank centrality we obtain the thesis.

In the following lemma we show that every F-normalised graph can be deconstructed into out-unity graphs.

Lemma 11. Let F be a centrality measure that satisfies FOR, OH, MON, MRG, and DN. For every F-normalised graph G ∈ G V without sinks, there exist F-normalised out-unity graphs G1, . . . , Gk ∈ G V such that G = G1 + · · · +Gk.

Proof. Let G = (V,E, β, ω). We will prove this lemma by induction on |E| - |V |. If |E| - |V | = 0, then G is already an out-unity graph. Assume |E| - |V | > 0. Let v be a node with more than one outgoing edge, and let e ∈ Γ+G(v) be its arbitrary edge. Consider graphs:

Now, consider F-normalisations of Ge and Gr: ˜Ge and ˜Gr. Since all nodes have outgoing edges in G, then they also have in Ge and Gr. Thus, f +(Ge) = Ge and f +(Gr) = Gr, which means f ∗ ◦ f - ◦ f + does not add new nodes or edges to both graphs. Hence, both graphs have less edges than G. Now, consider graph G′ :

In the remainder of this proof we will show that G′ = G; since both ce ˜Ge and cr ˜Gr are F-normalised and have less edges than G, this will conclude the inductive step.

Let G′ = (V,E′ , β′ , ω′ ). We begin by showing that E′ = E. We already argued that f + applied to Ge and Gr does not add any edges. Function f ∗ does not modify the set of edges. Thus, it remains to consider function f -, which removes outgoing edges of nodes which have zero centrality. From Zero Nodes (Proposition 2c) we know that every node in G either has a predecessor with a positive weight or has the positive weight itself. Since the same is true in at least one of the graphs Ge and Gr, f - will not remove the same edge from both graphs.

Clearly, β′ = (ce + cr)β. Consider ω′ . First, we focus on outgoing edges of node v: Γ+G′(v). Weights ce and cr are defined in a way that ω′ (v, u) = ω(v, u) for every (v, u) ∈ Γ+G(v) (note that deg+˜Ge (v) = deg+Ge (v)/ce). Since both G and G′ are F-normalised, this implies:

Now, consider outgoing edges of node u ∈ V \ {v}: Γ+G′ (u). We see that in each graphGe, Gr, ˜Ge, ˜Gr, andG′ the relation between weights of any two edges is the same as in G. Thus, from OH, we can adjust them so that deg+G′ (u) = (ce + cr) · deg+G(u). By doing so, for every u ∈ V \ {v} and v we get:

But we have already proved that Fv(G) = Fv(G′ ); therefore, ce + cr = 1, β′ = β, and-since deg+G′(u) = Fu(G′ ) = Fu(G) = deg+G(u)-also ω′ = ω. Hence, G = G′ .

We are now ready to state our main theorem.

Theorem12. If centrality measure satisfies FOR, OH, MON, MRG, and DN, then it is a PageRank centrality.

Proof. Assume that F satisfies FOR, OH, MON, MRG, and DN. Let G ∈ G V be an arbitrary graph and ˜G its F-normalisation. On behalf of Lemma 4, we know that Fv( ˜G) = Fv(G) for every v ∈ V . If there exists a sink, denoted by v, in ˜G, then from the fact that ˜G is F-normalisedwe know that v has zero centrality. From Zero Nodes (Proposition 2c) and Removing Zero Nodes (Proposition 2d) we know that Fv( ˜G) = 0 and Fu( ˜G) = Fu( ˜G[V \ {v}]) for every u ∈ V \ {v}. Thus, we can assume that all nodes have outgoing edges. Then, by using Lemma 11, we take out-unity graphs G1, . . . ,Gk such that ˜G = G1 +· · ·+Gk. FromLinearity (Lemma 5) we have F ( ˜G) = F (G1) + · · · + F (Gk).

Now, for each i ∈ {1, . . . , k} we know that F(Gi) = PR(Gi) on behalf of Theorem 10. Observe that graph Gi is also PR-normalised. Since the PageRank centrality also satisfies Linearity we get that PR( ˜G) = PR(G1) + · · · + PR(Gk). Moreover, none of the functions f ∗ , f -, f + influence the PageRank centrality of nodes in a graph. Thus, PRv( ˜G) = PRv(G) for every v ∈ V and

This concludes the proof of Theorem 12.

We note that all five axioms are independent from each other, i.e., there exist a centrality measure that satisfies any four of them and does not satisfy the fifth one.

5 Conclusions

In this paper, we proposed an axiomatization of the PageRank centrality. Specifically, we proved that if a centrality measure satisfies five simple axioms-Foreseeability, Outgoing Homogeneity, Monotonicity, Merging and Dummy Nodethen it is the PageRank centrality. Our characterization is the first one of the PageRank in its original, general form.

In our future work, we plan to study other centrality measures based on random walks in a graph, such as the random walk closeness centrality.

Acknowledgements

Tomasz W ˛ as and Oskar Skibski were supported by the Foundation for Polish Science within the Homing programme (Project title: "Centrality Measures: from Theory to Applications").