[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

The walk distances in graphs

Published: 01 July 2012 Publication History

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).

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics
Discrete Applied Mathematics  Volume 160, Issue 10-11
July, 2012
245 pages

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 July 2012

Author Tags

  1. Graph distances
  2. Logarithmic forest distances
  3. Network
  4. Resistance distance
  5. Transitional measure
  6. Walk distances

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media