Estimating the Manifold Dimension of a Complex Network Using Weyl’s Law

Luca Rossi, Andrea Torsello

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

The dimension of the space underlying real-world networks has been shown to strongly influence the networks structural properties, from the degree distribution to the way the networks respond to diffusion and percolation processes. In this paper we propose a way to estimate the dimension of the manifold underlying a network that is based on Weyl’s law, a mathematical result that describes the asymptotic behaviour of the eigenvalues of the graph Laplacian. For the case of manifold graphs, the dimension we estimate is equivalent to the fractal dimension of the network, a measure of structural self-similarity. Through an extensive set of experiments on both synthetic and real-world networks we show that our approach is able to correctly estimate the manifold dimension. We compare this with alternative methods to compute the fractal dimension and we show that our approach yields a better estimate on both synthetic and real-world examples.

Original languageEnglish
Title of host publicationStructural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshops, S+SSPR 2020, Proceedings
EditorsAndrea Torsello, Luca Rossi, Marcello Pelillo, Battista Biggio, Antonio Robles-Kelly
PublisherSpringer Science and Business Media Deutschland GmbH
Pages164-173
Number of pages10
ISBN (Print)9783030739720
DOIs
Publication statusPublished - Jan 2021
Externally publishedYes
EventJoint IAPR International Workshops on Structural, Syntactic and Statistical Techniques in Pattern Recognition, S+SSPR 2020 - Padua, Italy
Duration: 21 Jan 202122 Jan 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12644 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceJoint IAPR International Workshops on Structural, Syntactic and Statistical Techniques in Pattern Recognition, S+SSPR 2020
Country/TerritoryItaly
CityPadua
Period21/01/2122/01/21

Keywords

  • Complex networks
  • Manifold dimension
  • Weyl law

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this