Reconstruction of graphs based on random walks |
| |
Authors: | Dominik M Wittmann Daniel Schmidl Florian Blchl Fabian J Theis |
| |
Affiliation: | aInstitute for Bioinformatics and Systems Biology, Helmholtz Zentrum München — German Research Center for Environmental Health, Ingolstädter Landstrasse 1, D-85764 Neuherberg, Germany;bFaculty of Mathematics, Technische Universität München, Boltzmannstrasse 3, D-85747 Garching, Germany;cMax Planck Institute for Dynamics and Self-Organisation, Bunsenstrasse 10, D-37073 Göttingen, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Graph theory Distance realization problem Random walk Mean first hitting time |
本文献已被 ScienceDirect 等数据库收录! |
|