research-article

Diversified Temporal Subgraph Pattern Mining

Authors:

John C.S. LuiAuthors Info & Claims

KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Pages 1965 - 1974

https://doi.org/10.1145/2939672.2939848

Published: 13 August 2016 Publication History

Abstract

Many graphs in real-world applications, such as telecommunications networks, social-interaction graphs and co-authorship graphs, contain temporal information. However, existing graph mining algorithms fail to exploit these temporal information and the resulting subgraph patterns do not contain any temporal attribute. In this paper, we study the problem of mining a set of diversified temporal subgraph patterns from a temporal graph, where each subgraph is associated with the time interval that the pattern spans. This problem motivates important applications such as finding social trends in social networks, or detecting temporal hotspots in telecommunications networks. We propose a divide-and-conquer algorithm along with effective pruning techniques, and our approach runs 2 to 3 orders of magnitude faster than a baseline algorithm and obtains high-quality temporal subgraph patterns in real temporal graphs.

References

[1]

J. Abello, M. G. C. Resende, and S. Sudarsky. Massive quasi-clique detection. In LATIN, pages 598--612, 2002.

Digital Library

[2]

G. Ausiello, N. Boria, A. Giannakos, G. Lucarelli, and V. T. Paschos. Online maximum k-coverage. In Fundamentals of Computation Theory, pages 181--192. Springer, 2011.

Digital Library

[3]

V. Batagelj and M. Zaversnik. An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS/0310049, 2003.

[4]

M. Bazzi, M. A. Porter, S. Williams, M. McDonald, D. J. Fenn, and S. D. Howison. Community detection in temporal multilayer networks, with an application to correlation networks. Multiscale Modeling & Simulation, 14(1):1--41, 2016.

Digital Library

[5]

M. Benkert, J. Gudmundsson, F. Hübner, and T. Wolle. Reporting flock patterns. In ESA, pages 660--671, 2006.

Digital Library

[6]

B. Boden, S. Günnemann, H. Hoffmann, and T. Seidl. Mining coherent subgraphs in multi-layer graphs with edge labels. In KDD, pages 1258--1266. ACM, 2012.

Digital Library

[7]

C. Bron and J. Kerbosch. Finding all cliques of an undirected graph (algorithm 457). Commun. ACM, 16(9):575--576, 1973.

Digital Library

[8]

A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387--408, 2012.

Digital Library

[9]

G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM J. Comput., 18(1):30--55, 1989.

Digital Library

[10]

M.-G. Gong, L.-J. Zhang, J.-J. Ma, and L.-C. Jiao. Community detection in dynamic social networks based on multiobjective immune algorithm. Journal of Computer Science and Technology, 27(3):455--467, 2012.

[11]

J. Gudmundsson and M. J. van Kreveld. Computing longest duration flocks in trajectory data. In GIS, pages 35--42, 2006.

Digital Library

[12]

P. Holme and J. Saramäki. Temporal networks. CoRR, abs/1108.1780, 2011.

[13]

H. Jeung, H. T. Shen, and X. Zhou. Convoy queries in spatio-temporal databases. In ICDE, pages 1457--1459, 2008.

Digital Library

[14]

S. Khuller and B. Saha. On finding dense subgraphs. In ICALP, pages 597--608, 2009.

Digital Library

[15]

G. Kossinets, J. M. Kleinberg, and D. J. Watts. The structure of information pathways in a social communication network. In KDD, pages 435--443, 2008.

Digital Library

[16]

V. Kostakos. Temporal graphs. Physica A: Statistical Mechanics and its Applications, 388(6):1007--1023, 2009.

[17]

V. E. Lee, N. Ruan, R. Jin, and C. C. Aggarwal. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data, pages 303--336. 2010.

[18]

Z. Li, B. Ding, J. Han, and R. Kays. Swarm: Mining relaxed temporal moving object clusters. PVLDB, 3(1):723--734, 2010.

Digital Library

[19]

Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In WWW, pages 685--694. ACM, 2008.

Digital Library

[20]

G. Liu and L. Wong. Effective pruning techniques for mining quasi-cliques. In PKDD, pages 33--49, 2008.

Digital Library

[21]

J. Mugan, E. McDermid, A. McGrew, and L. Hitt. Identifying groups of interest through temporal analysis and event response monitoring. In Intelligence and Security Informatics (ISI), 2013 IEEE International Conference on, pages 185--190. IEEE, 2013.

[22]

M. Müller-Hannemann, F. Schulz, D. Wagner, and C. D. Zaroliagis. Timetable information: Models and algorithms. In ATMOS, pages 67--90, 2004.

Digital Library

[23]

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical Programming, 14(1):265--294, 1978.

Digital Library

[24]

R. K. Pan and J. Saramäki. Path lengths, correlations, and centrality in temporal networks. Phys. Rev. E, 84:016105, 2011.

[25]

P. M. Pardalos and S. Rebennack. Computational challenges with cliques, quasi-cliques and clique partitions in graphs. In Experimental Algorithms, pages 13--22. Springer, 2010.

Digital Library

[26]

J. Pei, D. Jiang, and A. Zhang. On mining cross-graph quasi-cliques. In KDD, pages 228--238, 2005.

Digital Library

[27]

N. Santoro, W. Quattrociocchi, P. Flocchini, A. Casteigts, and F. Amblard. Time-varying graphs and social network analysis: Temporal indicators and metrics. CoRR, abs/1102.0629, 2011.

[28]

J. Tang, M. Musolesi, C. Mascolo, and V. Latora. Temporal distance metrics for social network analysis. In WOSN, pages 31--36, 2009.

Digital Library

[29]

J. Tang, M. Musolesi, C. Mascolo, and V. Latora. Characterising temporal distance and reachability in mobile and online social networks. Computer Communication Review, 40(1):118--124, 2010.

Digital Library

[30]

C. E. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, and M. A. Tsiarli. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In KDD, pages 104--112, 2013.

Digital Library

[31]

J. Wang and J. Cheng. Truss decomposition in massive networks. PVLDB, 5(9):812--823, 2012.

Digital Library

[32]

H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. Path problems in temporal graphs. PVLDB, 7(9):721--732, 2014.

Digital Library

[33]

J. Xie, M. Chen, and B. K. Szymanski. Labelrankt: Incremental community detection in dynamic networks via label propagation. In Proceedings of the Workshop on Dynamic Networks Management and Mining, pages 25--32. ACM, 2013.

Digital Library

[34]

B.-M. B. Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci., 14(2):267--285, 2003.

[35]

L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang. Diversified top-k clique search. In ICDE, pages 387--398, 2015.

Cited By

Wu YSun RWang XWen DZhang YQin LLin X(2024)Efficient Maximal Frequent Group Enumeration in Temporal Bipartite GraphsProceedings of the VLDB Endowment10.14778/3681954.368199717:11(3243-3255)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3681997
Agarwal PHu XSintos SYang J(2024)On Reporting Durable Patterns in Temporal Proximity GraphsProceedings of the ACM on Management of Data10.1145/36511442:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651144
Zhang TGao YZhao JChen LJin LYang ZCao BFan JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficient Exact and Approximate Betweenness Centrality Computation for Temporal GraphsProceedings of the ACM Web Conference 202410.1145/3589334.3645438(2395-2406)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645438
Show More Cited By

Index Terms

Diversified Temporal Subgraph Pattern Mining

Recommendations

Subgraph matching on temporal graphs
Abstract
Temporal graphs are graphs whose edges are associated with timestamps. Subgraph matching on temporal graphs retrieves temporal subgraphs whose edge timestamps satisfy user-specified temporal orders. In this paper, a temporal query ...
Temporal subgraph matching method for multi-connected temporal graph
Abstract
Temporal graph matching is used to find a matching subgraph set that satisfies temporal and topological information on the temporal graph. It is widely used in real scenarios and provides important support for big data mining and analysis. Most ...
Dense subgraph mining with a mixed graph model

In this paper we introduce a graph clustering method based on dense bipartite subgraph mining. The method applies a mixed graph model (both standard and bipartite) in a three-phase algorithm. First a seed mining method is applied to find seeds of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 2016

2176 pages

ISBN:9781450342322

DOI:10.1145/2939672

General Chairs:
Balaji Krishnapuram
IBM
,
Mohak Shah
Bosch
,
Program Chairs:
Alex Smola
Amazon
,
Charu Aggarwal
IBM
,
Dou Shen
Baidu
,
Rajeev Rastogi
Amazon

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 August 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Key Projects of Fundamental Research Program of Shanghai Municipal Commission of Science and Technology
Hong Kong GRF

Conference

KDD '16

Sponsor:

KDD '16: The 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 13 - 17, 2016

California, San Francisco, USA

Acceptance Rates

KDD '16 Paper Acceptance Rate 66 of 1,115 submissions, 6%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
542
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)6

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu YSun RWang XWen DZhang YQin LLin X(2024)Efficient Maximal Frequent Group Enumeration in Temporal Bipartite GraphsProceedings of the VLDB Endowment10.14778/3681954.368199717:11(3243-3255)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3681997
Agarwal PHu XSintos SYang J(2024)On Reporting Durable Patterns in Temporal Proximity GraphsProceedings of the ACM on Management of Data10.1145/36511442:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651144
Zhang TGao YZhao JChen LJin LYang ZCao BFan JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficient Exact and Approximate Betweenness Centrality Computation for Temporal GraphsProceedings of the ACM Web Conference 202410.1145/3589334.3645438(2395-2406)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645438
Huang KCui YYe QZhao YZhao XTian YZheng KHu HZhou X(2024)TED$^+$: Towards Discovering Top-k Edge-Diversified Patterns in a Graph DatabaseIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3312566(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3312566
Chang CLu CTeng SChang MHo YShen C(2024)Maximizing $(k,L)$-Core With Edge Augmentation in Multilayer GraphsIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.333209111:3(3931-3943)Online publication date: Jun-2024
https://doi.org/10.1109/TCSS.2023.3332091
Wu YSun RWang XZhang YQin LZhang WLin X(2024)Efficient Maximal Temporal Plex Enumeration2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00240(3098-3110)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00240
Huang CZhang QGuo DZhao XWang X(2023)Discovering Association Rules with Graph Patterns in Temporal NetworksTsinghua Science and Technology10.26599/TST.2021.901009028:2(344-359)Online publication date: Apr-2023
https://doi.org/10.26599/TST.2021.9010090
Ge YChen ZKong WLiu YWong RZhang S(2023)An Efficient Dynamic Programming Algorithm for Finding Group Steiner Trees in Temporal GraphsInternational Journal of Intelligent Systems10.1155/2023/19741612023(1-20)Online publication date: 21-Nov-2023
https://doi.org/10.1155/2023/1974161
Yu KLong C(2023)Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design ApproachProceedings of the ACM on Management of Data10.1145/36173311:3(1-26)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3617331
Xie HFang YXia YLuo WMa C(2023)On Querying Connected Components in Large Temporal GraphsProceedings of the ACM on Management of Data10.1145/35893151:2(1-27)Online publication date: 20-Jun-2023
https://doi.org/10.1145/3589315
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten