Detecting dynamic patterns in dynamic graphs using subgraph isomorphism
Authors: 
Kamaldeep Singh Oberoi, Géraldine Del Mondo, Benoît Gaüzère, Yohan Dupuis, Pascal VasseurAuthors Info & Claims
Pages 1205 - 1221
Abstract
Graphs have been used in different fields of research for performing structural analysis of various systems. In order to compare the structure of two systems, the correspondence between their graphs has to be verified. The problem of graph matching, especially subgraph isomorphism (SI), has been well studied in case of static graphs. However, many applications require incorporating temporal information, making the corresponding graphs dynamic. In this paper, we apply SI to detect dynamic patterns in dynamic graphs. We propose an algorithm for induced SI to detect all the matchings for a given pattern graph while considering snapshot-based representation of dynamic graphs and taking into account the chronological order of these snapshots. This is the novelty of the proposed approach since the existing state-of-the-art algorithms model dynamic graphs using an aggregated model with time-stamped edges. To the best of our knowledge, there does not exist another approach which considers snapshot-based representation of dynamic pattern and dynamic target graphs for this problem. We discussed the time complexity of our algorithm and tested its performance while comparing it with two existing algorithms using the real-world datasets. It was found that our algorithm is the second best overall in terms of the execution time. The results are promising given the fact that the choice of dynamic graph model affects the algorithmic design for solving the problem of SI. For the applications where aggregated model of dynamic graphs is not applicable and snapshot-based representation is indispensable, our algorithm can be directly applied as opposed to the existing ones.
References
[1]
Conte D, Foggia P, Vento M, and Sansone C Thirty years of graph matching in pattern recognition Int J Pattern Recognit Artif Intell 2004 18 3 265-298
[2]
Bonnici V, Giugno R, Pulvirenti A, Shasha D, and Ferro A A subgraph isomorphism algorithm and its application to biochemical data BMC Bioinform 2013 14 7 13
[3]
Fan W (2012) Graph pattern matching revised for social network analysis. In: Proceedings of the 15th international conference on database theory, pp 8–21.
[4]
Diot F, Fromont E, Jeudy B, Marilly E, and Martinot O Flach PA, De Bie T, and Cristianini N Graph mining for object tracking in videos Machine learning and knowledge discovery in databases 2012 Berlin Springer 394-409
[5]
Semertzidis K and Pitoura E Top- durable graph pattern queries on temporal graphs IEEE Trans Knowl Data Eng 2019 31 1 181-194
[6]
Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: 10th International conference on web search and data mining. ACM, New York, NY, USA, pp 601–610.
[7]
Mackey P, Porterfield K, Fitzhenry E, Choudhury S, Chin G (2018) A chronological edge-driven approach to temporal subgraph isomorphism. In: 2018 IEEE international conference on big data, pp 3972–3979.
[8]
Locicero G, Micale G, Pulvirenti A, Ferro A (2021) TemporalRI: a subgraph isomorphism algorithm for temporal networks. In: Benito RM, Cherifi C, Cherifi H, Moro E, Rocha LM, Sales-Pardo M (eds) Complex networks & their applications IX. Springer, Cham, pp 675–687.
[9]
Micale G, Locicero G, Pulvirenti A, and Ferro A TemporalRI: subgraph isomorphism in temporal networks with multiple contacts Appl Netw Sci 2021 6 1 55-15522
[10]
Alakörkkö T, Saramäki J (2020) Circadian rhythms in temporal-network connectivity. Chaos Interdiscip J Nonlinear Sci 30(9):093115.
[11]
Kovanen L, Kaski K, Kertész J, and Saramäki J Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences Proc Natl Acad Sci 2013 110 45 18070-18075
[12]
Rossetti G and Cazabet R Community discovery in dynamic networks: a survey ACM Comput Surv 2018 51 2 1-37
[13]
Divakaran A and Mohan A Temporal link prediction: a survey New Gener Comput 2020 38 1 213-258
[14]
Tang J, Scellato S, Musolesi M, Mascolo C, and Latora V Small-world behavior in time-varying graphs Phys Rev E 2010 81
[15]
Crawford J and Milenković T Cluenet: clustering a temporal network based on topological similarity rather than denseness PLoS ONE 2018 13 5 1-25
[16]
Carletti V, Foggia P, Saggese A, and Vento M Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3 IEEE Trans Pattern Anal Mach Intell 2018 40 4 804-818
[17]
Carletti V, Foggia P, Greco A, Saggese A, and Vento M Comparing performance of graph matching algorithms on huge graphs Pattern Recognit Lett 2018
[18]
Vento M A long trip in the charming world of graphs for pattern recognition Pattern Recognit 2015 48 2 291-301
[19]
Cook SA (1971) The complexity of theorem-proving procedures. In: Third annual ACM symposium on theory of computing (STOC’71). ACM, New York, USA, pp 151–158.
[20]
Ullmann JR An algorithm for subgraph isomorphism J ACM 1976 23 1 31-42
[21]
Schmidt DC and Druffel LE A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices J ACM 1976 23 3 433-445
[22]
Cordella LP, Foggia P, Sansone C, and Vento M A (sub)graph isomorphism algorithm for matching large graphs IEEE Trans Pattern Anal Mach Intell 2004 26 10 1367-1372
[23]
Almasri I, Gao X, Fedoroff N (2014) Quick mining of isomorphic exact large patterns from large graphs. In: 2014 IEEE international conference on data mining workshop, pp 517–524.
[24]
McGregor JJ Relational consistency algorithms and their application in finding subgraph and graph isomorphisms Inf Sci 1979 19 3 229-250
[25]
Solnon C Alldifferent-based filtering for subgraph isomorphism Artif Intell 2010 174 12 850-864
[26]
Ullmann JR Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism J Exp Algorithmics 2011 15 1-61116164
[27]
Giugno R, Shasha D (2002) Graphgrep: a fast and universal method for querying graphs. In: Object recognition supported by user interaction for service robots, vol 2, pp 112–1152.
[28]
He H, Singh AK (2008) Graphs-at-a-time: query language and access methods for graph databases. In: International conference on management of data. ACM, New York, NY, USA, pp 405–418.
[29]
Kovanen L, Karsai M, Kaski K, Kertész J, Saramäki, J (2011) Temporal motifs in time-dependent networks. J Stat Mech Theory Exp 11:11005.
[30]
Redmond U, Cunningham P (2016) Subgraph isomorphism in temporal networks. arXiv preprint arXiv:1605.02174
[31]
Choudhury S, Holder L, Chin, G, Agarwal K, Feo J (2015) A selectivity based approach to continuous pattern detection in streaming graphs. In: 18th International conference on extending database technology, pp 157–168
[32]
Sun X, Tan Y, Wu Q, Wang J (2017) Hasse diagram based algorithm for continuous temporal subgraph query in graph stream. In: 6th International conference on computer science and network technology, pp 241–246.
[33]
Fan, W, Li J, Luo J, Tan Z, Wang X, Wu Y (2011) Incremental graph pattern matching. In: International conference on management of data. ACM, New York, NY, USA, pp 925–936.
[34]
Schiller B, Jager S, Hamacher K, and Strufe T Dediu A-H, Hernández-Quiroz F, Martín-Vide C, and Rosenblueth DA Stream—a stream-based algorithm for counting motifs in dynamic graphs Algorithms for computational biology 2015 Cham Springer 53-67
[35]
Mukherjee K, Hasan MM, Boucher C, and Kahveci T Counting motifs in dynamic networks BMC Syst Biol 2018 12 1 1-12
[36]
Berlingerio M, Bonchi F, Bringmann B, Gionis A (2009) Mining graph evolution rules. In: Buntine W, Grobelnik M, Mladenić D, Shawe-Taylor J (eds) Machine learning and knowledge discovery in databases. Springer, pp 115–130.
[37]
Cakmak E, Schlegel U, Jäckle D, Keim D, Schreck T (2021) Multiscale snapshots: visual analysis of temporal summaries in dynamic graphs. IEEE Trans Vis Comput Graph 27(2):517–527.
[38]
Mccreesh C, Prosser P, Solnon C, and Trimble J When subgraph isomorphism is really hard, and why this matters for graph databases J Artif Intell Res 2018 61 723-759
[39]
Leskovec J, Krevl A (2014) SNAP datasets: stanford large network dataset collection. http://snap.stanford.edu/data. Accessed Jan 2022
Index Terms
- Detecting dynamic patterns in dynamic graphs using subgraph isomorphism
Index terms have been assigned to the content through auto-classification.
Recommendations
Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs
Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as ...
The subgraph isomorphism problem for outerplanar graphs
This paper deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. We show that SUBOUTISOM remains NP-complete even when the strongest connectivity ...
Parallel Planar Subgraph Isomorphism and Vertex Connectivity
SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and ArchitecturesWe present the first parallel fixed-parameter algorithm for subgraph isomorphism in planar graphs, bounded-genus graphs, and, more generally, all minor-closed graphs of locally bounded treewidth. Our randomized low depth algorithm has a near-linear work ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 27 February 2023
Accepted: 24 January 2023
Received: 24 January 2022
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in