[StreamGraph] Proximity Tracking on Time-Evolving Bipartite Graphs

Hanghang Tong, Spiros Papadimitriou, Philip S. Yu, Christos Faloutsos, Proximity Tracking on Time-Evolving Bipartite Graphs, SDM 2008, Atlanta, USA. [PDF]   Best paper award

http://www.siam.org/proceedings/datamining/2008/dm08_64_Tong.pdf


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