{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T02:44:03Z","timestamp":1781664243516,"version":"3.54.5"},"reference-count":57,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T00:00:00Z","timestamp":1661212800000},"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":[[2022,8,23]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a temporal network $\\mathcal{G}(\\mathcal{V}, \\mathcal{E}, \\mathcal{T})$, $(\\mathcal{X},[t_a,t_b])$ (where $\\mathcal{X} \\subseteq \\mathcal{V}(\\mathcal{G})$ and $[t_a,t_b] \\subseteq \\mathcal{T}$) is said to be a $(\\Delta, \\gamma)$-clique of $\\mathcal{G}$, if for every pair of vertices in $\\mathcal{X}$, there must exist at least $\\gamma$ links in each $\\Delta$ duration within the time interval $[t_a,t_b]$. Enumerating such maximal cliques is an important problem in temporal network analysis, as it reveals contact pattern among the nodes of $\\mathcal{G}$. In this article, we study the maximal $(\\Delta, \\gamma)$-clique enumeration problem in online setting; that is, the entire link set of the network is not known in advance, and the links are coming as a batch in an iterative fashion. Suppose, the link set till time stamp $T_{1}$ (i.e. $\\mathcal{E}^{T_{1}}$), and its corresponding $(\\Delta, \\gamma)$-clique set are known. In the next batch (till time $T_{2}$), a new set of links (denoted as $\\mathcal{E}^{(T_1,T_2]}$) is arrived. Now, the goal is to update the existing $(\\Delta, \\gamma)$-cliques to obtain the maximal $(\\Delta, \\gamma)$-cliques till time stamp $T_{2}$. We formally call this problem as the Maximal $(\\Delta, \\gamma)$-Clique Updation Problem for enumerating maximal $(\\Delta, \\gamma)$-cliques. For this, we propose an efficient updation approach that can be used to enumerate maximal $(\\Delta, \\gamma)$-cliques of a temporal network in online setting. We show that the proposed methodology is correct, and it has been analysed for its time and space requirement. An extensive set of experiments have been carried out with four benchmark temporal network datasets. The obtained results show that the proposed methodology is efficient both in terms of time and space to enumerate maximal $(\\Delta, \\gamma)$-cliques in online setting. Particularly, compared to it\u2019s off-line counterpart, the improvement caused by our proposed approach is in the order of hours and GB for computational time and space, respectively, in large dataset.<\/jats:p>","DOI":"10.1093\/comnet\/cnac027","type":"journal-article","created":{"date-parts":[[2022,9,23]],"date-time":"2022-09-23T20:29:09Z","timestamp":1663964949000},"source":"Crossref","is-referenced-by-count":3,"title":["An efficient updation approach for enumerating maximal (\u0394,<i>\u03b3<\/i>)-cliques of a temporal network"],"prefix":"10.1093","volume":"10","author":[{"given":"Suman","family":"Banerjee","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Jammu Department of Computer Science and Engineering, , Jagti, NH-44, PO Nagrota, Jammu, Jammu & Kashmir, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2177-9776","authenticated-orcid":false,"given":"Bithika","family":"Pal","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur Department of Computer Science and Engineering, , Kharagpur, West Midnapore, West Bengal, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2022,9,23]]},"reference":[{"key":"2022092320284029900_B1","volume-title":"Network Science","author":"Barab\u00e1si,","year":"2016"},{"key":"2022092320284029900_B2","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/s11280-012-0177-1","article-title":"Creation and growth of online social network","volume":"16","author":"Musial,","year":"2013","journal-title":"World Wide Web"},{"key":"2022092320284029900_B3","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/2481244.2481248","article-title":"Mining heterogeneous information networks: a structural analysis approach","volume":"14","author":"Sun,","year":"2013","journal-title":"ACM Sigkdd Explor. Newslett."},{"key":"2022092320284029900_B4","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1016\/j.physa.2008.11.021","article-title":"Temporal graphs","volume":"388","author":"Kostakos,","year":"2009","journal-title":"Physica A"},{"key":"2022092320284029900_B5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0202001","article-title":"The enumeration of maximal cliques of large graphs","volume":"2","author":"Akkoyunlu,","year":"1973","journal-title":"SIAM J. Comput."},{"key":"2022092320284029900_B6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2543629","article-title":"Listing all maximal cliques in large sparse real-world graphs","volume":"18","author":"Eppstein,","year":"2013","journal-title":"J. Exp. Algorithmics"},{"key":"2022092320284029900_B7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s41060-016-0022-1","article-title":"A fast and complete algorithm for enumerating pseudo-cliques in large graphs","volume":"2","author":"Zhai,","year":"2016","journal-title":"Int. J. Data Sci. Anal."},{"key":"2022092320284029900_B8","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1145\/2723372.2746478","article-title":"Efficient enumeration of maximal k-plexes","volume-title":"Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data","author":"Berlowitz,","year":"2015"},{"key":"2022092320284029900_B9","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.cor.2014.07.006","article-title":"Two-phase heuristics for the k-club problem","volume":"52","author":"Almeida,","year":"2014","journal-title":"Comput. Oper. Res."},{"key":"2022092320284029900_B10","doi-asserted-by":"crossref","first-page":"13","DOI":"10.14778\/2850469.2850471","article-title":"K-core decomposition of large networks on a single PC","volume":"9","author":"Khaouid,","year":"2015","journal-title":"Proc. VLDB Endow."},{"key":"2022092320284029900_B11","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1145\/2505515.2505751","article-title":"Linear-time enumeration of maximal k-edge-connected subgraphs in large networks by random contraction","volume-title":"Proceedings of the 22nd ACM International Conference on Information & Knowledge Management","author":"Akiba,","year":"2013"},{"key":"2022092320284029900_B12","volume-title":"Topological Structure and Analysis of Interconnection Networks","author":"Xu,","year":"2013"},{"key":"2022092320284029900_B13","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","article-title":"Algorithm 457: finding all cliques of an undirected graph","volume":"16","author":"Bron,","year":"1973","journal-title":"Commun. ACM"},{"key":"2022092320284029900_B14","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/978-3-642-20662-7_31","article-title":"Listing all maximal cliques in large sparse real-world graphs","volume-title":"International Symposium on Experimental Algorithms","author":"Eppstein,","year":"2011"},{"key":"2022092320284029900_B15","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1145\/1807167.1807217","article-title":"Finding maximal cliques in massive networks by h*-graph","volume-title":"Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data","author":"Cheng,","year":"2010"},{"key":"2022092320284029900_B16","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/2043652.2043654","article-title":"Finding maximal cliques in massive networks","volume":"36","author":"Cheng,","year":"2011","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"2022092320284029900_B17","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1145\/2567948.2577283","article-title":"Fast maximum clique algorithms for large graphs","volume-title":"Proceedings of the 23rd International Conference on World Wide Web","author":"Rossi,","year":"2014"},{"key":"2022092320284029900_B18","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1109\/ICDE.2015.7113288","article-title":"Mining maximal cliques from an uncertain graph","volume-title":"2015 IEEE 31st International Conference on Data Engineering (ICDE)","author":"Mukherjee,","year":"2015"},{"key":"2022092320284029900_B19","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1109\/TKDE.2016.2527643","article-title":"Enumeration of maximal cliques from an uncertain graph","volume":"29","author":"Mukherjee,","year":"2017","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2022092320284029900_B20","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1109\/ICDE.2010.5447891","article-title":"Finding top-k maximal cliques in an uncertain graph","volume-title":"2010 IEEE 26th International Conference on Data Engineering (ICDE 2010)","author":"Zou,","year":"2010"},{"key":"2022092320284029900_B21","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s41019-017-0033-5","article-title":"Efficient maximal clique enumeration over graph data","volume":"1","author":"Hou,","year":"2016","journal-title":"Data Sci. Eng."},{"key":"2022092320284029900_B22","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1109\/ICDE.2013.6544815","article-title":"Scalable maximum clique computation using MapReduce","volume-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE)","author":"Xiang,","year":"2013"},{"key":"2022092320284029900_B23","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-319-32049-6_16","article-title":"Parallelizing maximal clique enumeration over graph data","volume-title":"International Conference on Database Systems for Advanced Applications","author":"Chen,","year":"2016"},{"key":"2022092320284029900_B24","doi-asserted-by":"crossref","first-page":"C589","DOI":"10.1137\/14100018X","article-title":"Parallel maximum clique algorithms with applications to network analysis","volume":"37","author":"Rossi,","year":"2015","journal-title":"SIAM J. Sci. Comput."},{"key":"2022092320284029900_B25","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.jpdc.2009.01.003","article-title":"A scalable, parallel algorithm for maximal clique enumeration","volume":"69","author":"Schmidt,","year":"2009","journal-title":"J. Parallel Distrib. Comput."},{"key":"2022092320284029900_B26","doi-asserted-by":"crossref","first-page":"1240","DOI":"10.1145\/2339530.2339724","article-title":"Fast algorithms for maximal clique enumeration with limited memory","volume-title":"Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Cheng,","year":"2012"},{"key":"2022092320284029900_B27","first-page":"1517","article-title":"Revealing contact patterns among high-school students using maximal cliques in link streams","volume-title":"2015 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)","author":"Viard,","year":"2015"},{"key":"2022092320284029900_B28","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.tcs.2015.09.030","article-title":"Computing maximal cliques in link streams","volume":"609","author":"Viard,","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2022092320284029900_B29","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1145\/3297001.3297015","article-title":"On the enumeration of maximal ($\\Delta$, $\\gamma$)-cliques of a temporal network","volume-title":"Proceedings of the ACM India Joint International Conference on Data Science and Management of Data","author":"Banerjee,","year":"2019"},{"key":"2022092320284029900_B30","doi-asserted-by":"crossref","first-page":"e107878","DOI":"10.1371\/journal.pone.0107878","article-title":"Contact patterns among high school students","volume":"9","author":"Fournet,","year":"2014","journal-title":"PLoS One"},{"key":"2022092320284029900_B31","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1002\/asi.21015","article-title":"Patterns and dynamics of users\u2019 behavior and interaction: network analysis of an online community","volume":"60","author":"Panzarasa,","year":"2009","journal-title":"J. Am. Soc. Inform. Sci. Technol."},{"key":"2022092320284029900_B32","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1080\/17445760.2012.668546","article-title":"Time-varying graphs and dynamic networks","volume":"27","author":"Casteigts,","year":"2012","journal-title":"Int. J. Parallel, Emerg. Distrib. Syst."},{"key":"2022092320284029900_B33","doi-asserted-by":"crossref","first-page":"721","DOI":"10.14778\/2732939.2732945","article-title":"Path problems in temporal graphs","volume":"7","author":"Wu,","year":"2014","journal-title":"Proc. VLDB Endow."},{"key":"2022092320284029900_B34","first-page":"983","article-title":"To sample or to smash? Estimating reachability in large time-varying graphs","volume-title":"Proceedings of the 2014 SIAM International Conference on Data Mining","author":"Basu,","year":"2014"},{"key":"2022092320284029900_B35","first-page":"169","article-title":"The time has come: traversal and reachability in time-varying graphs","volume-title":"Biomedical Data Management and Graph Online Querying","author":"Wildemann,","year":"2015"},{"key":"2022092320284029900_B36","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/2348543.2348589","article-title":"Temporal reachability graphs","volume-title":"Proceedings of the 18th Annual International Conference on Mobile Computing and Networking","author":"Whitbeck,","year":"2012"},{"key":"2022092320284029900_B37","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-319-18173-8_6","article-title":"Efficiently testing $T$-interval connectivity in dynamic graphs","volume-title":"International Conference on Algorithms and Complexity","author":"Casteigts,","year":"2015"},{"key":"2022092320284029900_B38","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/ICDE.2016.7498236","article-title":"Reachability and time-based path queries in temporal graphs","volume-title":"2016 IEEE 32nd International Conference on Data Engineering (ICDE)","author":"Wu,","year":"2016"},{"key":"2022092320284029900_B39","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1007\/978-3-319-21837-3_64","article-title":"Network reachability analysis on temporally varying interaction networks","volume-title":"International Conference on Wireless Algorithms, Systems, and Applications","author":"Xu,","year":"2015"},{"key":"2022092320284029900_B40","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/2723372.2723717","article-title":"Minimum spanning trees in temporal graphs","volume-title":"Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data","author":"Huang,","year":"2015"},{"key":"2022092320284029900_B41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/15M1009615","article-title":"Community detection in temporal multilayer networks, with an application to correlation networks","volume":"14","author":"Bazzi,","year":"2016","journal-title":"Multiscale Model. Simul."},{"key":"2022092320284029900_B42","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.physa.2015.02.069","article-title":"A fast algorithm for community detection in temporal network","volume":"429","author":"He,","year":"2015","journal-title":"Physica A"},{"key":"2022092320284029900_B43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3172867","article-title":"Community discovery in dynamic networks: a survey","volume":"51","author":"Rossetti,","year":"2018","journal-title":"ACM Comput. Surv."},{"key":"2022092320284029900_B44","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.tcs.2019.03.031","article-title":"Temporal graph classes: a view through temporal separators","volume":"806","author":"Fluschnik,","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"2022092320284029900_B45","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.jcss.2019.07.006","article-title":"The complexity of finding small separators in temporal graphs","volume":"107","author":"Zschoche,","year":"2020","journal-title":"J. Comput. Syst. Sci."},{"key":"2022092320284029900_B46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.006","article-title":"Traveling salesman problems in temporal graphs","volume":"634","author":"Michail,","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2022092320284029900_B47","author":"Khodaverdian,","year":"2016","journal-title":"Steiner network problems on temporal graphs"},{"key":"2022092320284029900_B48","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.ipl.2018.01.006","article-title":"Enumerating maximal cliques in link streams with durations","volume":"133","author":"Viard,","year":"2018","journal-title":"Inform. Process. Lett."},{"key":"2022092320284029900_B49","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/978-3-030-86475-0_33","article-title":"A Two-Phase Approach for Enumeration of Maximal $(\\Delta, \\gamma)$-Cliques of a Temporal Network","volume-title":"International Conference on Database and Expert Systems Applications","author":"Banerjee,","year":"2021"},{"key":"2022092320284029900_B50","first-page":"519","article-title":"Enumerating isolated cliques in temporal networks","volume-title":"International Conference on Complex Networks and Their Applications","author":"Molter,","year":"2019"},{"key":"2022092320284029900_B51","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3325859","article-title":"Listing all maximal k-plexes in temporal graphs","volume":"24","author":"Bentert,","year":"2019","journal-title":"J. Exp. Algorithmics"},{"key":"2022092320284029900_B52","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1109\/BigData.2015.7363809","article-title":"Core decomposition in large temporal graphs","volume-title":"2015 IEEE International Conference on Big Data (Big Data)","author":"Wu,","year":"2015"},{"key":"2022092320284029900_B53","first-page":"1","article-title":"Span-core decomposition for temporal networks: algorithms and applications","volume-title":"ACM Transactions on Knowledge Discovery from Data","author":"Galimberti,","year":"2019"},{"key":"2022092320284029900_B54","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","article-title":"Temporal networks","volume":"519","author":"Holme,","year":"2012","journal-title":"Phys. Rep."},{"key":"2022092320284029900_B55","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.jtbi.2010.11.033","article-title":"What\u2019s in a crowd? Analysis of face-to-face behavioral networks","volume":"271","author":"Isella,","year":"2011","journal-title":"J. Theor. Biol."},{"key":"2022092320284029900_B56","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/1081870.1081893","article-title":"Graphs over time: densification laws, shrinking diameters and possible explanations","volume-title":"Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining","author":"Leskovec,","year":"2005"},{"key":"2022092320284029900_B57","first-page":"485","article-title":"Updating maximal $(\\Delta, \\gamma)$-cliques efficiently","volume-title":"International Conference on Web Information Systems and Engineering","author":"Banerjee,","year":"2021"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/5\/cnac027\/45986023\/cnac027.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/5\/cnac027\/45986023\/cnac027.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T04:04:18Z","timestamp":1700971458000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnac027\/6712694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,23]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,8,23]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnac027","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,10,1]]},"published":{"date-parts":[[2022,8,23]]},"article-number":"cnac027"}}