Proximity tracking on time-evolving bipartite graphs

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

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

Abstract

Given an author-conference network that evolves over time, which are the conferences that a given author is most closely related with, and how do they change over time? Large time-evolving bipartite graphs appear 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. We propose pTrack and cTrack, which are based on random walk with restart, and use powerful matrix tools. Experiments on real data show that our methods are effective and efficient: the mining results agree with intuition; and we achieve up to 15-176 times speed-up, without any quality loss.

Original languageEnglish (US)
Title of host publicationSociety for Industrial and Applied Mathematics - 8th SIAM International Conference on Data Mining 2008, Proceedings in Applied Mathematics 130
PublisherSociety for Industrial and Applied Mathematics Publications
Pages704-715
Number of pages12
ISBN (Print)9781605603179
DOIs
StatePublished - 2008
Externally publishedYes
Event8th SIAM International Conference on Data Mining 2008, Applied Mathematics 130 - Atlanta, GA, United States
Duration: Apr 24 2008Apr 26 2008

Publication series

NameSociety for Industrial and Applied Mathematics - 8th SIAM International Conference on Data Mining 2008, Proceedings in Applied Mathematics 130
Volume2

Other

Other8th SIAM International Conference on Data Mining 2008, Applied Mathematics 130
Country/TerritoryUnited States
CityAtlanta, GA
Period4/24/084/26/08

ASJC Scopus subject areas

  • Information Systems
  • Software
  • Signal Processing
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Proximity tracking on time-evolving bipartite graphs'. Together they form a unique fingerprint.

Cite this