{
  "id": "1403.6723",
  "version": "v2",
  "published": "2014-03-26T15:54:26.000Z",
  "updated": "2014-09-11T09:03:11.000Z",
  "title": "Fast Algorithm for Relaxation Processes in Big-data Systems",
  "authors": [
    "S. Hwang",
    "D. -S. Lee",
    "B. Kahng"
  ],
  "comment": "11 pages, 3 figures",
  "categories": [
    "cond-mat.stat-mech"
  ],
  "abstract": "Relaxation processes driven by a Laplacian matrix can be found in many real-world big-data systems, for example, in search engines on the World-Wide-Web and the dynamic load balancing protocols in mesh networks. To numerically implement such processes, a fast-running algorithm for the calculation of the pseudo inverse of the Laplacian matrix is essential. Here we propose an algorithm which computes fast and efficiently the pseudo inverse of Markov chain generator matrices satisfying the detailed-balance condition, a general class of matrices including the Laplacian. The algorithm utilizes the renormalization of the Gaussian integral. In addition to its applicability to a wide range of problems, the algorithm outperforms other algorithms in its ability to compute within a manageable computing time arbitrary elements of the pseudo inverse of a matrix of size millions by millions. Therefore our algorithm can be used very widely in analyzing the relaxation processes occurring on large-scale networked systems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-03-26T15:54:26.000Z",
      "abstract": "Relaxation processes driven by the Laplacian matrix in complex networks can be found in many real-world big-data systems, for example, search engines on web pages and dynamic load balancing protocols in mesh networks. To numerically implement such processes, a fast-running algorithm for the calculation of the inverse of the Laplacian matrix is needed. Yet, such algorithms have not been developed in complex networks, in which the fast-Fourier acceleration method cannot be used. Here, we introduce a fast-running algorithm that computes the pseudo inverse of a given Laplacian matrix using the renormalization method of the Gaussian integral. Through this method, the inverse of the Laplacian matrices of real-world networks containing millions of nodes can be obtained within reasonable computing times. Thus, this proposed algorithm could be used very widely in analyzing the relaxation processes occurring on large-scale networked systems.",
      "comment": "5 pages, 2 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-09-11T09:03:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05.10.Cc",
      "05.40.-a",
      "89.75.Hc"
    ],
    "keywords": [
      "relaxation processes",
      "big-data systems",
      "fast algorithm",
      "computing time arbitrary elements",
      "pseudo inverse"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "doi": "10.1103/PhysRevE.90.043303",
      "journal": "Physical Review E",
      "year": 2014,
      "month": "Oct",
      "volume": 90,
      "number": 4,
      "pages": "043303"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014PhRvE..90d3303H"
    }
  }
}