Random-Walk Closeness Centrality Satisfies Boldi-Vigna Axioms Ricardo Mora1 and Claudio Gutierrez2 Center for Semantic Web Research, Dept. Computer Science, Universidad de Chile {rmora,cgutierr}@dcc.uchile.cl Abstract. Recently Boldi and Vigna proposed axioms that would char- acterize good notions of centrality. We study a random-walk version of closeness centrality and prove that is satisfies Boldi-Vigna axioms for non-directed graphs. Keywords: Random Walks, RDF, Centrality 1 Introduction Consider the Euclidean plane and a set of n points: Which one is the most central? An intuitive selection would be the point p that minimizes the sum of the distances from the other points to p. Consider now a set of n cities: In which one (abstracting social constraints) would you install a delivery store? Clearly in one that minimizes the sum of distances of each city to it (here distance is not Euclidean, but highways). A similar problem can be found inside a city (where distance is something close to Manhattan’s). In this paper we address this problem in the general case of undirected graphs, motivated by its application to semantic networks (particularly RDF graphs). This is not only a nice theoretical problem. One of the big challenges that the web offers today has to do with the huge quantity of data that it contains. In particular, in the case of large knowledge networks in the form of RDF graphs, it is highly relevant to understand which ones are the “essential” concepts they represent. What is the “good” distance in this case? There is some evidence [1, 2] that using a distance based on random walks might be a fruitful idea. It turns out, as we will show, that the idea of selecting a node v that minimizes the sum of the random walk distances from each other node u to v works really well in RDF graphs [3]. In this paper we study this notion and test it with the Boldi Vigna axioms. The problem of detecting central nodes in a graph has been extensively in- vestigated [4] and centrality indicators like degree and others based on shortest distances between elements such as betweenness centrality and closeness have been successfully employed on a variety of networks. By trying to unify these manifold centrality measures, recently Boldi and Vigna [5] proposed a set of ax- ioms that would capture the essential properties that underlie all of them. They show that classic notions such as closeness, degree, betweenness centrality do not satisfy these demanding axioms. In this paper we apply a Bodi Vigna test to random walk closeness centrality. We prove that this centrality notion satisfies these axioms for non-directed graphs. 2 Preliminaries 2.1 Basic Graph Theoretical Notions An undirected and simple graph (from now on we will work only with this kind of graph) is a pair G = (V, E) where E ⊆ [V ]2 , and [V ]2 is the set of all 2- elements subsets from V . The elements of V are the vertices of G, and the ones from E are its edges. When necessary, we will use the notation V (G) and E(G) for those sets. From now on, an element {u, v} ∈ E will be denoted simply by uv. An important family of graphs are cliques: for n ≥ 1 a n–clique is a graph Kn := (V, E) with |V | = n, such that E = [V ]2 . A vertex u is said to be a neighbor of another vertex v, when uv ∈ E. Note that the definition of E implies that v is also a neighbor of u. The set of neighbors of v will be denoted by NG (v). The degree of v, dG (v) is the size of NG (v). Should the reference be clear, they will simply be denoted by N (v) and d(v). Let G = (V, E) and G0 = (V 0 , E 0 ) be two graphs such that V ⊆ V 0 and E ⊆ E 0 , then G0 is said to be a subgraph of G (it is also said that G contains G0 ). For a subset S ⊆ V , G[S] := (S, {uv ∈ E : u, v ∈ S}) and G − S := G[V \ S]. Analogously, for F ⊆ E, G − F := (V, E \ F ).  A graph Pn = {v0 , v1 , ..., vn }, {v0 v1 , v1 v2 , ..., vn−1 vn } with n ≥ 0, where all vi are distinct is called a path, and the number of edges in it is its length. A cycle is a special type of path such that v0 = vn . We will call a cycle of length n a n–cycle. Let G = (V, E) be a graph and u, v ∈ V two distinct vertices. A path Pn in G, with n ≥ 1 such that v0 = u and vn = v, is called a u–v path. Also G is said to be connected if for all distinct u, v ∈ V a u–v path exists in G. A connected component of G is a maximally connected subgraph H. Note that a connected graph has only one connected component. An edge uv of G is said to be a bridge if the graph G − uv contains at least one more connected component than G. 2.2 Random Walks The next definitions come from the work of Lovász in random walk theory [6]. Let G = (V, E) be a connected graph such that |V | = n and |E| = m, where n, m ∈ N. Formally, a random walk is a sequence of vertices obtained as follows: it starts at a vertex v0 , and if at the t-th step it is at a vertex vt = u, it moves to a neighbor v of u with probability puv = 1/d(u). Note that the sequence of random vertices (vt : t = 0, 1, ...) is a Markov chain. Pt will denote the distribution of vt : Pt (v) = P(vt = v). The vertex v0 may be fixed, but may also be drawn from an initial distribution P0 . This initial distribution is said to be stationary if P1 = P0 (which will imply that Pt = P0 ∀t ≥ 0, because of the construction of the random walk). It can be easily proved that the distribution π(v) := d(v)/2m is stationary for every graph G. From now on π will be referred simply as the stationary distribution (it is not difficult to prove that this distribution is unique, which makes this reference valid). Definition 1. The hitting time H(u, v) is the expected number of steps that a random walk starting at vertex u takes to reach vertex v for the first time. Definition 2. Let S be a subset from V . The hitting time for a set H(u, S) is the expected number of steps that a random walk starting at vertex u takes to reach some vertex in S for the first time. When talking about H(S, u), a distribution (based on S) for the starting vertex of the random walk has to be specified. Therefore, if P is that distribution, HP (S, u) will be the expected number of steps that a random walk starting at a vertex of S (selected according to P) takes to reach vertex u for the first time. Note that for every pair of vertices u, v H(u, v) = H(u, {v}) = HP ({u}, v) . because the only starting distribution P in {u} is the trivial one. 3 Random Walk Closeness Centrality We are now in a position to formalize our notion of random walk centrality. The definition is motivated by several insights coming from different sources, but mainly from actual semantics graphs (RDF graphs). From a formal point of view –and this is the motivation of this paper– it satisfies (as it will be proven later) the three axioms of centrality proposed by Boldi and Vigna [5]. It is important to note that most centrality measures do not satisfy them all, thus making this notion of centrality interesting. Definition 3. [cf. [3]] Given a connected graph G = (V, E) and a vertex v ∈ V , the Random Walk Closeness Centrality of v is the real number X h. (v) = H(w, v). w∈V w6=v The smaller h. (v) is, the more central v is. A similar notion of centrality based on random walks was proposed by Noh and Rieger [7]. In fact, the definition proposed here is a particular case of a more general notion that includes both, Noh and Rieger’s and ours, but that will not be studied in this paper. 4 General Properties To prove that random walk closeness centrality satisfies Boldi and Vigna axioms, first we will need some properties. Proposition 4. Let u,v be distinct vertices of a connected graph G, and S ⊆ V \ {u, v} be such that every u–v path contains some vertex from S. Then H(u, v) = H(u, S) + HPu,S (S, v), where Pu,S is the distribution for random walks that start in S, such that for all w in that set, Pu,S (w) is the probability that w is the first vertex from S that a random walk starting in u reaches. Proof. Let Ωu be the sample space containing all possible outcomes associated to random walks that start in u and occur in G. Similarly, let ΩS be the one associated to random walks that start in any vertex w of S for which Pu,S (w) > 0. Consider the random variables TuS : Ωu → R, TSv : ΩS → R and Tuv : Ωu → R defined as follows TuS (ω) := # of steps that ω takes in order to reach some vertex in S for the first time. TSv (ω) := # of steps that ω takes in order to reach vertex v for the first time. Tuv (ω) := # of steps that ω takes in order to reach vertex v for the first time. Define X(ω) := Tuv (ω) − TuS (ω). Namely, X is also a random variable that satisfies X : Ωu → R and X(w) = # of steps that ω takes (after reaching S for the first time) in order to reach vertex v for the first time. For ω ∈ Ωu write ω = (u, v1 , v2 ...) and define iS (ω) := mini>0 {vi ∈ S} and iv (ω) := mini>0 {vi = v}. Also, define ωS := (viS , viS +1 , ...) and j(ωS ) := mini>0 {vi+iS = v}. Note that j(ωS ) = iv (ω) − iS (ω) and that ωS is an ele- ment of ΩS , because random walk are Markov process. Then, for n ∈ N X P(X(ω) = n) = P(viS (ω) = w)P(iv (ω) − iS (ω) = n) w∈S X = Pu,S (w)P(j(ωS ) = n) = P(TSv (ωS ) = n) . w∈S Therefore, X and TSv are random variables with the same expected value. Fi- nally, by using this H(u, v) = E(Tuv ) = E(TuS + X) = E(TuS ) + E(X) = E(TuS ) + E(TSv ) = H(u, S) + HPu,S (S, v) . t u Corollary 5. Let u,w,v be three distinct vertices of a connected graph G such that every u–v path contains w. Then H(u, v) = H(u, w) + H(w, v) . Proof. It follows directly from proposition 4 by considering S = {w}. t u Before stating the next theorem, we need the following result from Lovász [6] and one more definition. Lemma 6 (Lovász [6]). The probability that a random walk starting at u visits v before returning to u is 1 (H(u, v) + H(v, u))π(u) Definition 7. For a bridge uv of a connected graph G = (V, E), define Gu as Gu := G[{w ∈ V : ∀ w–v path in G, u ∈ w–v}], that is, Gu and Gv are the connected components of G − uv (see Fig. 1 below). ... ... ... u v ... ... Fig. 1. An example of a graph G with a bridge uv. To the left of the dashed line is Gu and to the right of the dash-dotted line is Gv . Note that u ∈ Gu . Theorem 8. Let uv be a bridge of a connected graph G. Then H(u, v) = 2|E(Gu )| + 1 . Proof. First note that any random walk starting at u has to go through v before stepping into another vertex of Gv , therefore H(u, v) does not depend on Gv . Because of this, for simplicity, we can assume that Gv = (v, ∅). Then, H(v, u) = 1 and |E(G)| = |E(Gu )| + 1. Now, the probability that a random walk starting at u reaches v before returning to u is 1/d(u). Then, it follows from lemma 6 that d(u) d(u) = (H(u, v) + H(v, u))π(u) = (H(u, v) + 1) 2|E(G)| d(u) = (H(u, v) + 1) , 2|E(Gu )| + 2 which is equivalent to H(u, v) = 2|E(Gu )| + 1, that is what we wanted to prove. t u Finally, using these properties we can prove the following result that will allow us to compare the centrality of different vertices, under certain conditions. Proposition 9. Let uv be a bridge of a connected graph G. Then h. (u) < h. (v) ⇐⇒ (2|E(Gu )| + 1)|V (Gu )| > (2|E(Gv )| + 1)|V (Gv )| . Proof. The proof is straightforward and is included in the appendix. 5 Boldi and Vigna Axioms We can now prove what was previously promised. Boldi and Vigna [5] seek to define certain axioms that provide a formal and provable piece of information about a centrality measure so it can be assured that it correctly captures the intuitive notion of centrality. To this end, they propose to study the behavior of the measure when making changes of size, local edge density and addition of edges in the graph. It is important to note that the axioms were designed primarily for measures that work with directed, and not necessarily connected graphs. For graphs representing semantic networks, direction is not relevant because the predicate represented by the directed edge represents at the same time the inverse predicate. Therefore, we work with a version of the original axioms adapted for connected and undirected graphs. First is the Size Axiom. The idea is to compare the centrality of vertices from a clique and a cycle joined through a path of large enough size. When fixing the size of one of them, and letting the other grow as much as wanted, one would expect the vertices of the latter to become more central. This is formalized as follows: Axiom 1: (Size axiom) Consider the graph Sk,p made by a k-clique and a p-cycle connected by a path of length l (see Fig. 2). A centrality measure satis- fies the size axiom if for every k there are two constants Pk , Lk such that for all p ≥ Pk , l ≥ Lk , the centrality of any vertex of the p-cycle is strictly better than the centrality of any vertex in the k-clique, and the same holds when inverting the situation (that is, fixing p and letting k be as big as desired). Proof. We will prove it for the first case as for the inverted situation the proof is analogous. For simplicity of notation we will use the labels proposed on Fig. 2 when referring to the nodes of Sk,p . Also, we will denote by K the subgraph of Sk,p that corresponds to the clique. ... c1 cp−1 k 0 1 ... l−1 l cp ... Fig. 2. An example of graph Sk,p . First note that it is not difficult to prove that vertex 0 is the most central vertex of the clique, and that cp is the one from the cycle with worst centrality. Therefore, if we prove that cp is more central than 0, we will have proved the result. Indeed, we have that X l X p−1 X h. (0) = H(w, 0) + H(j, 0) + 2 H(cj , 0) + H(cp , 0) w∈V (K) j=1 j=1 w6=0 l−1 X p−1 X = (k − 1)2 + H(j, 0) + 2 H(cj , l) + H(cp , l) + 2pH(l, 0) . j=1 j=1 On the other hand, the value of h. (cp ) is X l X p−1 X = H(w, cp ) + H(0, cp ) + H(j, cp ) + 2 H(cj , cp ) w∈V (K) j=1 j=1 w6=0 X l−1 X p−1 X = H(w, 0) + kH(0, cp ) + H(l, cp ) + H(j, cp ) + 2 H(cj , cp ) w∈V (K) j=1 j=1 w6=0 l−1 X p−1 X = (k − 1)2 + kH(0, l) + H(l, cp )(k + l) + H(j, l) + 2 H(cj , cp ) . j=1 j=1 Therefore, h. (0) − h. (cp ) equals p−1 X l−1 X =2 [H(cj , l) − H(cj , cp )] + [H(j, 0) − H(j, l)] + H(cp , l) + 2pH(l, 0) j=1 j=1 (1) − kH(0, l) − H(l, cp )(k + l) .   k(k + 1) Now, fix l ∈ N so that l > . Then 12 k(k + 1) k(k − 1) l> ⇐⇒ 6l > k + . (2) 12 2 Note that for k, l fixed, we can make p big enough so that the second sum of (1) is strictly greater than 0. Also, we have the following p−1 X =2 [H(cj , l) − H(cj , cp )] j=1 p−1    X k(k − 1) =2 j(2p − j) − (p − j) j + +l+p j=1 2 p−1      X k(k − 1) k(k − 1) =2 j + l + 2p − p +l+p j=1 2 2   k(k − 1) = p(p − 1) + l + 2p − p(p − 1)(k(k − 1) + 2l + 2p) 2   k(k − 1) = p(p − 1) − −l . 2 Using these two facts and (1), we have that h. (0) − h. (cp ) is strictly greater than   k(k − 1) > H(cp , l) + 2pH(l, 0) − kH(0, l) − H(l, cp )(k + l) − p(p − 1) +l 2   k(k − 1) > 2pH(0, l) − kH(0, l) − H(l, cp )(k + l) − p(p − 1) +l 2   k(k − 1) = 2pl(4p + l) − kl(k(k − 1) + 1) − p p + + l (k + l) 2   k(k − 1) − p(p − 1) +l 2     k(k − 1) k(k − 1) > p2 6l − k − +p + l (1 − k − l) − kl(k(k − 1) + 1) . 2 2 Finally, note that the second and third therm have order O(p) and O(1) respec- tively. Therefore, because of (2) we have that for p large enough h. (0) − h. (cp ) > 0, that is, cp is more central than vertex 0. t u Second is the Density Axiom. For this case two cycles of the same size are connected through a bridge. By symmetry both end points of the bridge have the same centrality. What should happen if we increase the number of edges of one of the cycles until it becomes a clique? Well, the centrality of the endpoint connected to the cycle that is becoming a clique should also increase. Formally stated: Axiom 2: (Density axiom) Consider the graph Dk,p made by a k-clique and a p-cycle (p, k > 3) connected by a bridge uv, where u is a vertex of the clique and v one from the cycle. A centrality measure satisfies the density axiom if for k = p, u is strictly more central than v. Proof. First, remember definition 7 made for bridges and note that in this case Gu corresponds to the k-clique and Gv to the p-cycle. Also, note that a k-clique has exactly k(k − 1)/2 edges, while a p-cycle has p. Therefore, by using this fact and proposition 9 we have that k > 3 ∧ k = p =⇒ k 3 − 3k 2 > 0 ⇐⇒ k 3 − k 2 + k > 2k 2 + k ⇐⇒ k(k(k − 1) + 1) > k(2k + 1)   k(k − 1) ⇐⇒ k 2 + 1 > p(2p + 1) 2 ⇐⇒ |V (Gu )|(2|E(Gu )| + 1) > |V (Gv )|(2|E(Gv )| + 1) ⇐⇒ h. (u) < h. (v) that is, u is strictly more central than v. t u Finally, there is the Monotonicity Axiom. It states that when adding an edge to a graph that originally did not have it, the centrality of both endpoints should increase. Axiom 3: (Monotonicity axiom) Consider an arbitrary graph G = (V, E) (with |V | ≥ 2) and a pair of vertices u, v of G such that uv ∈ / E. A centrality measure satisfies the monotonicity axiom if when we add uv to G, the centrality of both vertices improves. Proof. Note that is enough to prove it for vertex u. Write e = uv and define G0 := (V, E ∪ e). Also, we will use the notation HG (u, v) and HG0 (u, v) for the old and new hitting times respectively, and we will do similarly for the centrality values h.G0 (u) and h.G (u). Note that because we are only adding an edge, the set of vertices remain the same for both graphs, and therefore, we can refer to it simply by V . 0 We have that ∀ w ∈ V \ {u}, HG (w, u) > HG (w, u). Indeed, whenever a 0 random walk steps into v, in G has the opportunity of going through e to reach u in only one more step, whereas in G it has to neccesarily take one more step into a neighbor of v, and then in the best case scenario, another one to reach u. Therefore, by using this we have that h. X X G0 (u) = HG0 (w, u) < HG (w, u) = h. G (u) w∈V w∈V w6=u w6=u that is, u has strictly better centrality in G0 than in G. t u 6 Conclusions We studied a notion of centrality based on random walks over non-directed graphs. Besides experimental evidence (that we do not show in this article) this notion has nice theoretical properties. Although in this paper we concentrated in proving that it satisfies the recently introduced axioms of centrality by Boldi-Vigna, the techniques used give an insight of their potential. In fact, it can be proved that our notion of centrality captures fine properties of central nodes in undirected graphs. In a future paper we will present these results. Acknowledgments. The authors thank funding to Millennium Nucleus Center for Semantic Web Research under Grant NC120004. References 1. Thad Huges & Daniel Ramge (2007). Lexical semantics relatedness with random graph walks. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp.581-589. 2. Joshua T. Abbott, Joseph L. Austerweil, Thomas L. Griffiths (2012). Human mem- ory search as a random walk in a semantic network. In Advances in Neural Infor- mation Processing Systems 25, pp.3050-3058. 3. Camilo Garrido Garcı́a (2013). Resúmenes Semiautomáticos de Conocimiento: caso de RDF. In Memoria para optar al tı́tulo de Ingeniero Civil en Computación, http://repositorio.uchile.cl/bitstream/handle/2250/113509/cf-garrido_ cg.pdf?sequence=1&isAllowed=y. 4. Linton C. Freeman (1978/79). Centrality in Social Networks Conceptual Clarifica- tion. In Social Networks 1, pp.2125-239. 5. Paolo Boldi, Sebastiano Vigna (2013). Axioms for Centrality. In CoRR, vol. abs/ 1308.2140. 6. L.Lovász (1993). Random Walks on Graphs; A Survey. In Boltai Soc., Math. Stud- ies 2, pp.1-46. 7. Joe Dong Noh, Heiko Rieger (2004). Random Walks on Complex Networks. In Physical Review Letters, Volume 92, Number 11. 8. Shravas K Rao, Finding Hitting Times in Various Graphs. 9. M.E.J. Newman (2005). A measure of betweenness centrality based on random walks. In Social Networks 27, pp.39-54. 7 Appendix Proposition 9. Let uv be a bridge of a connected graph G. Then h. (u) < h. (v) ⇐⇒ (2|E(Gu )| + 1)|V (Gu )| > (2|E(Gv )| + 1)|V (Gv )| Proof. Note that h. (u) is equal to X = H(w, u) w∈V (G) w6=u X X = H(w, u) + H(w, u) + H(v, u) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X X = H(w, u) + [H(w, v) + H(v, u)] + H(v, u) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X X = H(w, u) + H(w, v) + |V (Gv )|H(v, u) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X X = H(w, u) + H(w, v) + |V (Gv )|(2|E(Gv )| + 1) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X X < H(w, u) + H(w, v) + |V (Gu )|(2|E(Gu )| + 1) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X X = H(w, u) + H(w, v) + |V (Gu )|H(u, v) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X X = [H(w, u) + H(u, v)] + H(w, v) + H(u, v) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X X = H(w, v) + H(w, v) + H(u, v) w∈V (Gu ) w∈V (Gv ) w6=u w6=v X = H(w, v) w∈V (G) w6=v = h. (v) .u t