Fast algorithm for relaxation processes in big-data systems.
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.
Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
S
S
Hwang
Department of Physics and Department of Natural Medical Sciences, Inha University, Incheon 402-751, Korea.
D-S
DS
Lee
Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
B
B
Kahng
D000465:Algorithms; D007256:Information Systems; D008390:Markov Chains; D013997:Time Factors