Premium
Fast Monitoring Proximity and Centrality on Time‐evolving Bipartite Graphs
Author(s) -
Tong Hanghang,
Papadimitriou Spiros,
Yu Philip S.,
Faloutsos Christos
Publication year - 2008
Publication title -
statistical analysis and data mining: the asa data science journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.381
H-Index - 33
eISSN - 1932-1872
pISSN - 1932-1864
DOI - 10.1002/sam.10014
Subject(s) - centrality , computer science , bipartite graph , node (physics) , data mining , theoretical computer science , link (geometry) , graph , computer network , mathematics , combinatorics , engineering , structural engineering
Large bipartite graphs that 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. How do we monitor (i) the centrality of an individual node (e.g. which is the most important conference ), or (ii) the proximity of two nodes or sets of nodes (e.g. who are the most influential authors with respect to a particular conference )? How can we do this efficiently and incrementally? How can we provide ‘any‐time’ answers to interesting queries, with respect to node centrality or proximity? In this paper we propose pTrack and cTrack , which are based on RWR, 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. We demonstrate the effectiveness and efficiency of our methods on several real datasets. Copyright © 2008 Wiley Periodicals, Inc. Statistical Analysis and Data Mining 1: 000‐000, 2008