Proximity tracking on dynamic bipartite graphs: Problem definitions and fast solutions

Hanghang Tong, Spiros Papadimitriou, Philip S. Yu, Christos Faloutsos

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Scopus citations


Large bipartite graphs which evolve and grow over time (e.g., new links arrive, old links die out, or link weights change) arise in many settings, such as social networks, co-citations, market-basket analysis, and collaborative filtering. Our goal is to monitor (i) the centrality of an individual node (e.g., who are the most important authors?) and (ii) the proximity of two nodes or sets of nodes (e.g., who are the most important authors with respect to a particular conference?). Moreover, we want to do this efficiently and incrementally and to provide any-time answers. In this chapter we propose pTrack, which is based on random walks with restart, together with some important modifications to adapt these measures to a dynamic, evolving setting. Additionally, we develop techniques for fast, incremental updates of these measures that allow us to track them continuously, as link updates arrive. In addition, we discuss variants of our method that can handle batch updates, as well as place more emphasis on recent links. Based on proximity tracking, we further proposed cTrack, which enables us to track the centrality of the nodes over time. We demonstrate the effectiveness and efficiency of our methods on several real data sets.

Original languageEnglish (US)
Title of host publicationLink Mining
Subtitle of host publicationModels, Algorithms, and Applications
PublisherSpringer New York
Number of pages26
ISBN (Electronic)9781441965158
ISBN (Print)9781441965141
StatePublished - 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Medicine


Dive into the research topics of 'Proximity tracking on dynamic bipartite graphs: Problem definitions and fast solutions'. Together they form a unique fingerprint.

Cite this