# axiomatization_of_the_pagerank_centrality__4f385040.pdf

Axiomatization of the Page Rank Centrality

Tomasz W as, Oskar Skibski University of Warsaw, Poland {t.was,o.skibski}@mimuw.edu.pl

We propose an axiomatization of Page Rank. Specifically, we introduce five simple axioms Foreseeability, Outgoing Homogeneity, Monotonicity, Merging, and Dummy Node and show that Page Rank is the only centrality measure that satisfies all of them. Our axioms give new conceptual and theoretical underpinnings of Page Rank and show how it differs from other centralities.

1 Introduction

Page Rank, 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, Page Rank 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, Page Rank 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 Page Rank 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

that the degree centrality only counts the number of neighbours, while the eigenvector centrality sums their centralities. Page Rank 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 Page Rank without node weights, called "a slightly simplified version of the Page Rank" by Page et al. [1999], has worse computational properties and is hard to define for some graphs [Langville and Meyer, 2011]. Although Page Rank 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 Page Rank differ from other similar measures? In other words, what properties characterize Page Rank? We answer this question by proposing an axiomatization of Page Rank 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 Page Rank is the only centrality measure that satisfies all the above axioms. To date, the original, general form of Page Rank has not been axiomatized. There exist two axiomatizations of the simplified version of Page Rank without node weights. Palacios-Huerta and Volij [2004] studied four properties of the Invariant method, which is this version of Page Rank adapted to the setting of scientific journal citation network. Altman and Tennenholtz [2005] characterized Page Rank for

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

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 GV 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):

Γ+ G(v) = {(v, u) E : u V }, Γ+ G(U) = S v U Γ+ G(v).

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) = P

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):

PG(v) = {u V : ΩG(u, 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: G[U] = (U, E[U], β[U], ω[E[U]]),

1More 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 Page Rank, 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:

G[M] = (V [M], M, β[V [M]], ω[M]),

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:

G + G = (V V , E E , β + β , ω + ω ).

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

c G = (V, E, c β, c ω).

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) = P q f 1(s) β(q) for every s V \ {u}, and

ω (s, t)=P 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.

Page Rank: A centrality measure, F : GV RV 0, is a function which assigns to every graph G and its node v a real value, denoted by Fv(G). Page Rank [Page et al., 1999], is a centrality measure, parametrised by a (0, 1), defined by the following recursive formula:

(u,v) Γ G(v)

ω(u, v) deg+ G(u)PRu(G)

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].

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

1 𝐹𝑂𝑅 𝑂𝐻 𝑀𝑂𝑁 𝑀𝑅𝐺 𝐷𝑁

Figure 1: An illustration of our five axioms. DN implies Fv(G5) = 2 and Fu(G5) = 1. Since equation (2) is satisfied, MRG implies Fv(G4) = Fv(G5)+Fu(G5). MON implies Fv(G3) > Fv(G4). OH implies Fv(G2) = Fv(G3). Finally, FOR implies Fv(G1) = Fv(G2). Edge weights are in italic font and node weights are bolded.

The Page Rank 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 Page Rank 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.

Foreseeability (FOR): For G GV and v V :

Fv(G) = Fv(G[Γ+ G(PG(v))]),

if PG(v) = , and Fv(G) = Fv(G[{v}]), otherwise. 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 Page Rank. 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

2This interpretation is valid if P

v V β(v) = 1 a. However, if the equation does not hold, the values can be easily scaled. 3This 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

ω (e) = s ω(e) if e Γ+ G(v), ω(e) otherwise,

then F(V, E, β, ω ) = F(V, E, β, ω). 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:

Fv(V, E {(u, v)}, β, ω ) > Fv(V, E, β, ω),

where ω (e) = ω(e) for every e E. 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.

Merging (MRG): For G GV and u, v V , if

deg+ G(u) Fv(G) = deg+ G(v) Fu(G), (2)

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 GV and v V :

Γ G(v) = Fv(G) = β(v).

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

Theorem 1. The Page Rank 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.

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

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

4 Uniqueness of the Page Rank Centrality

This section is devoted to proving Theorem 12, which states that each centrality measure that satisfies our five axioms is a Page Rank 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:

a. (Locality5): For every G GV such that V V = and v V it holds that Fv(G + G ) = Fv(G).

b. (Anonymity6): If G is isomorphic to G with isomorphism f, then Fv(G) = Ff(v)(G ) for every v V .

c. (Zero Nodes): Fv(G) = 0 if and only if β(v) = 0 and β(u) = 0 for every u PG(v).

d. (Removing Zero Nodes): If V0 = {v V : Fv(G) = 0} and v V \ V0, then Fv(G[V \ V0]) = Fv(G).

e. (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 Page Rank 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:

Fv(G) = β(v)

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:

Fu({u}, {(u, u)}, β, ω) = β(u) F( ˆG) = β(u)/(1 a),

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:

Fu( ˆG) > Fu({u}, , 1, ) = 1,

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 GV is F-normalised if for every v V , its out-degree equals its centrality, i.e., deg+ G(v) = Fv(G).

5Skibski et al. [2016] proposed this property as one of the axioms for the attachment and degree centralities. 6It 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 GV , 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 GV , 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

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Figure 2: An example of an out-unity graph.

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 GV and c R>0, graphs G+G and c G are F-normalised and

F(G + G ) = F(G) + F(G ).

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 Graphs7) A graph G GV 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:

OUG = G = (V, E, β, ω) G : v V |Γ+ G(v)| = 1 .

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 Page Rank centrality. Specifically:

7W 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.

𝑣2 𝐺𝑛: 𝐺𝑛 :

Figure 3: An illustration to the proof of Lemma 9.

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 GV , if G GV

is an in-tree with root v such that V V = {v}, then:

Fu(G+G ) = Fu G+({v}, , Fv(G ) 1, ) for every u V.

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

Fu(G) = β(u) + X

w PG(u) ah(w) h(u)β(w) = PRu(G).

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:

Fvi(G) = ai 1

1 an = PRvi(G), i {1, . . . , n}.

Proof. It is easy to check the equality for Page Rank. 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.:

Gk =(V Tk, E {(t1, t2), . . . ,(tk 1, tk),(tk, vk+1)}, βi, ωi),

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

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

G k = (V, E, β k, ω k) = Gk[V ] + ({vk+1}, , ak 1, ).

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

Fvk+1(Gk) = Fvk+1(G k) = ak Fv1(G). (3)

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:

Fvk+1(G) = Fv1(Gn) + Ft1(Gn) if k = n, Fvk+1(Gk) otherwise.

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 + an Fv1(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 Page Rank 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 GV without sinks, there exist F-normalised out-unity graphs G1, . . . , Gk GV 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:

Ge = G (Γ+ G(v) \ {e}), Gr = G {e}.

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 :

G = ce Ge + cr Gr, ce = deg+ Ge(v) Fv(Ge) , cr = deg+ Gr(v) Fv(Gr) .

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:

Fv(G) = deg+ G(v) = deg+ G (v) = Fv(G ).

Now, consider outgoing edges of node u V \ {v}: Γ+ G (u). We see that in each graph Ge, Gr, Ge, Gr, and G 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:

F(G ) OH = F(V, E, (ce + cr)β, (ce + cr)ω) P2e = (ce + cr)F(G).

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. Theorem 12. If centrality measure satisfies FOR, OH, MON, MRG, and DN, then it is a Page Rank centrality.

Proof. Assume that F satisfies FOR, OH, MON, MRG, and DN. Let G GV 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-normalised we

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

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. From Linearity (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 Page Rank centrality also satisfies Linearity we get that PR( G) = PR(G1) + + PR(Gk). Moreover, none of the functions f , f , f + influence the Page Rank centrality of nodes in a graph. Thus, PRv( G) = PRv(G) for every v V and

Fv(G) = Fv( G) = PRv( G) = PRv(G).

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 Page Rank centrality. Specifically, we proved that if a centrality measure satisfies five simple axioms Foreseeability, Outgoing Homogeneity, Monotonicity, Merging and Dummy Node then it is the Page Rank centrality. Our characterization is the first one of the Page Rank 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 ).

References [Altman and Tennenholtz, 2005] Alon Altman and Moshe Tennenholtz. Ranking systems: the Page Rank axioms. In Proceedings of the 6th ACM Conference on Electronic Commerce (ACM-EC), pages 1 8, 2005. [Bianchini et al., 2005] Monica Bianchini, Marco Gori, and Franco Scarselli. Inside pagerank. ACM Transactions on Internet Technology (TOIT), 5(1):92 128, 2005. [Bollen et al., 2006] Johan Bollen, Marko A Rodriquez, and Herbert Van de Sompel. Journal status. Scientometrics, 69(3):669 687, 2006. [Bonacich, 1972] Phillip Bonacich. Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology, 2(1):113 120, 1972. [Brandes and Erlebach, 2005] Ulrik Brandes and Thomas Erlebach. Network analysis: Methodological foundations. Springer-Verlag, 2005.

[Costa et al., 2007] L da F Costa, Francisco A Rodrigues, Gonzalo Travieso, and Paulino Ribeiro Villas Boas. Characterization of complex networks: A survey of measurements. Advances in physics, 56(1):167 242, 2007. [Freeman, 1979] Linton C. Freeman. Centrality in social networks: Conceptual clarification. Social Networks, 1(3):215 239, 1979. [Grando et al., 2016] Felipe Grando, Diego Noble, and Luis C Lamb. An analysis of centrality measures for complex and social networks. In IEEE Global Communications Conference (GLOBECOM), pages 1 6, 2016. [Haveliwala, 2002] Taher H Haveliwala. Topic-sensitive pagerank. In Proceedings of the 11th international conference on World Wide Web, pages 517 526. ACM, 2002. [Iván and Grolmusz, 2010] Gábor Iván and Vince Grolmusz. When the web meets the cell: using personalized Page Rank for analyzing protein interaction networks. Bioinformatics, 27(3):405 407, 2010. [Koschützki et al., 2005] Dirk Koschützki, Katharina Anna Lehmann, Dagmar Tenfelde-Podehl, and Oliver Zlotowski. Advanced centrality concepts. In Network Analysis, volume 3418 of Lecture Notes in Computer Science, pages 83 111. Springer, 2005. [Langville and Meyer, 2011] Amy N Langville and Carl D Meyer. Google s Page Rank and beyond: The science of search engine rankings. Princeton University Press, 2011. [Newman, 2010] Mark Newman. Networks: an introduction. Oxford university press, 2010. [Page et al., 1999] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The Page Rank citation ranking: bringing order to the web. Stanford Info Lab, 1999. [Palacios-Huerta and Volij, 2004] Ignacio Palacios-Huerta and Oscar Volij. The measurement of intellectual influence. Econometrica, 72(3):963 977, 2004. [Sabidussi, 1966] Gert Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581 603, 1966. [Skibski et al., 2016] Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, and Makoto Yokoo. Attachment centrality: An axiomatic approach to connectivity in networks. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 168 176, 2016. [Weng et al., 2010] Jianshu Weng, Ee-Peng Lim, Jing Jiang, and Qi He. Twitterrank: finding topic-sensitive influential twitterers. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM), pages 261 270, 2010. [W as and Skibski, 2018] Tomasz W as and Oskar Skibski. An axiomatization of the eigenvector and Katz centralities. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pages 1258 1265, 2018.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)