Finding top-k shortest path distance changes in an evolutionary network

Manish Gupta, Charu C. Aggarwal, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Networks can be represented as evolutionary graphs in a variety of spatio-temporal applications. Changes in the nodes and edges over time may also result in corresponding changes in structural garph properties such as shortest path distances. In this paper, we study the problem of detecting the top-k most significant shortest-path distance changes between two snapshots of an evolving graph. While the problem is solvable with two applications of the all-pairs shortest path algorithm, such a solution would be extremely slow and impractical for very large graphs. This is because when a graph may contain millions of nodes, even the storage of distances between all node pairs can become inefficient in practice. Therefore, it is desirable to design algorithms which can directly determine the significant changes in shortest path distances, without materializing the distances in individual snapshots. We present algorithms that are up to two orders of magnitude faster than such a solution, while retaining comparable accuracy.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings
Pages130-148
Number of pages19
DOIs
StatePublished - Sep 19 2011
Event12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011 - Minneapolis, MN, United States
Duration: Aug 24 2011Aug 26 2011

Publication series

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

Other

Other12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011
CountryUnited States
CityMinneapolis, MN
Period8/24/118/26/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Finding top-k shortest path distance changes in an evolutionary network'. Together they form a unique fingerprint.

  • Cite this

    Gupta, M., Aggarwal, C. C., & Han, J. (2011). Finding top-k shortest path distance changes in an evolutionary network. In Advances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings (pp. 130-148). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6849 LNCS). https://doi.org/10.1007/978-3-642-22922-0_9