Fast algorithm for relaxation processes in big-data systems

S. Hwang, D.-S. Lee, and B. Kahng
Phys. Rev. E 90, 043303 – Published 6 October 2014

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 pseudoinverse of the Laplacian matrix is essential. Here we propose an algorithm which computes quickly and efficiently the pseudoinverse 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 pseudoinverse 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.

  • Figure
  • Figure
  • Figure
  • Received 19 March 2014
  • Revised 11 August 2014

DOI:https://doi.org/10.1103/PhysRevE.90.043303

©2014 American Physical Society

Authors & Affiliations

S. Hwang1, D.-S. Lee2,*, and B. Kahng1,†

  • 1Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
  • 2Department of Physics and Department of Natural Medical Sciences, Inha University, Incheon 402-751, Korea

  • *deoksun.lee@inha.ac.kr
  • bkahng@snu.ac.kr

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 90, Iss. 4 — October 2014

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×