Discovery of “comet” communities in temporal and labeled graphs Com (Formula presented.)

Miguel Araujo, Stephan Günnemann, Spiros Papadimitriou, Christos Faloutsos, Prithwish Basu, Ananthram Swami, Evangelos E. Papalexakis, Danai Koutra

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

While the analysis of unlabeled networks has been studied extensively in the past, finding patterns in different kinds of labeled graphs is still an open challenge. Given a large edge-labeled network, e.g., a time-evolving network, how can we find interesting patterns? We propose Com (Formula presented.)  , a novel, fast and incremental tensor analysis approach which can discover communities appearing over subsets of the labels. 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 to real datasets, including a phone call network, a computer-traffic network and a flight information network. The phone call network consists of 4 million mobile users, with 51 million edges (phone calls), over 14 days, while the flights dataset consists of 7733 airports and 5995 airline companies flying 67,663 different routes. We show that Com (Formula presented.)   spots intuitive patterns regarding edge labels that carry temporal or other discrete information. Our findings include large “star”-like patterns, near-bipartite cores, as well as tiny groups (five users), calling each other hundreds of times within a few days. We also show that we are able to automatically identify competing airline companies.

Original languageEnglish (US)
Pages (from-to)657-677
Number of pages21
JournalKnowledge and Information Systems
Volume46
Issue number3
DOIs
StatePublished - Mar 1 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Community detection
  • Edge labels
  • Temporal data
  • Tensor decomposition

Fingerprint

Dive into the research topics of 'Discovery of “comet” communities in temporal and labeled graphs Com (Formula presented.)'. Together they form a unique fingerprint.

Cite this