TY - JOUR
T1 - Discovery of “comet” communities in temporal and labeled graphs Com (Formula presented.)
AU - Araujo, Miguel
AU - Günnemann, Stephan
AU - Papadimitriou, Spiros
AU - Faloutsos, Christos
AU - Basu, Prithwish
AU - Swami, Ananthram
AU - Papalexakis, Evangelos E.
AU - Koutra, Danai
N1 - Publisher Copyright:
© 2015, Springer-Verlag London.
PY - 2016/3/1
Y1 - 2016/3/1
N2 - 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.
AB - 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.
KW - Community detection
KW - Edge labels
KW - Temporal data
KW - Tensor decomposition
UR - http://www.scopus.com/inward/record.url?scp=84958160628&partnerID=8YFLogxK
U2 - 10.1007/s10115-015-0847-2
DO - 10.1007/s10115-015-0847-2
M3 - Article
AN - SCOPUS:84958160628
SN - 0219-1377
VL - 46
SP - 657
EP - 677
JO - Knowledge and Information Systems
JF - Knowledge and Information Systems
IS - 3
ER -