Home
Deutsch
Advanced Search
Browse by ...
Publication overview
Contact persons
Help
DOI
PMC
 |
|
Open Access Green as soon as Postprint is submitted to ZB.
Reconstruction of graphs based on random walks.
Theor. Comput. Sci. 410, 3826-3838 (2009)
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
ISSN (print) / ISBN
0304-3975
e-ISSN
1879-2294
Journal
Theoretical Computer Science
Quellenangaben
Volume: 410,
Issue: 38-40,
Pages: 3826-3838
Publisher
Elsevier
Publishing Place
AMSTERDAM
Non-patent literature
Publications
Reviewing status
Peer reviewed