Open Access Green möglich sobald Postprint bei der ZB eingereicht worden ist.
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
Weitere Metriken?
Zusatzinfos bearbeiten
[➜Einloggen]
Publikationstyp
Artikel: Journalartikel
Dokumenttyp
Wissenschaftlicher Artikel
Schlagwörter
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
Zeitschrift
Theoretical Computer Science
Quellenangaben
Band: 410,
Heft: 38-40,
Seiten: 3826-3838
Verlag
Elsevier
Verlagsort
AMSTERDAM
Nichtpatentliteratur
Publikationen
Begutachtungsstatus
Peer reviewed