Random path

from Wikipedia, the free encyclopedia

A random path is a path in a network or a graph with a random course. It starts at a random node and in each step a random edge is selected to continue the path. Random paths are u. a. Subject of network and graph theory .

The analysis of random paths can provide statistical information about the structure of a network. For example, it can be assumed that in the case of a random path in the World Wide Web , in which individual web pages represent the nodes and hyperlinks represent the edges, pages with a higher PageRank are more likely to be visited.

A process similar to random paths is formed by random walks , which cannot be viewed in graphs but, for example, in mathematical spaces in connection with a random number generator . A starting point (usually the zero point) is assumed and the current position in space is changed by a value generated randomly in each step.


Random paths can be used to obtain information about the entire structure of a graph without having to look at all nodes and edges.

Random paths are used in webometry to gain information about the structure of the Internet and to simulate the behavior of web surfers. However, it is questionable whether every link on a website is clicked with the same probability. The quality of search engines can also be examined. One problem with generating random paths on the Internet is finding a truly random start page.

Random paths can also be viewed from the point of view of graph theory and statistics in order to clarify the relationships between special structures of graphs and random paths in these graphs. Random paths have also been used to study the influence of expectations or supernatural forces on scientific experiments.

In mathematics , random paths can u. a. are used to calculate integrals and are the subject of statistical studies (see Monte Carlo simulation and Metropolis algorithm ).

See also


  • Monika R. Henzinger , Allan Heydon, Michael Mitzenmacher, Marc Najork: Measuring index quality using random walks on the Web . In: Proceeding of the eighth international conference on World Wide Web, May 1999, pp. 1291-1303
  • Henzinger, Heydon, Mitzenmacher, Najork: On near-uniform URL sampling . In: Proceedings of the 9th International World Wide Web Conference, May 2000, Computer Networks, 33 (1-6), pp. 295-308.
  • http://www.princeton.edu/~pear/
  • Siddhartha Chib and Edward Greenberg: Understanding the Metropolis – Hastings Algorithm . In: American Statistician, 49, 327-335, 1995