Intrinsic Degree: An Estimator of the Local Growth Rate in Graphs

Lorenzo von Ritter, Michael E. Houle, Stephan Günnemann

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

The neighborhood size of a query node in a graph often grows exponentially with the distance to the node, making a neighborhood search prohibitively expensive even for small distances. Estimating the growth rate of the neighborhood size is therefore an important task in order to determine an appropriate distance for which the number of traversed nodes during the search will be feasible. In this work, we present the intrinsic degree model, which captures the growth rate of exponential functions through the analysis of the infinitesimal vicinity of the origin. We further derive an estimator which allows to apply the intrinsic degree model to graphs. In particular, we can locally estimate the growth rate of the neighborhood size by observing the close neighborhood of some query points in a graph. We evaluate the performance of the estimator through experiments on both artificial and real networks.

Original languageEnglish
Title of host publicationSimilarity Search and Applications - 11th International Conference, SISAP 2018, Proceedings
EditorsStéphane Marchand-Maillet, Yasin N. Silva, Edgar Chávez
PublisherSpringer Verlag
Pages195-208
Number of pages14
ISBN (Print)9783030022235
DOIs
StatePublished - 2018
Event11th International Conference on Similarity Search and Applications, SISAP 2018 - Lima, Peru
Duration: 7 Oct 20189 Oct 2018

Publication series

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

Conference

Conference11th International Conference on Similarity Search and Applications, SISAP 2018
Country/TerritoryPeru
CityLima
Period7/10/189/10/18

Keywords

  • Degree
  • Estimation
  • Graph
  • Intrinsic dimensionality

Fingerprint

Dive into the research topics of 'Intrinsic Degree: An Estimator of the Local Growth Rate in Graphs'. Together they form a unique fingerprint.

Cite this