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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01263811
Contributor : Konstantin Avrachenkov <>
Submitted on : Thursday, January 28, 2016 - 11:44:40 AM
Last modification on : Thursday, October 17, 2019 - 12:36:05 PM

File

QRW_Infocom2016_final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01263811, version 1

Citation

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⟩

Share

Metrics

Record views

417

Files downloads

247