Graduate School and Research Center in Digital Sciences

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.

Document Doi Arxiv Hal Bibtex

Title:Eigenvalues and spectral dimension of random geometric graphs in thermodynamic regime
Keywords:Random geometric graph, Laplacian spectrum, Spectral dimension
Type:Conference
Language:English
City:Lisbon
Country:PORTUGAL
Date:
Department:Communication systems
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
Bibtex: @inproceedings{EURECOM+6050, doi = {http://dx.doi.org/https://doi.org/10.1007/978-3-030-36687-2_80}, year = {2019}, title = {{E}igenvalues and spectral dimension of random geometric graphs in thermodynamic regime}, author = {{A}vrachenkov, {K}onstantin and {C}ottatellucci, {L}aura and {H}amidouche, {M}ounia}, booktitle = {{COMPLEX} {NETWORKS} 2019, 8th {I}nternational {C}onference on {C}omplex {N}etworks and their {A}pplications, 10-12 {D}ecember 2019, {L}isbon, {P}ortugal}, address = {{L}isbon, {PORTUGAL}}, month = {12}, url = {http://www.eurecom.fr/publication/6050} }
See also: