{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T22:30:05Z","timestamp":1775341805408,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T00:00:00Z","timestamp":1567641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/13,NI 369\/16,NI 369\/17"],"award-info":[{"award-number":["NI 369\/13,NI 369\/16,NI 369\/17"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (which represent people in the case of social networks) are represented by timestamped edges. One of the most fundamental problems in (social) network analysis is community detection, and one of the most basic primitives to model a community is a clique. Addressing the problem of finding communities in temporal networks, Viard et al. [TCS 2016] introduced \u0394-cliques as a natural temporal version of cliques. Himmel et al. [SNAM 2017] showed how to adapt the well-known B\n            <jats:sc>ron<\/jats:sc>\n            K\n            <jats:sc>erbosch<\/jats:sc>\n            algorithm to enumerate \u0394-cliques. We continue this work and improve and extend the algorithm of Himmel et al. to enumerate temporal\n            <jats:italic>k<\/jats:italic>\n            -plexes (notably, cliques are the special case\n            <jats:italic>k<\/jats:italic>\n            =1).\n          <\/jats:p>\n          <jats:p>\n            We define a \u0394-\n            <jats:italic>k<\/jats:italic>\n            -plex as a set of vertices and a time interval, where during this time interval each vertex has in each consecutive \u0394 + 1 timesteps at least one edge to all but at most\n            <jats:italic>k<\/jats:italic>\n            \u22121 vertices in the chosen set of vertices. We develop a recursive algorithm for enumerating all maximal \u0394-\n            <jats:italic>k<\/jats:italic>\n            -plexes and perform experiments on real-world social networks that demonstrate the practical feasibility of our approach. In particular, for the special case of \u0394-1-plexes (i.e., \u0394-cliques), we observe that our algorithm is on average significantly faster than the previous algorithms by Himmel et al. [SNAM 2017] and Viard et al. [IPL 2018] for enumerating \u0394-cliques.\n          <\/jats:p>","DOI":"10.1145\/3325859","type":"journal-article","created":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T12:14:48Z","timestamp":1567685688000},"page":"1-27","source":"Crossref","is-referenced-by-count":23,"title":["Listing All Maximal\n            <i>k<\/i>\n            -Plexes in Temporal Graphs"],"prefix":"10.1145","volume":"24","author":[{"given":"Matthias","family":"Bentert","sequence":"first","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anne-Sophie","family":"Himmel","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Morik","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ren\u00e9","family":"Saitenmacher","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9757-x"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Akrida Eleni C.","year":"2018","unstructured":"Eleni C. Akrida , George B. Mertzios , Paul G. Spirakis , and Viktor Zamaraev . 2018 . Temporal vertex covers and sliding time windows . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 148:1--148:14. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. 2018. Temporal vertex covers and sliding time windows. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 148:1--148:14."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2018.8508847"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.05.026"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918)","author":"Chen Jiehua","year":"2018","unstructured":"Jiehua Chen , Hendrik Molter , Manuel Sorge , and Ondrej Such\u00fd . 2018 . Cluster editing in multi-layer and temporal graphs . In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918) (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 24:1--24:13. Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Such\u00fd. 2018. Cluster editing in multi-layer and temporal graphs. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918) (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 24:1--24:13."},{"key":"e_1_2_1_11_1","first-page":"76","article-title":"Clustering algorithms for ad hoc wireless networks","volume":"28","author":"Chen Yuanzhu Peter","year":"2004","unstructured":"Yuanzhu Peter Chen , Arthur L. Liestman , and Jiangchuan Liu . 2004 . Clustering algorithms for ad hoc wireless networks . Ad Hoc and Sensor Networks 28 (2004), 76 -- 91 . Yuanzhu Peter Chen, Arthur L. Liestman, and Jiangchuan Liu. 2004. Clustering algorithms for ad hoc wireless networks. Ad Hoc and Sensor Networks 28 (2004), 76--91.","journal-title":"Ad Hoc and Sensor Networks"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220093"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098031"},{"key":"e_1_2_1_14_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2017. Graph Theory ( 5 th ed.). Springer . Reinhard Diestel. 2017. Graph Theory (5th ed.). Springer.","edition":"5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2543629"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_36"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918)","volume":"117","author":"Erlebach Thomas","unstructured":"Thomas Erlebach and Jakob T. Spooner . 2018. Faster exploration of degree-bounded temporal graphs . In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918) (LIPIcs), Vol. 117 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 36:1--36:13. Thomas Erlebach and Jakob T. Spooner. 2018. Faster exploration of degree-bounded temporal graphs. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918) (LIPIcs), Vol. 117. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 36:1--36:13."},{"key":"e_1_2_1_18_1","volume-title":"Temporal graph classes: A view through temporal separators. Theoretical Computer Science","author":"Fluschnik Till","year":"2019","unstructured":"Till Fluschnik , Hendrik Molter , Rolf Niedermeier , Malte Renken , and Philipp Zschoche . 2019. Temporal graph classes: A view through temporal separators. Theoretical Computer Science ( 2019 ). Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. 2019. Temporal graph classes: A view through temporal separators. Theoretical Computer Science (2019)."},{"key":"e_1_2_1_19_1","volume-title":"Contact patterns among high school students. PlOS On 9, 9","author":"Fournet Julie","year":"2014","unstructured":"Julie Fournet and Alain Barrat . 2014. Contact patterns among high school students. PlOS On 9, 9 ( 2014 ). Julie Fournet and Alain Barrat. 2014. Contact patterns among high school students. PlOS On 9, 9 (2014)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12879-014-0695-9"},{"key":"e_1_2_1_21_1","volume-title":"Email Network of KIT Informatics. Retrieved on","author":"Goerke Robert","year":"2018","unstructured":"Robert Goerke . 2011. Email Network of KIT Informatics. Retrieved on January 2018 from http:\/\/i11www.iti.uni-karlsruhe.de\/en\/projects\/spp1307\/emaildata. Robert Goerke. 2011. Email Network of KIT Informatics. Retrieved on January 2018 from http:\/\/i11www.iti.uni-karlsruhe.de\/en\/projects\/spp1307\/emaildata."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767285"},{"key":"e_1_2_1_23_1","volume-title":"Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining 7, 1","author":"Himmel Anne-Sophie","year":"2017","unstructured":"Anne-Sophie Himmel , Hendrik Molter , Rolf Niedermeier , and Manuel Sorge . 2017. Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining 7, 1 ( 2017 ), 35:1--35:16. Anne-Sophie Himmel, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge. 2017. Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining 7, 1 (2017), 35:1--35:16."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2012.03.001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2010.11.033"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597044"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1829"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.04.021"},{"key":"e_1_2_1_30_1","volume-title":"DNC emails network dataset. Retrieved on","author":"KONECT.","year":"2018","unstructured":"KONECT. 2017. DNC emails network dataset. Retrieved on January 2018 from http:\/\/konect.uni-koblenz.de\/networks\/dnc-temporalGraph. KONECT. 2017. DNC emails network dataset. Retrieved on January 2018 from http:\/\/konect.uni-koblenz.de\/networks\/dnc-temporalGraph."},{"key":"e_1_2_1_31_1","volume-title":"Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining 8, 1","author":"Latapy Matthieu","year":"2018","unstructured":"Matthieu Latapy , Tiphaine Viard , and Cl\u00e9mence Magnien . 2018. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining 8, 1 ( 2018 ), 61:1--61:29. Matthieu Latapy, Tiphaine Viard, and Cl\u00e9mence Magnien. 2018. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining 8, 1 (2018), 61:1--61:29."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_33_1","first-page":"1","article-title":"Playing the role of weak clique property in link prediction: A friend recommendation model","volume":"6","author":"Ma Chuang","year":"2016","unstructured":"Chuang Ma , Tao Zhou , and Hai-Feng Zhang . 2016 . Playing the role of weak clique property in link prediction: A friend recommendation model . Scientific Reports 6 (2016), 1 -- 11 . Chuang Ma, Tao Zhou, and Hai-Feng Zhang. 2016. Playing the role of weak clique property in link prediction: A friend recommendation model. Scientific Reports 6 (2016), 1--11.","journal-title":"Scientific Reports"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9338-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0478-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33017667"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2016.1177801"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9391-5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2009.02.002"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_43_1","volume-title":"Corinne R\u00e9gis, Bruno Lina, et al.","author":"Stehl\u00e9 Juliette","year":"2011","unstructured":"Juliette Stehl\u00e9 , Nicolas Voirin , Alain Barrat , Ciro Cattuto , Lorenzo Isella , Jean-Fran\u00e7ois Pinton , Marco Quaggiotto , Wouter Van den Broeck , Corinne R\u00e9gis, Bruno Lina, et al. 2011 . High-resolution measurements of face-to-face contact patterns in a primary school. PlOS One 6, 8 (2011). Juliette Stehl\u00e9, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-Fran\u00e7ois Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne R\u00e9gis, Bruno Lina, et al. 2011. High-resolution measurements of face-to-face contact patterns in a primary school. PlOS One 6, 8 (2011)."},{"key":"e_1_2_1_44_1","volume-title":"Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PlOS One 8, 9","author":"Vanhems Philippe","year":"2013","unstructured":"Philippe Vanhems , Alain Barrat , Ciro Cattuto , Jean-Fran\u00e7ois Pinton , Nagham Khanafer , Corinne R\u00e9gis , Byeul-a Kim, Brigitte Comte , and Nicolas Voirin . 2013. Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PlOS One 8, 9 ( 2013 ). Philippe Vanhems, Alain Barrat, Ciro Cattuto, Jean-Fran\u00e7ois Pinton, Nagham Khanafer, Corinne R\u00e9gis, Byeul-a Kim, Brigitte Comte, and Nicolas Voirin. 2013. Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PlOS One 8, 9 (2013)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.030"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.01.006"},{"key":"e_1_2_1_47_1","volume-title":"Williams and Mirco Musolesi","author":"Matthew","year":"2016","unstructured":"Matthew J. Williams and Mirco Musolesi . 2016 . Matthew J. Williams and Mirco Musolesi. 2016."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsos.160196"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1780582.1780632"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917)","author":"Xiao Mingyu","year":"2017","unstructured":"Mingyu Xiao , Weibo Lin , Yuanshun Dai , and Yifeng Zeng . 2017 . A fast algorithm to compute maximum k-plexes in social network analysis . In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917) . AAAI Press, 919--925. Mingyu Xiao, Weibo Lin, Yuanshun Dai, and Yifeng Zeng. 2017. A fast algorithm to compute maximum k-plexes in social network analysis. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917). AAAI Press, 919--925."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918)","volume":"117","author":"Zschoche Philipp","year":"2018","unstructured":"Philipp Zschoche , Till Fluschnik , Hendrik Molter , and Rolf Niedermeier . 2018 . The complexity of finding small separators in temporal graphs . In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918) (LIPIcs), Vol. 117 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 45:1--45:17. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. 2018. The complexity of finding small separators in temporal graphs. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918) (LIPIcs), Vol. 117. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 45:1--45:17."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325859","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3325859","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:08Z","timestamp":1750204388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325859"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,5]]},"references-count":48,"alternative-id":["10.1145\/3325859"],"URL":"https:\/\/doi.org\/10.1145\/3325859","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,5]]}}}