Eigenvalues and spectral dimension of random geometric graphs in thermodynamic regime

Avrachenkov, Konstantin; Cottatellucci, Laura; Hamidouche, Mounia
COMPLEX NETWORKS 2019, 8th International Conference on Complex Networks and their Applications, 10-12 December 2019, Lisbon, Portugal

Network geometries are typically characterized by having a finite spectral
dimension (SD), ds that characterizes the return time distribution of a random
walk on a graph. The main purpose of this work is to determine the SD of a variety
of random graphs called random geometric graphs (RGGs) in the thermodynamic
regime, in which the average vertex degree is constant. The spectral dimension
depends on the eigenvalue density (ED) of the RGG normalized Laplacian in the
neighborhood of the minimum eigenvalues. In fact, the behavior of the ED in
such a neighborhood characterizes the random walk. Therefore, we first provide
an analytical approximation for the eigenvalues of the regularized normalized
Laplacian matrix of RGGs in the thermodynamic regime. Then, we show that the
smallest non zero eigenvalue converges to zero in the large graph limit. Based on
the analytical expression of the eigenvalues, we show that the eigenvalue distribution
in a neighborhood of the minimum value follows a power-law tail. Using
this result, we find that the SD of RGGs is approximated by the space dimension
d in the thermodynamic regime.

DOI
HAL
Type:
Conférence
City:
Lisbon
Date:
2019-12-09
Department:
Systèmes de Communication
Eurecom Ref:
6050
Copyright:
© Springer. Personal use of this material is permitted. The definitive version of this paper was published in COMPLEX NETWORKS 2019, 8th International Conference on Complex Networks and their Applications, 10-12 December 2019, Lisbon, Portugal and is available at : http://dx.doi.org/https://doi.org/10.1007/978-3-030-36687-2_80

PERMALINK : https://www.eurecom.fr/publication/6050