PuSH - Publication Server of Helmholtz Zentrum München

Reconstruction of graphs based on random walks.

Theor. Comput. Sci. 410, 3826-3838 (2009)
DOI PMC
Open Access Green as soon as Postprint is submitted to ZB.
The analysis of complex networks is of major interest in various fields of science. In many applications we face the challenge that the exact topology of a network is unknown but we are instead given information about distances within this network. The theoretical approaches to this problem have so far been focusing on the reconstruction of graphs from shortest path distance matrices. Often, however, movements in networks do not follow shortest paths but occur in a random fashion. In these cases an appropriate distance measure can be defined as the mean length of a random walk between two nodes - a quantity known as the mean first hitting time. In this contribution we investigate whether a graph can be reconstructed from its mean first hitting time matrix and put forward an algorithm for solving this problem. A heuristic method to reduce the computational effort is described and analyzed. In the case of trees we can even give an algorithm for reconstructing graphs from incomplete random walk distance matrices.
Altmetric
Additional Metrics?
Edit extra informations Login
Publication type Article: Journal article
Document type Scientific Article
Keywords Graph theory; Distance realization problem; Random walk; Mean first hitting time; distance matrices; metric-spaces; tree; algorithm; realizations; networks; model
Reviewing status