Abstract
A finite connected undirected graph G(V, E) can be seen as a discrete time dynamical system possessing a finite number of states (nodes) (Prisner 1995). The behavior of such a dynamical system can be studied by means of a transfer operator which describes the time evolution of distributions in phase space. The transfer operator can be represented by a stochastic matrix determining a discrete time random walk on the graph in which a walker picks at each node between the various available edges with equal probability. An obvious benefit of the approach based on random walks to graph theory is that the relations between individual nodes and subgraphs acquire a precise quantitative probabilistic description that enables us to attack applied problems which could not even be started otherwise.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Blanchard, P., Volchenkov, D. (2011). Exploring Undirected Graphs by Random Walks. In: Random Walks and Diffusions on Graphs and Databases. Springer Series in Synergetics, vol 10. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19592-1_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-19592-1_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19591-4
Online ISBN: 978-3-642-19592-1
eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)