{
  "id": "cond-mat/0501669",
  "version": "v2",
  "published": "2005-01-27T15:35:51.000Z",
  "updated": "2006-02-08T13:58:56.000Z",
  "title": "Ring structures and mean first passage time in networks",
  "authors": [
    "Andrea Baronchelli",
    "Vittorio Loreto"
  ],
  "comment": "8 pages, 8 figures",
  "journal": "Phys. Rev. E 73, 026103 (2006)",
  "doi": "10.1103/PhysRevE.73.026103",
  "categories": [
    "cond-mat.stat-mech",
    "cond-mat.dis-nn"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2006-02-08T13:58:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "mean first passage time",
      "ring structures",
      "original process",
      "transition matrix",
      "real world graphs"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Phys. Rev. E"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}