Hamiltonian System Approach to Distributed Spectral Decomposition in Networks

Abstract : Because of the significant increase in size and complexity of the networks, the distributed computation of eigenvalues and eigenvectors of graph matrices has become very challenging and yet it remains as important as before. In this paper we develop efficient distributed algorithms to detect, with higher resolution, closely situated eigenvalues and corresponding eigenvectors of symmetric graph matrices. We model the system of graph spectral computation as physical systems with Lagrangian and Hamiltonian dynamics. The spectrum of Laplacian matrix, in particular, is framed as a classical spring-mass system with Lagrangian dynamics. The spectrum of any general symmetric graph matrix turns out to have a simple connection with quantum systems and it can be thus formulated as a solution to a Schrödinger-type differential equation. Taking into account the higher resolution requirement in the spectrum computation and the related stability issues in the numerical solution of the underlying differential equation, we propose the application of symplectic integrators to the calculation of eigenspectrum. The effectiveness of the proposed techniques is demonstrated with numerical simulations on real-world networks of different sizes and complexities.
Type de document :
Communication dans un congrès
nDS 2017 - 10th International Workshop on Multidimensional (nD) Systems, Sep 2017, Zielona Gora, Poland
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01646881
Contributeur : Konstantin Avrachenkov <>
Soumis le : jeudi 23 novembre 2017 - 20:00:08
Dernière modification le : vendredi 12 janvier 2018 - 01:49:54

Fichier

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

Identifiants

  • HAL Id : hal-01646881, version 1

Collections

Citation

Konstantin Avrachenkov, Philippe Jacquet, Jithin Sreedharan. Hamiltonian System Approach to Distributed Spectral Decomposition in Networks. nDS 2017 - 10th International Workshop on Multidimensional (nD) Systems, Sep 2017, Zielona Gora, Poland. 〈hal-01646881〉

Partager

Métriques

Consultations de la notice

22

Téléchargements de fichiers

8