Proximity Tracking on Time-Evolving Bipartite Graphs
Proximity Tracking on Time-Evolving Bipartite Graphs
复制标题
DOI：
10.1137/1.9781611972788.64
复制
发表时间：
2008-10
期刊：
影响因子：
--
通讯作者：
Hanghang Tong;S. Papadimitriou;Philip S. Yu;C. Faloutsos
中科院分区：
文献类型：
--
作者：
Hanghang Tong;S. Papadimitriou;Philip S. Yu;C. Faloutsos
给定一个随时间发展的作者-会议网络，给定的作者与哪些会议关系最密切，它们是如何随着时间的推移而变化的？大型时间演化二部图出现在许多环境中，如社交网络、共引、市场篮子分析和协作过滤。我们的目标是监测(I)单个节点的中心性(例如，谁是最重要的作者？)；以及(Ii)两个节点或节点集的接近程度(例如，对于特定会议，谁是最重要的作者？)此外，我们希望高效、渐进地完成这项工作，并提供“任何时间”的答案。我们提出了基于随机游走和重启的pTrack和cTrack，并使用了强大的矩阵工具。在真实数据上的实验表明，我们的方法是有效和高效的：挖掘结果与直觉一致，并且在没有任何质量损失的情况下，我们获得了高达15∼176倍的加速。
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.