Studying new classes of graph metrics Pavel Chebotarev Russian Academy of Sciences: Institute of Control Sciences pavel4e@gmail.com GSI’2013 – Geometric Science of Information Paris – Ecole des Mines August 28, 2013 Pavel Chebotarev New classes of graph metrics Page 1 Classical graph distances 1 Shortest path distance 2 Weighted shortest path distance 3 Resistance distance Are other distances needed? Pavel Chebotarev New classes of graph metrics Page 2 Classical graph distances 1 Shortest path distance 2 Weighted shortest path distance 3 Resistance distance Are other distances needed? Pavel Chebotarev New classes of graph metrics Page 2 Distance Let M be an arbitrary set. A distance on M is a function d : M × M → R such that for all x, y, z ∈ M, 1. d(x, y) ≥ 0 2. d(x, y) = 0 iff x = y 3. d(x, y) = d(y, x) 4. d(x, y) + d(y, z) ≥ d(x, z) A shorter deﬁnition: d : M × M → R such that for all x, y, z ∈ M, 2. d(x, y) = 0 iff x = y 4 . d(x, y) + d(x, z) ≥ d(y, z) M.M. Deza, E. Deza, Encyclopedia of Distances, Springer, 2013. Pavel Chebotarev New classes of graph metrics Page 3 Distance Let M be an arbitrary set. A distance on M is a function d : M × M → R such that for all x, y, z ∈ M, 1. d(x, y) ≥ 0 2. d(x, y) = 0 iff x = y 3. d(x, y) = d(y, x) 4. d(x, y) + d(y, z) ≥ d(x, z) A shorter deﬁnition: d : M × M → R such that for all x, y, z ∈ M, 2. d(x, y) = 0 iff x = y 4 . d(x, y) + d(x, z) ≥ d(y, z) M.M. Deza, E. Deza, Encyclopedia of Distances, Springer, 2013. Pavel Chebotarev New classes of graph metrics Page 3 Distance Let M be an arbitrary set. A distance on M is a function d : M × M → R such that for all x, y, z ∈ M, 1. d(x, y) ≥ 0 2. d(x, y) = 0 iff x = y 3. d(x, y) = d(y, x) 4. d(x, y) + d(y, z) ≥ d(x, z) A shorter deﬁnition: d : M × M → R such that for all x, y, z ∈ M, 2. d(x, y) = 0 iff x = y 4 . d(x, y) + d(x, z) ≥ d(y, z) M.M. Deza, E. Deza, Encyclopedia of Distances, Springer, 2013. Pavel Chebotarev New classes of graph metrics Page 3 The shortest path distance 1 The shortest path distance on a graph G, ds(i, j) is... the length of a shortest path between i and j in G. A graph and its distance matrix 2 3 4 1 5 Ds (G) = 0 1 2 2 3 1 0 1 1 2 2 1 0 1 2 2 1 1 0 1 3 2 2 1 0 G F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, 1990. Pavel Chebotarev New classes of graph metrics Page 4 The shortest path distance 1 The shortest path distance on a graph G, ds(i, j) is... the length of a shortest path between i and j in G. A graph and its distance matrix 2 3 4 1 5 Ds (G) = 0 1 2 2 3 1 0 1 1 2 2 1 0 1 2 2 1 1 0 1 3 2 2 1 0 G F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, 1990. Pavel Chebotarev New classes of graph metrics Page 4 The shortest path distance 1 The shortest path distance on a graph G, ds(i, j) is... the length of a shortest path between i and j in G. A graph and its distance matrix 2 3 4 1 5 Ds (G) = 0 1 2 2 3 1 0 1 1 2 2 1 0 1 2 2 1 1 0 1 3 2 2 1 0 G F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, 1990. Pavel Chebotarev New classes of graph metrics Page 4 The weighted shortest path distance Let G be a weighted graph with weighted adjacency matrix A. The weights are positive. 2 The weighted shortest path distance: dws (i, j) = min π e∈E(π) e the minimum is taken over all paths π from i to j e = 1/we is the weight-based length of e (we is the weight) If we is the conductivity of e then e is the resistance of e. Pavel Chebotarev New classes of graph metrics Page 5 The weighted shortest path distance Let G be a weighted graph with weighted adjacency matrix A. The weights are positive. 2 The weighted shortest path distance: dws (i, j) = min π e∈E(π) e the minimum is taken over all paths π from i to j e = 1/we is the weight-based length of e (we is the weight) If we is the conductivity of e then e is the resistance of e. Pavel Chebotarev New classes of graph metrics Page 5 The weighted shortest path distance Let G be a weighted graph with weighted adjacency matrix A. The weights are positive. 2 The weighted shortest path distance: dws (i, j) = min π e∈E(π) e the minimum is taken over all paths π from i to j e = 1/we is the weight-based length of e (we is the weight) If we is the conductivity of e then e is the resistance of e. Pavel Chebotarev New classes of graph metrics Page 5 The resistance distance 3 The resistance distance d r(i, j) is the effective resistance between i and j in the electrical network corresponding to G. Gerald Subak-Sharpe was the ﬁrst to study this distance: G.E. Sharpe, Solution of the (m + 1)-terminal resistive network problem by means of metric geometry. In: Proc. First Asilomar Conference on Circuits and Systems, Paciﬁc Grove, CA (November 1967) 319–328. Pavel Chebotarev New classes of graph metrics Page 6 The resistance distance 3 The resistance distance d r(i, j) is the effective resistance between i and j in the electrical network corresponding to G. Gerald Subak-Sharpe was the ﬁrst to study this distance: G.E. Sharpe, Solution of the (m + 1)-terminal resistive network problem by means of metric geometry. In: Proc. First Asilomar Conference on Circuits and Systems, Paciﬁc Grove, CA (November 1967) 319–328. Pavel Chebotarev New classes of graph metrics Page 6 The resistance distance 3 The resistance distance d r(i, j) is the effective resistance between i and j in the electrical network corresponding to G. Gerald Subak-Sharpe was the ﬁrst to study this distance: G.E. Sharpe, Solution of the (m + 1)-terminal resistive network problem by means of metric geometry. In: Proc. First Asilomar Conference on Circuits and Systems, Paciﬁc Grove, CA (November 1967) 319–328. Pavel Chebotarev New classes of graph metrics Page 6 Rediscovering and review: A.D. Gvishiani, V.A. Gurvich, Metric and ultrametric spaces of resistances, Russian Math. Surveys 42 (1987) 235–236. D.J. Klein, M. Randi´c, Resistance distance, J. Math. Chem. 12 (1993) 81–95. F. Harary: Electric metric A nice paper: R.B. Bapat, Resistance distance in graphs, Math. Student 68 (1999) 87–98. A short review is in: Y. Yang, D.J. Klein, A recursion formula for resistance distances and its applications, DAM, 2013. In press. Pavel Chebotarev New classes of graph metrics Page 7 Rediscovering and review: A.D. Gvishiani, V.A. Gurvich, Metric and ultrametric spaces of resistances, Russian Math. Surveys 42 (1987) 235–236. D.J. Klein, M. Randi´c, Resistance distance, J. Math. Chem. 12 (1993) 81–95. F. Harary: Electric metric A nice paper: R.B. Bapat, Resistance distance in graphs, Math. Student 68 (1999) 87–98. A short review is in: Y. Yang, D.J. Klein, A recursion formula for resistance distances and its applications, DAM, 2013. In press. Pavel Chebotarev New classes of graph metrics Page 7 Rediscovering and review: A.D. Gvishiani, V.A. Gurvich, Metric and ultrametric spaces of resistances, Russian Math. Surveys 42 (1987) 235–236. D.J. Klein, M. Randi´c, Resistance distance, J. Math. Chem. 12 (1993) 81–95. F. Harary: Electric metric A nice paper: R.B. Bapat, Resistance distance in graphs, Math. Student 68 (1999) 87–98. A short review is in: Y. Yang, D.J. Klein, A recursion formula for resistance distances and its applications, DAM, 2013. In press. Pavel Chebotarev New classes of graph metrics Page 7 Rediscovering and review: A.D. Gvishiani, V.A. Gurvich, Metric and ultrametric spaces of resistances, Russian Math. Surveys 42 (1987) 235–236. D.J. Klein, M. Randi´c, Resistance distance, J. Math. Chem. 12 (1993) 81–95. F. Harary: Electric metric A nice paper: R.B. Bapat, Resistance distance in graphs, Math. Student 68 (1999) 87–98. A short review is in: Y. Yang, D.J. Klein, A recursion formula for resistance distances and its applications, DAM, 2013. In press. Pavel Chebotarev New classes of graph metrics Page 7 Rediscovering and review: A.D. Gvishiani, V.A. Gurvich, Metric and ultrametric spaces of resistances, Russian Math. Surveys 42 (1987) 235–236. D.J. Klein, M. Randi´c, Resistance distance, J. Math. Chem. 12 (1993) 81–95. F. Harary: Electric metric A nice paper: R.B. Bapat, Resistance distance in graphs, Math. Student 68 (1999) 87–98. A short review is in: Y. Yang, D.J. Klein, A recursion formula for resistance distances and its applications, DAM, 2013. In press. Pavel Chebotarev New classes of graph metrics Page 7 Resistance distance: Connections The resistance distance is proportional to the commute-time distance in the corresponding Markov chain. It is expressed as follows: d r (i, j) = + ii + + jj − 2 + ij , where ( + ij )n×n = L+ is the Moore-Penrose pseudoinverse of L, L = diag(A1) − A is the Laplacian matrix of G. Here, diag(A1) is the matrix of weighted vertex degrees. Pavel Chebotarev New classes of graph metrics Page 8 Resistance distance: Connections The resistance distance is proportional to the commute-time distance in the corresponding Markov chain. It is expressed as follows: d r (i, j) = + ii + + jj − 2 + ij , where ( + ij )n×n = L+ is the Moore-Penrose pseudoinverse of L, L = diag(A1) − A is the Laplacian matrix of G. Here, diag(A1) is the matrix of weighted vertex degrees. Pavel Chebotarev New classes of graph metrics Page 8 Example For any tree, the resistance distance coincides with the shortest path distance! For our graph: 2 3 4 1 5 Ds (G) = 0 1 2 2 3 1 0 1 1 2 2 1 0 1 2 2 1 1 0 1 3 2 2 1 0 ; Dr (G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 G Pavel Chebotarev New classes of graph metrics Page 9 Example For any tree, the resistance distance coincides with the shortest path distance! For our graph: 2 3 4 1 5 Ds (G) = 0 1 2 2 3 1 0 1 1 2 2 1 0 1 2 2 1 1 0 1 3 2 2 1 0 ; Dr (G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 G Pavel Chebotarev New classes of graph metrics Page 9 A combinatorial interpretation A combinatorial interpretation of the resistance distance 2 3 4 1 5 Dr(G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 d r(i, j) = f[2](i,j) T Pavel Chebotarev New classes of graph metrics Page 10 A combinatorial interpretation A combinatorial interpretation of the resistance distance 2 3 4 1 5 Dr(G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 d r(i, j) = f[2](i,j) T Pavel Chebotarev New classes of graph metrics Page 10 Connection with the graph structure 2 3 4 1 5 Dr (G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 d r (1, 2) + d r (2, 5) = d r (1, 5) d r (1, 3) + d r (3, 5) > d r (1, 5) i j k [i−j−k] Deﬁnition d(·, ·): V2 → R is cutpoint additive provided that d(i, j) + d(j, k) = d(i, k) iff all i → k paths pass through j. Pavel Chebotarev New classes of graph metrics Page 11 Connection with the graph structure 2 3 4 1 5 Dr (G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 d r (1, 2) + d r (2, 5) = d r (1, 5) d r (1, 3) + d r (3, 5) > d r (1, 5) i j k [i−j−k] Deﬁnition d(·, ·): V2 → R is cutpoint additive provided that d(i, j) + d(j, k) = d(i, k) iff all i → k paths pass through j. Pavel Chebotarev New classes of graph metrics Page 11 Connection with the graph structure 2 3 4 1 5 Dr (G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 d r (1, 2) + d r (2, 5) = d r (1, 5) d r (1, 3) + d r (3, 5) > d r (1, 5) i j k [i−j−k] Deﬁnition d(·, ·): V2 → R is cutpoint additive provided that d(i, j) + d(j, k) = d(i, k) iff all i → k paths pass through j. Pavel Chebotarev New classes of graph metrics Page 11 Connection with the graph structure 2 3 4 1 5 Dr (G) = 0 1 5 3 5 3 8 3 1 0 2 3 2 3 5 3 5 3 2 3 0 2 3 5 3 5 3 2 3 2 3 0 1 8 3 5 3 5 3 1 0 d r (1, 2) + d r (2, 5) = d r (1, 5) d r (1, 3) + d r (3, 5) > d r (1, 5) i j k [i−j−k] Deﬁnition d(·, ·): V2 → R is cutpoint additive provided that d(i, j) + d(j, k) = d(i, k) iff all i → k paths pass through j. Pavel Chebotarev New classes of graph metrics Page 11 As we could conjecture... Theorem (Gvishiani, Gurvich, 1992) The electric metric is cutpoint additive. However... The shortest path distance only satisﬁes the “if” part: d(i, j) + d(j, k) = d(i, k) does not imply [i−j−k]: 1 + 1 = 2 Observation The Euclidean distance satisﬁes a similar condition resulting by replacing “path” by “line segment”. Pavel Chebotarev New classes of graph metrics Page 12 As we could conjecture... Theorem (Gvishiani, Gurvich, 1992) The electric metric is cutpoint additive. However... The shortest path distance only satisﬁes the “if” part: d(i, j) + d(j, k) = d(i, k) does not imply [i−j−k]: 1 + 1 = 2 Observation The Euclidean distance satisﬁes a similar condition resulting by replacing “path” by “line segment”. Pavel Chebotarev New classes of graph metrics Page 12 As we could conjecture... Theorem (Gvishiani, Gurvich, 1992) The electric metric is cutpoint additive. However... The shortest path distance only satisﬁes the “if” part: d(i, j) + d(j, k) = d(i, k) does not imply [i−j−k]: 1 + 1 = 2 Observation The Euclidean distance satisﬁes a similar condition resulting by replacing “path” by “line segment”. Pavel Chebotarev New classes of graph metrics Page 12 Proximity measures Let’s think of proximity measures... Pavel Chebotarev New classes of graph metrics Page 13 Applications World Wide Web Social networks Semantic networks Transport networks Other... ... Cry: “Measure us!” So functions that “measure” networks are necessary ... including proximity measures Pavel Chebotarev New classes of graph metrics Page 14 Applications World Wide Web Social networks Semantic networks Transport networks Other... ... Cry: “Measure us!” So functions that “measure” networks are necessary ... including proximity measures Pavel Chebotarev New classes of graph metrics Page 14 Applications World Wide Web Social networks Semantic networks Transport networks Other... ... Cry: “Measure us!” So functions that “measure” networks are necessary ... including proximity measures Pavel Chebotarev New classes of graph metrics Page 14 Applications World Wide Web Social networks Semantic networks Transport networks Other... ... Cry: “Measure us!” So functions that “measure” networks are necessary ... including proximity measures Pavel Chebotarev New classes of graph metrics Page 14 Proximity measures Spanning forest measures Reliability measures Path measures Walk measures Pavel Chebotarev New classes of graph metrics Page 15 The spanning forest measure Q = (I + L)−1 Pavel Chebotarev New classes of graph metrics Page 16 The spanning forest measure Q = (I + L)−1 Q = (qij)n×n Matrix Forest Theorem (Ch. & Shamis, ’95) qij = fij f , where f is the number of spanning rooted forests in G; fij is the number of such of them that have i in a tree rooted at j. Pavel Chebotarev New classes of graph metrics Page 16 The spanning forest measure Q = (I + L)−1 Q = (qij)n×n Matrix Forest Theorem (Ch. & Shamis, ’95) qij = fij f , where f is the number of spanning rooted forests in G; fij is the number of such of them that have i in a tree rooted at j. Q is a proximity measure having natural properties. Pavel Chebotarev New classes of graph metrics Page 16 The spanning forest measure Q = (I + L)−1 Q = (qij)n×n Matrix Forest Theorem (Ch. & Shamis, ’95) qij = fij f , where f is the number of spanning rooted forests in G; fij is the number of such of them that have i in a tree rooted at j. Q is a proximity measure having natural properties. For networks, the number of forests is replaced by the weight of forests. Pavel Chebotarev New classes of graph metrics Page 16 The spanning forest measure Q = (I + L)−1 Q = (qij)n×n Matrix Forest Theorem (Ch. & Shamis, ’95) qij = fij f , where f is the number of spanning rooted forests in G; fij is the number of such of them that have i in a tree rooted at j. Q is a proximity measure having natural properties. For networks, the number of forests is replaced by the weight of forests. The weight is the product of edge weights. Pavel Chebotarev New classes of graph metrics Page 16 Transitional measures Theorem (a property of the forest measure) The matrix Q satisﬁes: qij qjk ≤ Pavel Chebotarev New classes of graph metrics Page 17 Transitional measures Theorem (a property of the forest measure) The matrix Q satisﬁes: qij qjk ≤ qik qjj Pavel Chebotarev New classes of graph metrics Page 17 Transitional measures Theorem (a property of the forest measure) The matrix Q satisﬁes: qij qjk ≤ qik qjj (transition inequality) and qij qjk = Pavel Chebotarev New classes of graph metrics Page 17 Transitional measures Theorem (a property of the forest measure) The matrix Q satisﬁes: qij qjk ≤ qik qjj (transition inequality) and qij qjk = qik qjj iff all paths from i to k in G contain j (bottleneck identity). Pavel Chebotarev New classes of graph metrics Page 17 Transitional measures Theorem (a property of the forest measure) The matrix Q satisﬁes: qij qjk ≤ qik qjj (transition inequality) and qij qjk = qik qjj iff all paths from i to k in G contain j (bottleneck identity). Deﬁnition In this case we say that Q determines a transitional measure on G. Pavel Chebotarev New classes of graph metrics Page 17 Transitional Measures A matrix S =(sij)∈Rn×n satisﬁes the transition inequality if for all i, j, k = 1, . . . , n, sij sjk ≤ (1) i j k Pavel Chebotarev New classes of graph metrics Page 18 Transitional Measures A matrix S =(sij)∈Rn×n satisﬁes the transition inequality if for all i, j, k = 1, . . . , n, sij sjk ≤ sik sjj. (1) i j k Pavel Chebotarev New classes of graph metrics Page 18 Transitional Measures A matrix S =(sij)∈Rn×n satisﬁes the transition inequality if for all i, j, k = 1, . . . , n, sij sjk ≤ sik sjj. (1) i j k Is there any connection between transitional measures and cutpoint additive distances? Pavel Chebotarev New classes of graph metrics Page 18 The connection reliability measure Let the edge weight wij ∈ (0, 1] be the intactness probability of the (i, j) edge. Pavel Chebotarev New classes of graph metrics Page 19 The connection reliability measure Let the edge weight wij ∈ (0, 1] be the intactness probability of the (i, j) edge. Deﬁnition Let pij be the i → j connection reliability, i.e., the probability that at least one path from i to j remains intact, provided that the edge failures are independent. P = (pij) is the matrix of pairwise connection reliabilities. Pavel Chebotarev New classes of graph metrics Page 19 Is the connection reliability a transitional measure? Theorem For any graph G with edge weights wp ij ∈ (0, 1], the matrix P = (pij) of connection reliabilities determines a transitional measure on G. Pavel Chebotarev New classes of graph metrics Page 20 Is the connection reliability a transitional measure? Theorem For any graph G with edge weights wp ij ∈ (0, 1], the matrix P = (pij) of connection reliabilities determines a transitional measure on G. A representation of the connection reliabilities1 pij = k Pr(Pk ) − k 0 such that for every α ∈ (0, α0), the matrix Pα = (pα ij ) of α-path proximities determines a transitional measure on G. Pavel Chebotarev New classes of graph metrics Page 21 The walk-counting proximity measures Walks and paths... The number of walks is inﬁnite. Pavel Chebotarev New classes of graph metrics Page 22 The walk-counting proximity measures Walks and paths... The number of walks is inﬁnite. G → Gt transformation by multiplying edge weights by t > 0 The weight of a walk is the product of its edge weights. Pavel Chebotarev New classes of graph metrics Page 22 The walk-counting proximity measures Walks and paths... The number of walks is inﬁnite. G → Gt transformation by multiplying edge weights by t > 0 The weight of a walk is the product of its edge weights. Deﬁnition Let rt ij be the total weight of all i → j walks in Gt if it is ﬁnite. Pavel Chebotarev New classes of graph metrics Page 22 The walk-counting proximity measures Walks and paths... The number of walks is inﬁnite. G → Gt transformation by multiplying edge weights by t > 0 The weight of a walk is the product of its edge weights. Deﬁnition Let rt ij be the total weight of all i → j walks in Gt if it is ﬁnite. Rt = (rt ij) is the matrix of t-walk proximities in G (if it is ﬁnite). Leo Katz, A new status index derived from sociometric analysis, Psychometrika 18 (1953) 39–43. Pavel Chebotarev New classes of graph metrics Page 22 The walk proximity measures www. .com uses this index (which generalizes PageRank). Pavel Chebotarev New classes of graph metrics Page 23 The walk proximity measures www. .com uses this index (which generalizes PageRank). Computation of Rt : (tA)k provides the total weights of k-length walks in G Pavel Chebotarev New classes of graph metrics Page 23 The walk proximity measures www. .com uses this index (which generalizes PageRank). Computation of Rt : (tA)k provides the total weights of k-length walks in G Rt = (rt ij) = ∞ k=0 (tA)k , A is the weighted adjacency matrix. Pavel Chebotarev New classes of graph metrics Page 23 The walk proximity measures www. .com uses this index (which generalizes PageRank). Computation of Rt : (tA)k provides the total weights of k-length walks in G Rt = (rt ij) = ∞ k=0 (tA)k , A is the weighted adjacency matrix. Observation (corollary of Frobenius’ theorem) Rt is ﬁnite iff t < ρ−1 (ρ is the spectral radius of A). In this case, Rt = (I − tA)−1. Pavel Chebotarev New classes of graph metrics Page 23 Walks determine a transitional measure! For our example, ∞ k=0 (1A)k is inﬁnite. 2 3 4 1 5 R0.4 = ∞ k=0 (0.4·A)k ≈ 5.63 5.94 4.34 4.90 1.96 5.94 8.92 6.50 7.34 2.94 4.34 6.50 5.98 5.94 2.38 4.90 7.34 5.94 7.52 3.01 1.96 2.94 2.38 3.01 2.20 . A measure of proximity Pavel Chebotarev New classes of graph metrics Page 24 Walks determine a transitional measure! For our example, ∞ k=0 (1A)k is inﬁnite. 2 3 4 1 5 R0.4 = ∞ k=0 (0.4·A)k ≈ 5.63 5.94 4.34 4.90 1.96 5.94 8.92 6.50 7.34 2.94 4.34 6.50 5.98 5.94 2.38 4.90 7.34 5.94 7.52 3.01 1.96 2.94 2.38 3.01 2.20 . A measure of proximity t = 0.4 is the proportion of counting shorter and longer walks Pavel Chebotarev New classes of graph metrics Page 24 Walks determine a transitional measure! For our example, ∞ k=0 (1A)k is inﬁnite. 2 3 4 1 5 R0.4 = ∞ k=0 (0.4·A)k ≈ 5.63 5.94 4.34 4.90 1.96 5.94 8.92 6.50 7.34 2.94 4.34 6.50 5.98 5.94 2.38 4.90 7.34 5.94 7.52 3.01 1.96 2.94 2.38 3.01 2.20 . A measure of proximity t = 0.4 is the proportion of counting shorter and longer walks Theorem For any G, the matrix Rt with 0 < t < ρ−1 , where ρ is the spectral radius of A, determines a transitional measure on G. Pavel Chebotarev New classes of graph metrics Page 24 Walks determine a transitional measure! For our example, ∞ k=0 (1A)k is inﬁnite. 2 3 4 1 5 R0.4 = ∞ k=0 (0.4·A)k ≈ 5.63 5.94 4.34 4.90 1.96 5.94 8.92 6.50 7.34 2.94 4.34 6.50 5.98 5.94 2.38 4.90 7.34 5.94 7.52 3.01 1.96 2.94 2.38 3.01 2.20 . A measure of proximity t = 0.4 is the proportion of counting shorter and longer walks Theorem For any G, the matrix Rt with 0 < t < ρ−1 , where ρ is the spectral radius of A, determines a transitional measure on G. r12 · r24 = r14 · r22 : 5.94 · 7.34 ≈ 4.90 · 8.92 (bottleneck identity). Pavel Chebotarev New classes of graph metrics Page 24 Maybe all proximity measures are transitional measures... Of course not. Are not: The path measure with a large enough α; Pavel Chebotarev New classes of graph metrics Page 25 Maybe all proximity measures are transitional measures... Of course not. Are not: The path measure with a large enough α; The communicability measure: eA. E. Estrada, The communicability distance in graphs, Linear Algebra and its Applications 436 (2012) 4317-4328. Pavel Chebotarev New classes of graph metrics Page 25 Maybe all proximity measures are transitional measures... Of course not. Are not: The path measure with a large enough α; The communicability measure: eA. E. Estrada, The communicability distance in graphs, Linear Algebra and its Applications 436 (2012) 4317-4328. In fact, this property is not typical. Pavel Chebotarev New classes of graph metrics Page 25 Maybe all proximity measures are transitional measures... Of course not. Are not: The path measure with a large enough α; The communicability measure: eA. E. Estrada, The communicability distance in graphs, Linear Algebra and its Applications 436 (2012) 4317-4328. In fact, this property is not typical. Is there any connection between transitional measures and cutpoint additive distances? Pavel Chebotarev New classes of graph metrics Page 25 Central theorem The transformation theorem If S =(sij )n×n determines a transitional measure for some graph G and has positive off-diagonal entries, then D = (dij )n×n deﬁned by d(i, j) = −γ ln sij sii sjj , i, j = 1, . . . , n, γ > 0 (2) is the matrix of a cutpoint additive distance on V(Γ). Pavel Chebotarev New classes of graph metrics Page 26 Central theorem The transformation theorem If S =(sij )n×n determines a transitional measure for some graph G and has positive off-diagonal entries, then D = (dij )n×n deﬁned by d(i, j) = −γ ln sij sii sjj , i, j = 1, . . . , n, γ > 0 (2) is the matrix of a cutpoint additive distance on V(Γ). Corollary For any connected G, the matrices of: walk weights path weights with a small enough α the weights of spanning forests connection reliabilities produce cutpoint additive metrics by applying the logarithmic cosine transform (2). Pavel Chebotarev New classes of graph metrics Page 26 Logarithmic cosine transform Transitional measures → cutpoint additive distances Pavel Chebotarev New classes of graph metrics Page 27 The properties of Walk distances “Topological” and matrix representations Pavel Chebotarev New classes of graph metrics Page 28 Walk distances (an example) For our graph, the logarithmic cosine transform gives: 2 3 4 1 5 D0.3 ≈ 0 1.18 2.19 2.17 3.59 1.18 0 1.01 0.98 2.40 2.19 1.01 0 1.02 2.44 2.17 0.98 1.02 0 1.42 3.59 2.40 2.44 1.42 0 . Pavel Chebotarev New classes of graph metrics Page 29 Walk distances (an example) For our graph, the logarithmic cosine transform gives: 2 3 4 1 5 D0.3 ≈ 0 1.18 2.19 2.17 3.59 1.18 0 1.01 0.98 2.40 2.19 1.01 0 1.02 2.44 2.17 0.98 1.02 0 1.42 3.59 2.40 2.44 1.42 0 . Here, d(2, 4) 0 Pavel Chebotarev New classes of graph metrics Page 43 The e-Walk distances (a different family) w(α) = w ρ e− 1 αw , α > 0 The construction is similar: Construction of the family deW α (i, j) of e-Walk distances 1. Rα = ∞ k=0 (A(α))k = (I − A(α))−1 2. deW α (i, j) = −θα α ln rij rii rjj θα is the normalizing factor. Pavel Chebotarev New classes of graph metrics Page 43 Asymptotic of the e-Walk distances Theorem (on e-Walk distances as α → 0+ ) For any vertices i, j ∈ V(G), lim α→0+ deW α (i, j) = dws (i, j), where dws (·, ·) is the weighted shortest path distance. Pavel Chebotarev New classes of graph metrics Page 44 Asymptotic of the e-Walk distances Theorem (on e-Walk distances as α → 0+ ) For any vertices i, j ∈ V(G), lim α→0+ deW α (i, j) = dws (i, j), where dws (·, ·) is the weighted shortest path distance. Theorem (on e-Walk distances as α → ∞) For any vertices i, j ∈ V(G) such that j = i, lim α→∞ deW α (i, j) = θ∞ 2 p−1 i (ρI − A¯¯)−1 ˇA¯ i + p−1 j (ρI − A¯ı¯ı)−1 ˇA¯ı j p, where p is the Perron vector of A, ˇA = (ˇaij )n×n results from A by replacing the nonzero entries by 1, ˇA¯ı is ˇA with the ith row removed. Pavel Chebotarev New classes of graph metrics Page 44 The Long e-Walk distance Pavel Chebotarev New classes of graph metrics Page 45 The Long e-Walk distance Deﬁne the Long e-Walk distance: d LeW (i, j) = lim α→∞ deW α (i, j), i, j ∈ V(G) Pavel Chebotarev New classes of graph metrics Page 46 A “topological” expression for the Long e-Walk distance Theorem For any vertices i, j ∈ V(G) such that i = j, d LeW (i, j) = θ∞ 2ρ (c i(j) + c j(i) ), where c i(j) is the weight of Ci(j), which is a set of speciﬁc “cycles with a jump”. Pavel Chebotarev New classes of graph metrics Page 47 A relationship between d LeW (i, j) and d LW (i, j) Theorem If θ∞ = 2 n · pT (A/ρ)p pTˇAp , then d LeW (i, j) = d LW (i, j), i, j ∈ V(G). Pavel Chebotarev New classes of graph metrics Page 48 Logarithmic forest distances ...as a special case of walk distances Pavel Chebotarev New classes of graph metrics Page 49 Logarithmic forest distances as a subclass of walk distances 1. Qα = (I + Lα)−1, where Lα =diag(Aα1)−Aα and Aα are the Laplacian and weighted adjacency matrices of the graph Gα that differs from G by the edge weights: wα = ϕα(w). The logarithmic forest distances: 2. dα(i, j) = −0.5θ ln qij(α) qii(α) qjj(α) Pavel Chebotarev New classes of graph metrics Page 50 Logarithmic forest distances as a subclass of walk distances 1. Qα = (I + Lα)−1, where Lα =diag(Aα1)−Aα and Aα are the Laplacian and weighted adjacency matrices of the graph Gα that differs from G by the edge weights: wα = ϕα(w). The logarithmic forest distances: 2. dα(i, j) = −0.5θ ln qij(α) qii(α) qjj(α) The marginal cases of the logarithmic forest distance are the shortest path distance and the resistance distance. Pavel Chebotarev New classes of graph metrics Page 50 The logarithmic forest distances are walk distances Theorem (actually, a sketch of the theorem) For any connected graph G, the family of logarithmic forest distances with any edge weight transformation ϕα(w) coincides with a certain family of modiﬁed walk distances obtained through balancing the graphs Gα by loops. Pavel Chebotarev New classes of graph metrics Page 51 The logarithmic forest distances are walk distances Theorem (actually, a sketch of the theorem) For any connected graph G, the family of logarithmic forest distances with any edge weight transformation ϕα(w) coincides with a certain family of modiﬁed walk distances obtained through balancing the graphs Gα by loops. G is a balance-graph of G G Pavel Chebotarev New classes of graph metrics Page 51 The logarithmic forest distances are walk distances Theorem (actually, a sketch of the theorem) For any connected graph G, the family of logarithmic forest distances with any edge weight transformation ϕα(w) coincides with a certain family of modiﬁed walk distances obtained through balancing the graphs Gα by loops. G is a balance-graph of G 2 2 1 1 G G Pavel Chebotarev New classes of graph metrics Page 51 Is there any connection between the long walk distance and the resistance distance? Pavel Chebotarev New classes of graph metrics Page 52 The resistance distance is also a long walk distance Corollary For any connected G, the resistance distance in G coincides with the long walk distance d LW (i, j) in G, where G is any balance-graph of G. Pavel Chebotarev New classes of graph metrics Page 53 The resistance distance is also a long walk distance Corollary For any connected G, the resistance distance in G coincides with the long walk distance d LW (i, j) in G, where G is any balance-graph of G. G is a balance-graph of G 2 2 1 1 G G The resistance distance on G coincide with the long walk distances on G . Pavel Chebotarev New classes of graph metrics Page 53 A novel expression for the resistance distance Corollary For any connected graph G on n vertices, let L be the Laplacian matrix of G and let d r(·, ·) be the resistance distance on V(G). Then for any i, j ∈ V(G) such that j = i, d r (i, j) = n−1 (L¯¯)−1 i + (L¯ı¯ı)−1 j 1 holds, where 1 is the vector of n − 1 ones and (L¯¯)−1 i is the ith row of the inverse principal submatrix L¯¯. Pavel Chebotarev New classes of graph metrics Page 54 An inverse simulation Is the long walk distance equal to the resistance distance in a certain modiﬁed graph? Pavel Chebotarev New classes of graph metrics Page 55 A “resistance” representation of the long walk distance Theorem Suppose that: An×n is the weighted adjacency matrix of a connected graph G p is the Perron vector of A A = P AP , where P = diag(p ) and p = √ n p 2 p Then the long walk distance in G coincides with the resistance distance in G whose weighted adjacency matrix is A . Pavel Chebotarev New classes of graph metrics Page 56 Are there SIMPLE matrix representations of the long walk distance? Pavel Chebotarev New classes of graph metrics Page 57 Simple representations of the long walk distance Corollary (of the previous theorem) d LW (i, j) = det(L¯ı¯ı)¯¯ det L¯ı¯ı , j = i, d LW (i, j) = + ii + + jj − 2 + ij , where L + =( + ij ) is the pseudoinverse of L = P (ρI − A)P . Pavel Chebotarev New classes of graph metrics Page 58 Simple representations of the long walk distance Corollary (of the previous theorem) d LW (i, j) = det(L¯ı¯ı)¯¯ det L¯ı¯ı , j = i, d LW (i, j) = + ii + + jj − 2 + ij , where L + =( + ij ) is the pseudoinverse of L = P (ρI − A)P . Remark. Since L is symmetric and irreducible, L + coincides with the group inverse L# = (L + J)−1 − J, where J = 1 n 11T . Pavel Chebotarev New classes of graph metrics Page 58 Expressions for the long walk distance in terms of B = ρI − A Theorem (Ch., R.Bapat, R.Balaji) d LW (i, j) = (np2 j )−1 · det(B¯ı¯ı)¯¯ det B¯ı¯ı , j = i, d LW (i, j) = zT (i, j)B+ z(i, j) n , where B = ρI − A, p = p/ p 2, and z(i, j) is the n-vector whose ith element is 1/pi , jth element is −1/pj , and the other elements are 0. B = ρI − A is the para-Laplacian matrix of G. Pavel Chebotarev New classes of graph metrics Page 59 Cutpoint additive metrics on P4 Pavel Chebotarev New classes of graph metrics Page 60 Cutpoint additive metrics on P4 On the next slide, the distances are listed in descending order of d(1, 4). Each picture presents the projection of the distance-obeying polygon onto the plane parallel to the line segments (1, 4) and (2, 3). Pavel Chebotarev New classes of graph metrics Page 60 Cutpoint non-additive metrics on P4 Pavel Chebotarev New classes of graph metrics Page 61 Classical graph distances 1 Shortest path distance 2 Weighted shortest path distance 3 Resistance distance Are other distances needed? Pavel Chebotarev New classes of graph metrics Page 62 Classical graph distances 1 Shortest path distance 2 Weighted shortest path distance 3 Resistance distance Are other distances needed? Pavel Chebotarev New classes of graph metrics Page 62 Are new graph metrics needed in practice? Yen, Saerens, Mantrach, Shimbo (2008) performed machine clustering with noisy data and used a parametric family of dissimilarity measures that reduce to the shortest path and the resistance distance at the marginal values of the parameter and are not distances in general. Pavel Chebotarev New classes of graph metrics Page 63 Are new graph metrics needed in practice? Yen, Saerens, Mantrach, Shimbo (2008) performed machine clustering with noisy data and used a parametric family of dissimilarity measures that reduce to the shortest path and the resistance distance at the marginal values of the parameter and are not distances in general. “The results obtained for intermediate values of θ are usually better than those obtained with the commute-time and the shortest-path kernels.” Pavel Chebotarev New classes of graph metrics Page 63 Are new graph metrics needed in practice? Yen, Saerens, Mantrach, Shimbo (2008) performed machine clustering with noisy data and used a parametric family of dissimilarity measures that reduce to the shortest path and the resistance distance at the marginal values of the parameter and are not distances in general. “The results obtained for intermediate values of θ are usually better than those obtained with the commute-time and the shortest-path kernels.” “We study the behavior of the commute distance as the size of the underlying graph increases. We prove that the commute distance converges to an expression that does not take into account the structure of the graph at all and that is completely meaningless as a distance function on the graph. Consequently, the use of the commute distance for machine learning purposes is strongly discouraged for large graphs and in high dimensions.” (von Luxburg, Radl, Hein, 2010) Pavel Chebotarev New classes of graph metrics Page 63 Are new graph metrics needed in practice? Yen, Saerens, Mantrach, Shimbo (2008) performed machine clustering with noisy data and used a parametric family of dissimilarity measures that reduce to the shortest path and the resistance distance at the marginal values of the parameter and are not distances in general. “The results obtained for intermediate values of θ are usually better than those obtained with the commute-time and the shortest-path kernels.” “We study the behavior of the commute distance as the size of the underlying graph increases. We prove that the commute distance converges to an expression that does not take into account the structure of the graph at all and that is completely meaningless as a distance function on the graph. Consequently, the use of the commute distance for machine learning purposes is strongly discouraged for large graphs and in high dimensions.” (von Luxburg, Radl, Hein, 2010) There is a strong demand for alternative graph distances. Pavel Chebotarev New classes of graph metrics Page 63 Finally, some problems Study the the family of p-resistance distances by Alamgir and von Luxburg (2011). Pavel Chebotarev New classes of graph metrics Page 64 Finally, some problems Study the the family of p-resistance distances by Alamgir and von Luxburg (2011). Study links of the e-distances with entropy, free energy, etc. Pavel Chebotarev New classes of graph metrics Page 64 Finally, some problems Study the the family of p-resistance distances by Alamgir and von Luxburg (2011). Study links of the e-distances with entropy, free energy, etc. Study the new distances in the context of clustering on large random graphs in high dimensions. Pavel Chebotarev New classes of graph metrics Page 64 Finally, some problems Study the the family of p-resistance distances by Alamgir and von Luxburg (2011). Study links of the e-distances with entropy, free energy, etc. Study the new distances in the context of clustering on large random graphs in high dimensions. Study connections of the new distances with Ricci curvature on graphs. Pavel Chebotarev New classes of graph metrics Page 64 Thank you! Pavel Chebotarev New classes of graph metrics Page 65 Some references F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, Redwood City, CA, 1990. P.Yu. Chebotarev, E.V. Shamis. On proximity measures for graph vertices, Automation and Remote Control 59 (1998) No. 10, Part 2 1443–1459. P. Chebotarev, The walk distances in graphs, Discr. Appl. Math. 160 (2012) 1484-1500. P. Chebotarev, The graph bottleneck identity, Adv. Appl. Math. 47 (2011) 403–413. P. Chebotarev, A Class of graph-geodetic distances generalizing the shortest-path and the resistance distances, Discr. Appl. Math. 159 (2011) 295–302. P. Chebotarev, R. Agaev, Forest matrices around the Laplacian matrix, Linear Algebra Appl. 356 (2002) 253–274. P. Chebotarev, E. Shamis, The forest metrics for graph vertices, Electron. Notes Discrete Math. 11 (2002) 98–107. H. Chen, F. Zhang, Resistance distance and the normalized Laplacian spectrum, Discrete Appl. Math. 155 (2007) 654–661. R.L. Graham, A.J. Hoffman, H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory 1 (1977) 85–88. A.D. Gvishiani, V.A. Gurvich, Dynamical Classiﬁcation Problems and Convex Programming in Applications, Nauka (Science), Moscow, 1992 (in Russian). U. von Luxburg, A. Radl, M. Hein, Getting lost in space: Large sample analysis of the commute distance, Working paper of Saarland University, Saarbrücken, Germany, 2010. L. Yen, M. Saerens, A. Mantrach, M. Shimbo, A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances, 14th ACM SIGKDD Intern. Conf. on Knowledge Discovery & Data Mining, 2008, pp. 785–793. Pavel Chebotarev New classes of graph metrics Page 66 Deﬁnitions: hitting walk, cycle, commute cycle A hitting v0 → vm walk is a v0 → vm walk containing only one occurrence of vm. A v0 → vm walk is called a v0 → v0 cycle if1 vm = v0. A v0 → v0 cycle is called a v0 vm commute cycle if it contains vm and at most two occurrences of v0. 1 Such a walk is also called a closed walk. Pavel Chebotarev New classes of graph metrics Page 67 A balance-graph of G G is a balance-graph of G if G is obtained from G by attaching some loops and assigning the loop weights that provide G with uniform weighted vertex degrees. Balancing G by loops means constructing a balance-graph of G. Pavel Chebotarev New classes of graph metrics Page 68 On the simplest logarithmic forest distances Corollary For any connected graph G, if ϕα(w) = αw, then the family of logarithmic forest distances with A = R+ coincides with the family of walk distances calculated for any balance-graph of G. Pavel Chebotarev New classes of graph metrics Page 69 On the simplest logarithmic forest distances Corollary For any connected graph G, if ϕα(w) = αw, then the family of logarithmic forest distances with A = R+ coincides with the family of walk distances calculated for any balance-graph of G. G is a balance-graph of G 2 2 1 1 G G The simplest logarithmic forest distances on G coincide with the walk distances on G . Pavel Chebotarev New classes of graph metrics Page 69