文章基本信息

标题：On Summarizing Large-Scale Dynamic Graphs
本地全文：下载
作者：Neil Shah ; Danai Koutra ; Lisa Jin 等
期刊名称：Bulletin of the Technical Committee on Data Engineering
出版年度：2017
卷号：40
期号：3
页码：75
出版社：IEEE Computer Society
摘要：How can we describe a large, dynamic graph over time? Is it random? If not, what are the mostapparent deviations from randomness – a dense block of actors that persists over time, or perhaps astar with many satellite nodes that appears with some fixed periodicity? In practice, these deviationsindicate patterns – for example, research collaborations forming and fading away over the years. Whichpatterns exist in real-world dynamic graphs, and how can we find and rank their importance? Theseare exactly the problems we focus on. Our main contributions are (a) formulation: we show how toformalize this problem as minimizing an information theoretic encoding cost, (b) algorithm: we proposeTIMECRUNCH, an effective and scalable method for finding coherent, temporal patterns in dynamicgraphs and (c) practicality: we apply our method to several large, diverse real-world datasets with upto 36 million edges and introduce our auxiliary ECOVIZ framework for visualizing and interacting withdynamic graphs which have been summarized by TIMECRUNCH. We show that TIMECRUNCH is ableto compress these graphs by summarizing important temporal structures and finds patterns that agreewith intuition.