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

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

8 Zitate (Scopus)

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.

OriginalspracheEnglisch
Seiten (von - bis)657-677
Seitenumfang21
FachzeitschriftKnowledge and Information Systems
Jahrgang46
Ausgabenummer3
DOIs
PublikationsstatusVeröffentlicht - 1 März 2016
Extern publiziertJa

Fingerprint

Untersuchen Sie die Forschungsthemen von „Discovery of “comet” communities in temporal and labeled graphs Com (Formula presented.)“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren