2017/04/04 by Konstantin Avrachenkov, Avrachenkov, Konstantin, Philippe Jacquet +3
Computer Science · Physics and Astronomy · #FOS: Mathematics #Numerical Analysis (math.NA) #Opinion Dynamics and Social Influence #Quantum Computing Algorithms and Architecture #Quantum many-body systems
paper · pdf · doi:10.48550/arxiv.1704.00941
openalex publication_date 2017/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Because of the significant increase in size and complexity of the networks,\nthe distributed computation of eigenvalues and eigenvectors of graph matrices\nhas become very challenging and yet it remains as important as before. In this\npaper we develop efficient distributed algorithms to detect, with higher\nresolution, closely situated eigenvalues and corresponding eigenvectors of\nsymmetric graph matrices. We model the system of graph spectral computation as\nphysical systems with Lagrangian and Hamiltonian dynamics. The spectrum of\nLaplacian matrix, in particular, is framed as a classical spring-mass system\nwith Lagrangian dynamics. The spectrum of any general symmetric graph matrix\nturns out to have a simple connection with quantum systems and it can be thus\nformulated as a solution to a Schr "odinger-type differential equation. Taking\ninto account the higher resolution requirement in the spectrum computation and\nthe related stability issues in the numerical solution of the underlying\ndifferential equation, we propose the application of symplectic integrators to\nthe calculation of eigenspectrum. The effectiveness of the proposed techniques\nis demonstrated with numerical simulations on real-world networks of different\nsizes and complexities.\n