{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:22:08Z","timestamp":1760016128520},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2022,11,21]],"date-time":"2022-11-21T00:00:00Z","timestamp":1668988800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,1,17]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Pattern matching in big graphs is important for different modern applications. Recently, this problem was defined in terms of multiple extensions of graph simulation, to reduce complexity and capture more meaningful results. These results were achieved through the relaxation of commonly used constraint in subgraph isomorphism pattern matching. Nevertheless, these graph simulation variant models are still too strict to provide results in many cases, especially when analyzed graphs contain anomalies and incomplete information. To deal with this issue, we introduce a new graph pattern matching (GPM) method, called partial simulation, capable of retrieving matches despite missing parts of the pattern graph, such as vertices and\/or edges. Furthermore, considering the number and inequality of the outputs, we define a relevance function to compute a value expressing how each match vertex respects the pattern graph. Similarly, we define partial dual simulation GPM that returns vertices that satisfy a part of the dual simulation constraints and assigns a relevance value to them. Additionally, we provide distributed scalable algorithms to evaluate the proposed partial simulation methods based on the distributed vertex-centric programming paradigm. Finally, our experiments on real-world data graphs demonstrate the effectiveness of the proposed models and the efficiency of their associated algorithms.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac161","type":"journal-article","created":{"date-parts":[[2022,11,21]],"date-time":"2022-11-21T15:39:16Z","timestamp":1669045156000},"page":"110-126","source":"Crossref","is-referenced-by-count":2,"title":["Distributed Partial Simulation for Graph Pattern Matching"],"prefix":"10.1093","volume":"67","author":[{"given":"Aissam","family":"Aouar","sequence":"first","affiliation":[{"name":"Ecole Millitaire Polytechnique , BP 17, Bordj el Bahri, Algiers 16111, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sa\u00efd","family":"Yahiaoui","sequence":"additional","affiliation":[{"name":"CERIST Research Center on Scientific and Technical Information , Ben Aknoun, Algiers 16030, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lamia","family":"Sadeg","sequence":"additional","affiliation":[{"name":"Ecole Millitaire Polytechnique , BP 17, Bordj el Bahri, Algiers 16111, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Nouali-Taboudjemat","sequence":"additional","affiliation":[{"name":"CERIST Research Center on Scientific and Technical Information , Ben Aknoun, Algiers 16030, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kadda","family":"Beghdad Bey","sequence":"additional","affiliation":[{"name":"Ecole Millitaire Polytechnique , BP 17, Bordj el Bahri, Algiers 16111, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,11,21]]},"reference":[{"key":"2024012011484317600_ref1"},{"key":"2024012011484317600_ref2","first-page":"45","volume-title":"AAAI Fall Symposium: Capturing and Using Patterns for Evidence Detection","author":"Gallagher","year":"2006"},{"key":"2024012011484317600_ref3","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An algorithm for subgraph isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. ACM"},{"key":"2024012011484317600_ref4","first-page":"183","volume-title":"2009 IEEE\/WIC\/ACM Int. Joint Conf. on Web Intelligence and Intelligent Agent Technology","author":"Boldi","year":"2009"},{"key":"2024012011484317600_ref5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.jcss.2015.06.007","article-title":"Answering \u201cwhy empty?\u201d and \u201cwhy so many?\u201d queries in graph databases","volume":"82","author":"Vasilyeva","year":"2016","journal-title":"J. Comput. Syst. Sci."},{"key":"2024012011484317600_ref6","first-page":"452","volume-title":"12th Int. Conf. on Information Fusion","author":"Stotz","year":"2009"},{"key":"2024012011484317600_ref7","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.inffus.2013.05.006","article-title":"A fuzzy graph matching approach in intelligence analysis and maintenance of continuous situational awareness","volume":"18","author":"Gross","year":"2014","journal-title":"Inf. Fusion"},{"key":"2024012011484317600_ref8","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1142\/S0218001404003228","article-title":"Thirty years of graph matching in pattern recognition","volume":"18","author":"Conte","year":"2004","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"2024012011484317600_ref9","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-1-4419-6045-0_7","volume-title":"Managing and Mining Graph Data","author":"Riesen","year":"2010"},{"key":"2024012011484317600_ref10","doi-asserted-by":"crossref","first-page":"264","DOI":"10.14778\/1920841.1920878","article-title":"Graph pattern matching: from intractable to polynomial time","volume":"3","author":"Fan","year":"2010","journal-title":"Proc. VLDB Endowment"},{"key":"2024012011484317600_ref11","doi-asserted-by":"crossref","first-page":"310","DOI":"10.14778\/2095686.2095690","article-title":"Capturing topology in graph pattern matching","volume":"5","author":"Ma","year":"2011","journal-title":"Proc. VLDB Endowment"},{"key":"2024012011484317600_ref12","first-page":"567","volume-title":"Proc. of the 8th IEEE Int. Conf. on Collaborative Computing: Networking, Applications and Worksharing","author":"Fard","year":"2012"},{"key":"2024012011484317600_ref13","first-page":"1","article-title":"Harvesting and analysis of weak signals for detecting lone wolf terrorists","volume":"2","author":"Brynielsson","year":"2013","journal-title":"Secur. Inf."},{"key":"2024012011484317600_ref14","first-page":"24","article-title":"Article: a survey on social network analysis for counter-terrorism","volume":"112","author":"Choudhary","year":"2015","journal-title":"Int. J. Comput. Appl."},{"key":"2024012011484317600_ref15","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1111\/1556-4029.13676","article-title":"Lone actor terrorist attack planning and preparation: a data-driven analysis","volume":"63","author":"Schuurman","year":"2018","journal-title":"J. Forensic Sci."},{"key":"2024012011484317600_ref16","volume-title":"Proc. Conf. Civil and Military Readiness","author":"Svenson","year":"2006"},{"key":"2024012011484317600_ref17","first-page":"43","article-title":"Mapping networks of terrorist cells","volume":"24","author":"Krebs","year":"2002","journal-title":"Connections"},{"key":"2024012011484317600_ref18","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0378-8733(91)90008-H","article-title":"The application of network analysis to criminal intelligence: an assessment of the prospects","volume":"13","author":"Sparrow","year":"1991","journal-title":"Social Netw."},{"key":"2024012011484317600_ref19","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1145\/971617.971643","article-title":"Graph-based technologies for intelligence analysis","volume":"47","author":"Coffman","year":"2004","journal-title":"Commun. ACM"},{"key":"2024012011484317600_ref20","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub) graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2024012011484317600_ref21","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1109\/SFCS.1995.492576","volume-title":"Proc. IEEE 36th Annual Foundations of Computer Science","author":"Henzinger","year":"1995"},{"key":"2024012011484317600_ref22","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1109\/BigData.2013.6691601","volume-title":"2013 IEEE Int. Conf. on Big Data","author":"Fard","year":"2013"},{"key":"2024012011484317600_ref23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3439724","article-title":"A survey on distributed graph pattern matching in massive graphs","volume":"54","author":"Bouhenni","year":"2021","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"2024012011484317600_ref24","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/ICDE.2011.5767858","volume-title":"2011 IEEE 27th International Conference on Data Engineering (ICDE)","author":"Fan","year":"2011"},{"key":"2024012011484317600_ref25","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1093\/comjnl\/bxu159","article-title":"PRS: parallel relaxation simulation for massive graphs","volume":"59","author":"Gao","year":"2016","journal-title":"Comput. J."},{"key":"2024012011484317600_ref26","first-page":"1","article-title":"Diversified top-k search with relaxed graph simulation","volume":"9","author":"Habi","year":"2019","journal-title":"Social Netw. Anal. Mining"},{"key":"2024012011484317600_ref27","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.14778\/2536258.2536263","article-title":"Diversified top-k graph pattern matching","volume":"6","author":"Fan","year":"2013","journal-title":"Proc. VLDB Endowment"},{"key":"2024012011484317600_ref28","first-page":"493","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases","author":"Chen","year":"2005"},{"key":"2024012011484317600_ref29","doi-asserted-by":"crossref","first-page":"533","DOI":"10.14778\/2735479.2735486","article-title":"Optimal enumeration: efficient top-k tree matching","volume":"8","author":"Chang","year":"2015","journal-title":"Proc. VLDB Endowment"},{"key":"2024012011484317600_ref30","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/1807167.1807184","volume-title":"Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data","author":"Malewicz","year":"2010"},{"key":"2024012011484317600_ref31","first-page":"599","volume-title":"11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14)","author":"Gonzalez","year":"2014"},{"key":"2024012011484317600_ref32","first-page":"95","article-title":"Spark: cluster computing with working sets","volume":"10","author":"Zaharia","year":"2010","journal-title":"HotCloud"},{"key":"2024012011484317600_ref33","volume-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec","year":"2014"},{"key":"2024012011484317600_ref34","first-page":"25","volume-title":"Proc. of the 1st ACM SIGCOMM Workshop on Social Networks (WOSN\u201908)","author":"Mislove","year":"2008"},{"key":"2024012011484317600_ref35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3381449","article-title":"JGraphT-a Java library for graph data structures and algorithms","volume":"46","author":"Michail","year":"2020","journal-title":"ACM Trans. Math. Softw."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/110\/56167590\/bxac161.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/110\/56167590\/bxac161.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:49:42Z","timestamp":1705751382000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/1\/110\/6832432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,21]]},"references-count":35,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,11,21]]},"published-print":{"date-parts":[[2024,1,17]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac161","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,1]]},"published":{"date-parts":[[2022,11,21]]}}}