Ring structures and mean first passage time in networks
| dc.creator | Baronchelli, Andrea | |
| dc.creator | Loreto, Vittorio | |
| dc.date | 2005-01-27 | |
| dc.date | 2006-02-08 | |
| dc.date.accessioned | 2026-07-07T06:37:29Z | |
| dc.date.available | 2026-07-07T06:37:29Z | |
| dc.description | In this paper we address the problem of the calculation of the mean first passage time (MFPT) on generic graphs. We focus in particular on the mean first passage time on a node 's' for a random walker starting from a generic, unknown, node 'x'. We introduce an approximate scheme of calculation which maps the original process in a Markov process in the space of the so-called rings, described by a transition matrix of size O(ln N / ln<k> X ln N / ln<k>), where N is the size of the graph and <k> the average degree in the graph. In this way one has a drastic reduction of degrees of freedom with respect to the size N of the transition matrix of the original process, corresponding to an extremely-low computational cost. We first apply the method to the Erdos-Renyi random graph for which the method allows for almost perfect agreement with numerical simulations. Then we extend the approach to the Barabasi-Albert graph, as an example of scale-free graph, for which one obtains excellent results. Finally we test the method with two real world graphs, Internet and a network of the brain, for which we obtain accurate results. | |
| dc.description | 8 pages, 8 figures | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0501669 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0501669 | |
| dc.identifier | Phys. Rev. E 73, 026103 (2006) | |
| dc.identifier | doi:10.1103/PhysRevE.73.026103 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/100407 | |
| dc.subject | Statistical Mechanics | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.title | Ring structures and mean first passage time in networks | |
| dc.type | text |