## Studying new classes of graph metrics

28/08/2013**Auteurs :**Pavel Chebotarev

**Publication**GSI2013 - Geometric Science of Information

**OAI :**oai:www.see.asso.fr:2552:4888

**DOI :**

<resource xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://datacite.org/schema/kernel-4" xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd"> <identifier identifierType="DOI">10.23723/2552/4888</identifier><creators><creator><creatorName>Pavel Chebotarev</creatorName></creator></creators><titles> <title>Studying new classes of graph metrics</title></titles> <publisher>SEE</publisher> <publicationYear>2013</publicationYear> <resourceType resourceTypeGeneral="Text">Text</resourceType><dates> <date dateType="Created">Mon 16 Sep 2013</date> <date dateType="Updated">Sun 25 Dec 2016</date> <date dateType="Submitted">Tue 15 Jan 2019</date> </dates> <alternateIdentifiers> <alternateIdentifier alternateIdentifierType="bitstream">4986321e96db307c1d6e8bd4225c7b71ddb36cce</alternateIdentifier> </alternateIdentifiers> <formats> <format>application/pdf</format> </formats> <version>27094</version> <descriptions> <description descriptionType="Abstract"></description> </descriptions> </resource>

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