A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. (English) Zbl 1209.05068
Summary: A new class of distances for graph vertices is proposed. This class contains parametric families of distances which reduce to the shortest-path, weighted shortest-path, and the resistance distances at the limiting values of the family parameters. The main property of the class is that all distances it comprises are graph-geodetic: \(d(i,j)+d(j,k)=d(i,k)\) if and only if every path from \(i\) to \(k\) passes through \(j\). The construction of the class is based on the matrix forest theorem and the transition inequality.
Keywords:
shortest path distance; resistance distance; forest distance; matrix forest theorem; spanning rooted forest; transitional measure; graph bottleneck identity; regularized Laplacian kernelReferences:
| [1] | Buckley, F.; Harary, F., Distance in Graphs (1990), Addison-Wesley: Addison-Wesley Redwood City, CA · Zbl 0688.05017 |
| [2] | Chandra, A. K.; Raghavan, P.; Ruzzo, W. L.; Smolensky, R.; Tiwari, P., The electrical resistance of a graph captures its commute and cover times, (Proc. 21st Annual ACM Symp. on Theory of Computing (1989), ACM Press: ACM Press Seattle), 574-586 |
| [3] | P. Chebotarev, The graph bottleneck identity, Adv. Appl. Math. URL: http://dx.doi.org/10.1016/j.aam.2010.11.001; P. Chebotarev, The graph bottleneck identity, Adv. Appl. Math. URL: http://dx.doi.org/10.1016/j.aam.2010.11.001 · Zbl 1232.05064 |
| [4] | Chebotarev, P., Spanning forests and the golden ratio, Discrete Appl. Math., 156, 813-821 (2008) · Zbl 1136.05035 |
| [5] | Chebotarev, P.; Agaev, R., Forest matrices around the Laplacian matrix, Linear Algebr Appl., 356, 253-274 (2002) · Zbl 1017.05073 |
| [6] | Chebotarev, P.; Shamis, E., The forest metrics for graph vertices, Electron. Notes Discrete Math., 11, 98-107 (2002) · Zbl 1075.05522 |
| [7] | Chebotarev, P. Yu.; Shamis, E. V., The matrix-forest theorem and measuring relations in small social groups, Autom. Remote Control, 58, 1505-1514 (1997) · Zbl 0920.92042 |
| [8] | P.Yu. Chebotarev, E. Shamis, On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix, in: Abstracts of the Conference “Linear Algebra and its Applications”, 10-12 July, 1995, University of Manchester, Manchester, UK, 1995, pp. 6-7. URL: http://www.ma.man.ac.uk/ higham/laa95/abstracts.ps; P.Yu. Chebotarev, E. Shamis, On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix, in: Abstracts of the Conference “Linear Algebra and its Applications”, 10-12 July, 1995, University of Manchester, Manchester, UK, 1995, pp. 6-7. URL: http://www.ma.man.ac.uk/ higham/laa95/abstracts.ps |
| [9] | Chebotarev, P. Yu.; Shamis, E. V., On proximity measures for graph vertices, Autom. Remote Control, 59, 1443-1459 (1998) · Zbl 1079.05503 |
| [10] | Chen, H.; Zhang, F., Resistance distance and the normalized Laplacian spectrum, Discrete Appl. Math., 155, 654-661 (2007) · Zbl 1113.05062 |
| [11] | F. Chung, W. Zhao, PageRank and random walks on graphs, in: Proceedings of “Fete of Combinatorics and Computer Science” Conference in honor of Laci Lovász, Keszthely, Hungary, August 11-15, 2008 (in press).; F. Chung, W. Zhao, PageRank and random walks on graphs, in: Proceedings of “Fete of Combinatorics and Computer Science” Conference in honor of Laci Lovász, Keszthely, Hungary, August 11-15, 2008 (in press). |
| [12] | Deza, M. M.; Deza, E., Encyclopedia of Distances (2009), Springer: Springer Berlin, Heidelberg · Zbl 1167.51001 |
| [13] | Deza, M. M.; Laurent, M., Geometry of Cuts and Metrics (1997), Springer: Springer Berlin · Zbl 0885.52001 |
| [14] | Göbel, F.; Jagers, A. A., Random walks on graphs, Stochastic Process. Appl., 2, 311-336 (1974) · Zbl 0296.60046 |
| [15] | Graham, R. L.; Hoffman, A. J.; Hosoya, H., On the distance matrix of a directed graph, J. Graph Theory, 1, 85-88 (1977) · Zbl 0363.05034 |
| [16] | Gurvich, V., Metric and ultrametric spaces of resistances, Discrete Appl. Math., 158, 1496-1505 (2010) · Zbl 1234.94091 |
| [17] | Gvishiani, A. D.; Gurvich, V. A., Metric and ultrametric spaces of resistances, Russian Math. Surveys, 42, 235-236 (1987) · Zbl 0708.90028 |
| [18] | Klein, D. J.; Randić, M., Resistance distance, J. Math. Chem., 12, 81-95 (1993) |
| [19] | Klein, D. J.; Zhu, H. Y., Distances and volumina for graphs, J. Math. Chem., 23, 179-195 (1998) · Zbl 0908.05038 |
| [20] | Mantrach, A.; Yen, L.; Callut, J.; Françoisse, K.; Shimbo, M.; Saerens, M., The Sum-over-paths covariance kernel: a novel covariance measure between nodes of a directed graph, IEEE Trans. Pattern Anal. Mach. Intell., 32, 1112-1126 (2010) |
| [21] | Nash-Williams, C. St. J.A., Random walk and electric currents in networks, Math. Proc. Cambridge Philos. Soc., 55, 181-194 (1959) · Zbl 0100.13602 |
| [22] | Seshu, S.; Reed, M. B., Linear Graphs and Electrical Networks (1961), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0102.34001 |
| [23] | Shapiro, L. W., An electrical lemma, Math. Mag., 60, 36-38 (1987) · Zbl 0638.05017 |
| [24] | Shimbo, M.; Ito, T.; Mochihashi, D.; Matsumoto, Yu., On the properties of von Neumann kernels for link analysis, Mach. Learn., 75, 37-67 (2009) · Zbl 1470.68176 |
| [25] | A.J. Smola, R.I. Kondor, Kernels and regularization of graphs, in: Proc. 16th Annual Conf. on Learning Theory, 2003, pp. 144-158.; A.J. Smola, R.I. Kondor, Kernels and regularization of graphs, in: Proc. 16th Annual Conf. on Learning Theory, 2003, pp. 144-158. · Zbl 1274.68351 |
| [26] | 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, in: 14th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining, 2008, pp. 785-793.; 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, in: 14th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining, 2008, pp. 785-793. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
