Discovery of "comet" communities in temporal and labeled graphs COM2

dc.contributor.author Miguel Ramos Araújo en
dc.contributor.author Guennemann,S en
dc.contributor.author Papadimitriou,S en
dc.contributor.author Faloutsos,C en
dc.contributor.author Basu,P en
dc.contributor.author Swami,A en
dc.contributor.author Papalexakis,E en
dc.contributor.author Koutra,D en
dc.date.accessioned 2018-01-18T12:11:52Z
dc.date.available 2018-01-18T12:11:52Z
dc.date.issued 2016 en
dc.description.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 , 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 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. en
dc.identifier.uri http://repositorio.inesctec.pt/handle/123456789/6928
dc.identifier.uri http://dx.doi.org/10.1007/s10115-015-0847-2 en
dc.language eng en
dc.relation 6311 en
dc.rights info:eu-repo/semantics/openAccess en
dc.title Discovery of "comet" communities in temporal and labeled graphs COM2 en
dc.type article en
dc.type Publication en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
P-00F-K0G.pdf
Size:
1.86 MB
Format:
Adobe Portable Document Format
Description: