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.
Type de document :
Communication dans un congrès
IEEE Infocom 2016, Apr 2016, San Francisco, United States. 2016, 〈http://infocom2016.ieee-infocom.org/〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01263811
Contributeur : Konstantin Avrachenkov <>
Soumis le : jeudi 28 janvier 2016 - 11:44:40
Dernière modification le : vendredi 31 août 2018 - 09:12:06

Fichier

QRW_Infocom2016_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01263811, version 1

Collections

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. 2016, 〈http://infocom2016.ieee-infocom.org/〉. 〈hal-01263811〉

Partager

Métriques

Consultations de la notice

364

Téléchargements de fichiers

80