Fast Algorithm for Relaxation Processes in Big-data Systems

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.

11 pages, 3 figures

References in corpus (14)

• Emergence of scaling in random networks
• Synchronization in small-world systems
• Growing Scale-Free Networks with Tunable Clustering
• Fractal and Transfractal Recursive Scale-Free Nets
• Global mean first-passage times of random walks on complex networks
• First passage time for random walks in heterogeneous networks
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Percolation in Hierarchical Scale-Free Nets
• From Massively Parallel Algorithms and Fluctuating Time Horizons to Non-equilibrium Surface Growth
• The spectral dimension of generic trees
• Testing the Collective Properties of Small-World Networks through Roughness Scaling
• Generalized inverses of Markovian kernels in terms of properties of the Markov chain
• Extreme fluctuations in noisy task-completion landscapes on scale-free networks

Cited by in corpus (2)

• Relevance of the minimum degree to dynamic fluctuation in strongly heterogeneous networks
• Heterogeneous Mean First-Passage Time Scaling in Fractal Media