Cited By
View all- Aynulin R(2019)Efficiency of Transformations of Proximity Measures for Graph ClusteringAlgorithms and Models for the Web Graph10.1007/978-3-030-25070-6_2(16-29)Online publication date: 6-Jul-2019
The walk distances in graphs
Pages 1484 - 1500
Abstract
The walk distances in graphs are defined as the result of appropriate transformations of the @?"k"="0^~(tA)^k proximity measures, where A is the weighted adjacency matrix of a graph and t is a sufficiently small positive parameter. The walk distances are graph-geodetic; moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter t approaches its limiting values. We also show that the logarithmic forest distances which are known to generalize the resistance distance and the shortest path distance are a specific subclass of walk distances. On the other hand, the long walk distance is equal to the resistance distance in a transformed graph.
References
[1]
Bapat, R.B., Resistance distance in graphs. Math. Student. v68. 87-98.
[2]
Bapat, R.B. and Sivasubramanian, S., Identities for minors of the Laplacian, resistance and distance matrices. Linear Algebra Appl. v435. 1479-1489.
[3]
Buckley, F. and Harary, F., Distance in Graphs. 1990. Addison-Wesley, Redwood City, CA.
[4]
Chebotarev, P., A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discrete Appl. Math. v159. 295-302.
[5]
The graph bottleneck identity. Adv. Appl. Math. v47. 403-413.
[6]
Chebotarev, P. and Agaev, R., Forest matrices around the Laplacian matrix. Linear Algebra Appl. v356. 253-274.
[7]
P. Chebotarev, R.B. Bapat, R. Balaji, Simple expressions for the long walk distance, arXiv Peprint math.CO/1112.0088, 2011. http://arxiv.org/abs/1112.0088.
[8]
P. Chebotarev, M. Deza, A topological interpretation of the walk distances, arXiv Peprint math.CO/1111.0284 (submitted for publication in Springer collection "Distance Geometry", 2012). http://arxiv.org/abs/1111.0284.
[9]
Chebotarev, P.Yu. and Shamis, E.V., The matrix-forest theorem and measuring relations in small social groups. Autom. Remote Control. v58. 1505-1514.
[10]
Chebotarev, P.Yu. and Shamis, E.V., On proximity measures for graph vertices. Autom. Remote Control. v59. 1443-1459.
[11]
Chebotarev, P.Yu. and Shamis, E.V., The forest metrics of a graph and their properties. Autom. Remote Control. v61. 1364-1373.
[12]
Chelnokov, V.M. and Zefirova, V.L., A matrix-based measure of inter-node walk relatedness in a network. Math. Notes. v85. 109-119.
[13]
Cinkir, Z., The tau constant and the discrete Laplacian matrix of a metrized graph. European J. Combin. v32. 639-655.
[14]
Critchley, F., On certain linear mappings between inner-product and squared-distance matrices. Linear Algebra Appl. v105. 91-107.
[15]
Deza, M. and Deza, E., Encyclopedia of Distances. 2009. Springer, Berlin, Heidelberg.
[16]
Deza, M. and Laurent, M., Geometry of Cuts and Metrics. 1997. Springer, Berlin.
[17]
Estrada, E., The Structure of Complex Networks: Theory and Applications. 2011. Oxford Univ. Press, Oxford.
[18]
Estrada, E. and Higham, D.J., Network properties revealed through matrix functions. SIAM Rev. v52. 696-714.
[19]
Gantmacher, F.R., Applications of the Theory of Matrices. 1959. Interscience, New York.
[20]
Göbel, F. and Jagers, A.A., Random walks on graphs. Stochastic Process. Appl. v2. 311-336.
[21]
Gurvich, V., Metric and ultrametric spaces of resistances. Discrete Appl. Math. v158. 1496-1505.
[22]
Metric and ultrametric spaces of resistances. Russian Math. Surveys. v42. 235-236.
[23]
Harary, F., Graph Theory. 1969. Addison-Wesley, Reading, MA.
[24]
Harary, F. and Schwenk, A.J., The spectral approach to determining the number of walks in a graph. Pacific J. Math. v80. 443-449.
[25]
Kasteleyn, P.W., Graph theory and crystal physics. In: Harary, F. (Ed.), Graph Theory and Theoretical Physics, Academic Press, London. pp. 43-110.
[26]
Katz, L., A new status index derived from sociometric analysis. Psychometrika. v18. 39-43.
[27]
Klein, D.J., Centrality measure in graphs. J. Math. Chem. v47. 1209-1223.
[28]
Random walks and chemical graph theory. J. Chem. Inf. Comput. Sci. v44. 1521-1525.
[29]
Klein, D.J. and Randić, M., Resistance distance. J. Math. Chem. v12. 81-95.
[30]
Klein, D.J. and Zhu, H.-Y., Distances and volumina for graphs. J. Math. Chem. v23. 179-195.
[31]
Meyer Jr., C.D., Limits and the index of a square matrix. SIAM J. Appl. Math. v26. 469-478.
[32]
Metric transformation of an (m+1)-terminal resistive network into a hyperacute angled simplex Pm in Euclidean space Em. In: Proceedings of the Eleventh Midwest Symposium on Circuit Theory, Univ. of Notre Dame, Notre Dame, Indiana. pp. 184-192.
[33]
Nei, M., Genetic distance between populations. Am. Nat. v106 i949. 283-292.
[34]
Ponstein, J., Self-avoiding paths and the adjacency matrix of a graph. SIAM J. Appl. Math. v14. 600-609.
[35]
Rao, C.R. and Mitra, S.K., Generalized Inverse of Matrices and its Applications. 1971. Wiley, New York.
[36]
Rothblum, U.G., Computation of the eigenprojection of a nonnegative matrix at its spectral radius. In: Wets, R.J.-B. (Ed.), Mathematical Programming Study, vol. 6. North-Holland, Amsterdam. pp. 188-201.
[37]
Rothblum, U.G., Resolvent expansions of matrices and applications. Linear Algebra Appl. v38. 33-49.
[38]
Seshu, S. and Reed, M.B., Linear Graphs and Electrical Networks. 1961. Addison-Wesley, Reading, MA.
[39]
G.E. Sharpe, Solution of the (m+1)-terminal resistive network problem by means of metric geometry, in: Proceedings of the First Asilomar Conference on Circuits and Systems, Pacific Grove, CA, November 1967, pp. 319-328.
[40]
Sharpe, G.E., Theorem on resistive networks. Electron. Lett. v3. 444-445.
[41]
Sharpe, G.E., Violation of the 2-triple property by resistive networks. Electron. Lett. v3. 543-544.
[42]
Sharpe, G.E. and Spain, B., On the solution of networks by means of the equicofactor matrix. IRE Trans. Circuit Theory. v7. 230-239.
[43]
Sharpe, G.E. and Styan, G.P.H., A note on the general network inverse. IEEE Trans. Circuit Theory. v12. 632-633.
[44]
Circuit duality and the general network inverse. IEEE Trans. Circuit Theory. v12. 22-27.
[45]
Sharpe, G.E. and Styan, G.P.H., A note on equicofactor matrices. Proc. IEEE. v55. 1226-1227.
[46]
Styan, G.P.H. and Subak-Sharpe, G.E., Inequalities and equalities associated with the Campbell-Youla generalized inverse of the indefinite admittance matrix of resistive networks. Linear Algebra Appl. v250. 349-370.
[47]
G.E. Subak-Sharpe, On the structural constraints of electrical networks, in: Proceedings of 1989 IEEE International Conference on Circuits and Systems, Nanjing, China, July 6-8, 1989, pp. 369-374.
[48]
G.E. Subak-Sharpe, On the characterization of positive resistance networks by means of distance geometry, in: Proceedings of the 1990 IEEE International Symposium on Circuits and Systems, vol. 3, 1990, pp. 1764-1768.
[49]
M. Tang, Graph metrics and dimension reduction, Ph.D. Thesis, School of Informatics and Computing, Indiana University, Bloomington, IN, 2010.
[50]
Taylor, M., Graph-theoretic approaches to the theory of social choice. Public Choice. v4. 35-47.
[51]
Thompson, G.L., Lectures on Game Theory, Markov Chains and Related Topics, Sandia Corporation Monograph SCR-11, Albuquerque, New Mexico. 1958.
[52]
von Luxburg, U., Radl, A. and Hein, M., Getting lost in space: large sample analysis of the resistance distance. In: NIPS 2010, Twenty-Fourth Annual Conference on Neural Information Processing Systems, Curran, Red Hook, New York. pp. 2622-2630.
[53]
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 International Conference on Knowledge Discovery and Data Mining, 2008, pp. 785-793.
[54]
D. Youla, Some new formulas in the theory of n-terminal networks, Rome Air Development Center Report, Colgate Univ., Hamilton, New York, 1959, 20 pp (unpublished).
- The walk distances in graphs
Recommendations
A class of graph-geodetic distances generalizing the shortest-path and the resistance distances
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 ...
Resistance distances in generalized join graphs
AbstractLet H be a graph with vertex set V ( H ) = { v 1 , v 2 , … , v k }. The generalized join graph H [ G 1 , G 2 , … , G k ] is obtained from H by replacing each vertex v i with a graph G i and joining each vertex in G i with each vertex in G j ...
Algorithmic techniques for finding resistance distances on structured graphs
AbstractIn this paper, we give a survey of methods used to calculate values of resistance distance (also known as effective resistance) in graphs. Resistance distance has played a prominent role not only in circuit theory and chemistry, but ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V. © 2012.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 01 July 2012
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
Cited By
View all- Aynulin R(2019)Efficiency of Transformations of Proximity Measures for Graph ClusteringAlgorithms and Models for the Web Graph10.1007/978-3-030-25070-6_2(16-29)Online publication date: 6-Jul-2019