TY - GEN

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

AU - Gupta, Manish

AU - Aggarwal, Charu C.

AU - Han, Jiawei

PY - 2011/9/19

Y1 - 2011/9/19

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80052707774&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052707774&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22922-0_9

DO - 10.1007/978-3-642-22922-0_9

M3 - Conference contribution

AN - SCOPUS:80052707774

SN - 9783642229213

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 130

EP - 148

BT - Advances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings

T2 - 12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011

Y2 - 24 August 2011 through 26 August 2011

ER -