Discovery of "comet" communities in temporal and labeled graphs Com$$^2$$2 . Issue 3 (March 2016)

• Record Type: Journal Article
• Authors: Araujo, Miguel; Günnemann, Stephan; Papadimitriou, Spiros; Faloutsos, Christos; Basu, Prithwish; Swami, Ananthram; Papalexakis, Evangelos; Koutra, Danai
• Is Part Of: Knowledge and information systems. Volume 46:Issue 3(2016:Mar.)
• Page Start: 657
• Page End: 677
• Publication Date: 2016-03
• Subjects: Community detection -- Temporal data -- Edge labels -- Tensor decomposition; Expert systems (Computer science) -- Periodicals; Information storage and retrieval systems -- Periodicals; 006.33
• DOI: 10.1007/s10115-015-0847-2
• Languages: English
• ISSNs: 0219-1377

Abstract

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 proposeCom $$^2$$ 2 , 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 thatCom $$^2$$ 2 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.