Database Seminar

  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University

Com2: Fast Automatic Discovery of Temporal (’Comet’) Communities

Given a large network, changing over time, how can we find patterns and anomalies? We propose Com2, a novel and fast, incremental tensor analysis approach which can discover both transient and periodic/repeating communities. The method is (a) scalable, being linear on the input size (b) general, (c) needs no user-defined parameters and (d) effective, returning results that agree with intuition.

We apply our method on real datasets, including a phone-call network and a computer-traffic network. The phone call network consists of 4 million mobile users, with 51 million edges (phonecalls), over 14 days. Com2 spots intuitive patterns, that is, temporal communities (comet communities). We report our findings, which include large ’star’-like patterns, near-bipartite- cores, as well as tiny groups (5 users), calling each other hundreds of times within a few days.

This is joint work with Spiros Papadimitriou, Stephan Gunnemann, Christos Faloutsos, Prithwish Basu, Ananthram Swami, Evangelos E. Papalexakis and Danai Koutra.

For More Information, Please Contact: