2015 TimeCrunchInterpretableDynamicG

• (Shah et al., 2015) ⇒ Neil Shah, Danai Koutra, Tianmin Zou, Brian Gallagher, and Christos Faloutsos. (2015). “TimeCrunch: Interpretable Dynamic Graph Summarization.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783321

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+TimeCrunch%3A+Interpretable+Dynamic+Graph+Summarization
• http://dl.acm.org/citation.cfm?id=2783258.2783321&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; clustering; compression; dynamic graph; network; summarization

Abstract

How can we describe a large, dynamic graph over time? Is it random? If not, what are the most apparent deviations from randomness -- a dense block of actors that persists over time, or perhaps a star with many satellite nodes that appears with some fixed periodicity? In practice, these deviations indicate patterns -- for example, botnet attackers forming a bipartite core with their victims over the duration of an attack, family members bonding in a clique-like fashion over a difficult period of time, or research collaborations forming and fading away over the years. Which patterns exist in real-world dynamic graphs, and how can we find and rank them in terms of importance? These are exactly the problems we focus on in this work. Our main contributions are (a) formulation: we show how to formalize this problem as minimizing the encoding cost in a data compression paradigm, (b) algorithm: we propose TIMECRUNCH, an effective, scalable and parameter-free method for finding coherent, temporal patterns in dynamic graphs and (c) practicality: we apply our method to several large, diverse real-world datasets with up to 36 million edges and 6.3 million nodes. We show that TIMECRUNCH is able to compress these graphs by summarizing important temporal structures and finds patterns that agree with intuition.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 TimeCrunchInterpretableDynamicG	Christos Faloutsos Brian Gallagher Danai Koutra Neil Shah Tianmin Zou			TimeCrunch: Interpretable Dynamic Graph Summarization				10.1145/2783258.2783321		2015