Skip to Main content Skip to Navigation
New interface
Conference papers

Distributed Spectral Decomposition in Networks by Complex Diffusion and Quantum Random Walk

Abstract : In this paper we address the problem of finding top k eigenvalues and corresponding eigenvectors of symmetric graph matrices in networks in a distributed way. We propose a novel idea called complex power iterations in order to decompose the eigenvalues and eigenvectors at node level, analogous to time-frequency analysis in signal processing. At each node, eigenvalues correspond to the frequencies of spectral peaks and respective eigenvector components are the amplitudes at those points. Based on complex power iterations and motivated from fluid diffusion processes in networks, we devise distributed algorithms with different orders of approximation. We also introduce a Monte Carlo technique with gossiping which substantially reduces the computational overhead. An equivalent parallel random walk algorithm is also presented. We validate the algorithms with simulations on real-world networks. Our formulation of the spectral decomposition can be easily adapted to a simple algorithm based on quantum random walks. With the advent of quantum computing, the proposed quantum algorithm will be extremely useful.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Thursday, January 28, 2016 - 11:44:40 AM
Last modification on : Friday, January 21, 2022 - 3:21:44 AM


Files produced by the author(s)


  • HAL Id : hal-01263811, version 1


Konstantin Avrachenkov, Philippe Jacquet, Jithin K. Sreedharan. Distributed Spectral Decomposition in Networks by Complex Diffusion and Quantum Random Walk. IEEE Infocom 2016, Apr 2016, San Francisco, United States. ⟨hal-01263811⟩



Record views


Files downloads