{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T19:47:54Z","timestamp":1781812074236,"version":"3.54.5"},"publisher-location":"New York, New York, USA","reference-count":53,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Google","award":["Google Faculty Award Mauro Sozio"],"award-info":[{"award-number":["Google Faculty Award Mauro Sozio"]}]},{"name":"French National Agency of Research","award":["FIELDS ANR-15-CE23- 0006"],"award-info":[{"award-number":["FIELDS ANR-15-CE23- 0006"]}]},{"name":"French National Agency of Research","award":["ANR-15-CE38-0001 (AlgoDiv)"],"award-info":[{"award-number":["ANR-15-CE38-0001 (AlgoDiv)"]}]},{"name":"European Commission","award":["H2020 FETPROACT 2016-2017 program under grant 732942 (ODYCCEUS)"],"award-info":[{"award-number":["H2020 FETPROACT 2016-2017 program under grant 732942 (ODYCCEUS)"]}]},{"name":"Ile-de-France Region","award":["program FUI21 under grant 16010629 (iTRAC)"],"award-info":[{"award-number":["program FUI21 under grant 16010629 (iTRAC)"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3178876.3186125","type":"proceedings-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T15:53:48Z","timestamp":1523634828000},"page":"589-598","source":"Crossref","is-referenced-by-count":102,"title":["Listing k-cliques in Sparse Real-World Graphs*"],"prefix":"10.1145","author":[{"given":"Maximilien","family":"Danisch","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oana","family":"Balalau","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mauro","family":"Sozio","sequence":"additional","affiliation":[{"name":"LTCI, T\u00e9l\u00e9com ParisTech University, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","reference":[{"key":"key-10.1145\/3178876.3186125-1","unstructured":"[n. d.]. http:\/\/research.nii.ac.jp\/~uno\/codes.htm. ([n. d.])."},{"key":"key-10.1145\/3178876.3186125-2","unstructured":"Nesreen K Ahmed, Jennifer Neville, Ryan A Rossi, and Nick Duffield. 2015. Efficient graphlet counting for large networks. In Data Mining (ICDM), 2015 IEEE International Conference on. IEEE, 1--10."},{"key":"key-10.1145\/3178876.3186125-3","doi-asserted-by":"crossref","unstructured":"Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. J. ACM 42, 4 (July 1995), 844--856. https:\/\/doi.org\/10.1145\/210332.210337","DOI":"10.1145\/210332.210337"},{"key":"key-10.1145\/3178876.3186125-4","doi-asserted-by":"crossref","unstructured":"Noga Alon, Raphael Yuster, and Uri Zwick. 1997. Finding and counting given length cycles. Algorithmica 17, 3 (1997), 209--223.","DOI":"10.1007\/BF02523189"},{"key":"key-10.1145\/3178876.3186125-5","doi-asserted-by":"crossref","unstructured":"Albert Angel, Nick Koudas, Nikos Sarkas, Divesh Srivastava, Michael Svendsen, and Srikanta Tirthapura. 2014. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. VLDB J. 23, 2 (2014), 175--199.","DOI":"10.1007\/s00778-013-0340-z"},{"key":"key-10.1145\/3178876.3186125-6","doi-asserted-by":"crossref","unstructured":"Oana Denisa Balalau, Francesco Bonchi, T.-H. Hubert Chan, Francesco Gullo, and Mauro Sozio. 2015. Finding Subgraphs with Maximum Total Density and Limited Overlap. In WSDM. 379--388.","DOI":"10.1145\/2684822.2685298"},{"key":"key-10.1145\/3178876.3186125-7","doi-asserted-by":"crossref","unstructured":"Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. 2008. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In SIGKDD. 16--24.","DOI":"10.1145\/1401890.1401898"},{"key":"key-10.1145\/3178876.3186125-8","unstructured":"Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163--166."},{"key":"key-10.1145\/3178876.3186125-9","unstructured":"Piotr Berman and Marek Karpinski. 1999. On some tighter inapproximability results. In International Colloquium on Automata, Languages, and Programming. Springer, 200--209."},{"key":"key-10.1145\/3178876.3186125-10","doi-asserted-by":"crossref","unstructured":"Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. 2014. Listing triangles. In Automata, Languages, and Programming. Springer, 223--234.","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"key-10.1145\/3178876.3186125-11","doi-asserted-by":"crossref","unstructured":"Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. 2017. Counting Graphlets: Space vs Time. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining (WSDM '17). ACM, New York, NY, USA, 557--566. https:\/\/doi.org\/10.1145\/3018661.3018732","DOI":"10.1145\/3018661.3018732"},{"key":"key-10.1145\/3178876.3186125-12","doi-asserted-by":"crossref","unstructured":"Coen Bron and Joep Kerbosch. 1973. Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16, 9 (1973), 575--577.","DOI":"10.1145\/362342.362367"},{"key":"key-10.1145\/3178876.3186125-13","doi-asserted-by":"crossref","unstructured":"Gregory Buehrer and Kumar Chellapilla. 2008. A scalable pattern mining approach to web graph compression with communities. In WSDM. 95--106.","DOI":"10.1145\/1341531.1341547"},{"key":"key-10.1145\/3178876.3186125-14","doi-asserted-by":"crossref","unstructured":"Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization. Springer, 84--95.","DOI":"10.1007\/3-540-44436-X_10"},{"key":"key-10.1145\/3178876.3186125-15","doi-asserted-by":"crossref","unstructured":"James Cheng, Linhong Zhu, Yiping Ke, and Shumo Chu. 2012. Fast algorithms for maximal clique enumeration with limited memory. In SIGKDD. ACM, 1240--1248.","DOI":"10.1145\/2339530.2339724"},{"key":"key-10.1145\/3178876.3186125-16","doi-asserted-by":"crossref","unstructured":"Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM J. Comput. 14, 1 (1985), 210--223.","DOI":"10.1137\/0214017"},{"key":"key-10.1145\/3178876.3186125-17","doi-asserted-by":"crossref","unstructured":"Shumo Chu and James Cheng. 2011. Triangle listing in massive networks and its applications. In SIGKDD. 672--680.","DOI":"10.1145\/2020408.2020513"},{"key":"key-10.1145\/3178876.3186125-18","unstructured":"Alessio Conte, Roberto De Virgilio, Antonio Maccioni, Maurizio Patrignani, and Riccardo Torlone. 2016. Finding All Maximal Cliques in Very Large Social Networks Categories. (2016)."},{"key":"key-10.1145\/3178876.3186125-19","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch, T-H Hubert Chan, and Mauro Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming. In Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 233--242.","DOI":"10.1145\/3038912.3052619"},{"key":"key-10.1145\/3178876.3186125-20","doi-asserted-by":"crossref","unstructured":"Yon Dourisboure, Filippo Geraci, and Marco Pellegrini. 2009. Extraction and classification of dense implicit communities in the Web graph. TWEB 3, 2 (2009).","DOI":"10.1145\/1513876.1513879"},{"key":"key-10.1145\/3178876.3186125-21","doi-asserted-by":"crossref","unstructured":"Xiaoxi Du, Ruoming Jin, Liang Ding, Victor E. Lee, and John H. Thornton Jr. 2009. Migration motif: a spatial - temporal pattern mining approach for financial markets. In SIGKDD. 1135--1144.","DOI":"10.1145\/1557019.1557142"},{"key":"key-10.1145\/3178876.3186125-22","doi-asserted-by":"crossref","unstructured":"Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. 2015. Efficient Densest Subgraph Computation in Evolving Graphs. In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18--22, 2015. 300--310.","DOI":"10.1145\/2736277.2741638"},{"key":"key-10.1145\/3178876.3186125-23","doi-asserted-by":"crossref","unstructured":"David Eppstein, Maarten Löffler, and Darren Strash. 2010. Listing all maximal cliques in sparse graphs in near-optimal time. Springer.","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"key-10.1145\/3178876.3186125-24","doi-asserted-by":"crossref","unstructured":"David Eppstein, Maarten Löffler, and Darren Strash. 2013. Listing all maximal cliques in large sparse real-world graphs. Journal of Experimental Algorithmics (JEA) 18 (2013), 3--1.","DOI":"10.1145\/2543629"},{"key":"key-10.1145\/3178876.3186125-25","doi-asserted-by":"crossref","unstructured":"Irene Finocchi, Marco Finocchi, and Emanuele G Fusco. 2015. Clique counting in mapreduce: Algorithms and experiments. Journal of Experimental Algorithmics (JEA) 20 (2015), 1--7.","DOI":"10.1145\/2794080"},{"key":"key-10.1145\/3178876.3186125-26","doi-asserted-by":"crossref","unstructured":"Eugene Fratkin, Brian T. Naughton, Douglas L. Brutlag, and Serafim Batzoglou. 2006. MotifCut: regulatory motifs finding with maximum density subgraphs. In Proceedings 14th International Conference on Intelligent Systems for Molecular Biology 2006, Fortaleza, Brazil, August 6--10, 2006. 156--157.","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"key-10.1145\/3178876.3186125-27","unstructured":"David Gibson, Ravi Kumar, and Andrew Tomkins. 2005. Discovering Large Dense Subgraphs in Massive Graphs. In PVLDB. 721--732."},{"key":"key-10.1145\/3178876.3186125-28","doi-asserted-by":"crossref","unstructured":"Enrico Gregori, Luciano Lenzini, and Simone Mainardi. 2013. Parallel k-clique community detection on large-scale networks. IEEE Transactions on Parallel and Distributed Systems 24, 8 (2013), 1651--1660.","DOI":"10.1109\/TPDS.2012.229"},{"key":"key-10.1145\/3178876.3186125-29","unstructured":"Mikhail Rudoy (https:\/\/cstheory.stackexchange.com\/users\/34401\/mikhail rudoy). [n. d.]. Is this vertex ordering optimization NP-Hard? Theoretical Computer Science Stack Exchange. ([n. d.])."},{"key":"key-10.1145\/3178876.3186125-30","doi-asserted-by":"crossref","unstructured":"Leonidas D. Iasemidis, Deng-Shan Shiau, Wanpracha Art Chaovalitwongse, J. Chris Sackellares, Panos M. Pardalos, Jose C. Principe, Paul R. Carney, Awadhesh Prasad, Balaji Veeramani, and Kostas Tsakalis. 2003. Adaptive epileptic seizure prediction system. IEEE Trans. Biomed. Engineering 50, 5 (2003), 616--627.","DOI":"10.1109\/TBME.2003.810689"},{"key":"key-10.1145\/3178876.3186125-31","doi-asserted-by":"crossref","unstructured":"Shweta Jain and C Seshadhri. 2017. A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem. In Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 441--449.","DOI":"10.1145\/3038912.3052636"},{"key":"key-10.1145\/3178876.3186125-32","doi-asserted-by":"crossref","unstructured":"Ruoming Jin, Yang Xiang, Ning Ruan, and David Fuhry. 2009. 3-HOP: a highcompression indexing scheme for reachability query. In SIGMOD. 813--826.","DOI":"10.1145\/1559845.1559930"},{"key":"key-10.1145\/3178876.3186125-33","unstructured":"Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hernán A Makse. 2010. Identification of influential spreaders in complex networks. Nature physics 6, 11 (2010), 888--893."},{"key":"key-10.1145\/3178876.3186125-34","unstructured":"Tamara G Kolda, Ali Pinar, Todd Plantenga, C Seshadhri, and Christine Task. 2014. Counting triangles in massive graphs with MapReduce. SIAM Journal on Scientific Computing 36, 5 (2014), S48--S77."},{"key":"key-10.1145\/3178876.3186125-35","doi-asserted-by":"crossref","unstructured":"Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In Proceedings of the 19th international conference on World wide web. ACM, 591--600.","DOI":"10.1145\/1772690.1772751"},{"key":"key-10.1145\/3178876.3186125-36","doi-asserted-by":"crossref","unstructured":"Matthieu Latapy. 2008. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical Computer Science 407, 1 (2008), 458--473.","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"key-10.1145\/3178876.3186125-37","doi-asserted-by":"crossref","unstructured":"Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu C. Aggarwal. 2010. A Survey of Algorithms for Dense Subgraph Discovery. In Managing and Mining Graph Data. 303--336.","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"key-10.1145\/3178876.3186125-38","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data. (June 2014)."},{"key":"key-10.1145\/3178876.3186125-39","doi-asserted-by":"crossref","unstructured":"Matthaios Letsios, Oana Denisa Balalau, Maximilien Danisch, Emmanuel Orsini, and Mauro Sozio. 2016. Finding heaviest k-subgraphs and events in social media. In Data Mining Workshops (ICDMW), 2016 IEEE 16th International Conference on. IEEE, 113--120.","DOI":"10.1109\/ICDMW.2016.0024"},{"key":"key-10.1145\/3178876.3186125-40","doi-asserted-by":"crossref","unstructured":"Kazuhisa Makino and Takeaki Uno. 2004. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT 2004. Springer, 260--272.","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"key-10.1145\/3178876.3186125-41","doi-asserted-by":"crossref","unstructured":"David W. Matula and Leland L. Beck. 1983. Smallest-last Ordering and Clustering and Graph Coloring Algorithms. J. ACM 30, 3 (July 1983), 417--427.","DOI":"10.1145\/2402.322385"},{"key":"key-10.1145\/3178876.3186125-42","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, and Shen Chen Xu. 2015. Scalable large near-clique detection in large-scale networks via sampling. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 815--824.","DOI":"10.1145\/2783258.2783385"},{"key":"key-10.1145\/3178876.3186125-43","doi-asserted-by":"crossref","unstructured":"Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 7043 (2005), 814--818.","DOI":"10.1038\/nature03607"},{"key":"key-10.1145\/3178876.3186125-44","doi-asserted-by":"crossref","unstructured":"Ali Pinar, C. Seshadhri, and Vaidyanathan Vishal. 2017. ESCAPE: Efficiently Counting All 5-Vertex Subgraphs. In Proceedings of the 26th International Conference on World Wide Web, WWW 2017, Perth, Australia, April 3--7, 2017. 1431--1440. https:\/\/doi.org\/10.1145\/3038912.3052597","DOI":"10.1145\/3038912.3052597"},{"key":"key-10.1145\/3178876.3186125-45","doi-asserted-by":"crossref","unstructured":"Angela P. Presson, Eric M. Sobel, Jeanette C. Papp, Charlyn J. Suarez, Toni Whistler, Mangalathu S. Rajeevan, Suzanne D. Vernon, and Steve Horvath. 2008. Integrated Weighted Gene Co-expression Network Analysis with an Application to Chronic Fatigue Syndrome. BMC Systems Biology 2 (2008), 95.","DOI":"10.1186\/1752-0509-2-95"},{"key":"key-10.1145\/3178876.3186125-46","doi-asserted-by":"crossref","unstructured":"Ahmet Erdem Sariyüce, C. Seshadhri, Ali Pinar, and Ümit V. Çatalyürek. 2015. Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions. In WWW. 927--937.","DOI":"10.1145\/2736277.2741640"},{"key":"key-10.1145\/3178876.3186125-47","unstructured":"Matthew C Schmidt, Nagiza F Samatova, Kevin Thomas, and Byung-Hoon Park. 2009. A scalable, parallel algorithm for maximal clique enumeration. J. Parallel and Distrib. Comput. 69, 4 (2009), 417--428."},{"key":"key-10.1145\/3178876.3186125-48","unstructured":"Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. 2016. CoreScope: Graph Mining Using k-Core Analysis Patterns, Anomalies and Algorithms. In Data Mining (ICDM), 2016 IEEE 16th International Conference on. IEEE, 469--478."},{"key":"key-10.1145\/3178876.3186125-49","unstructured":"UNO Takeaki. 2012. Implementation issues of clique enumeration algorithm. Special issue: Theoretical computer science and discrete mathematics, Progress in Informatics 9 (2012), 25--30."},{"key":"key-10.1145\/3178876.3186125-50","doi-asserted-by":"crossref","unstructured":"Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science 363, 1 (2006), 28--42.","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"key-10.1145\/3178876.3186125-51","doi-asserted-by":"crossref","unstructured":"Charalampos Tsourakakis. 2015. The k-clique densest subgraph problem. In Proceedings of the 24th international conference on world wide web. ACM, 1122-- 1132.","DOI":"10.1145\/2736277.2741098"},{"key":"key-10.1145\/3178876.3186125-52","doi-asserted-by":"crossref","unstructured":"Stanley Wasserman and Katherine Faust. 1994. Social network analysis: Methods and applications. Vol. 8. Cambridge university press.","DOI":"10.1017\/CBO9780511815478"},{"key":"key-10.1145\/3178876.3186125-53","doi-asserted-by":"crossref","unstructured":"Xiao Zhou and Takao Nishizeki. 1999. Edge-Coloring and f-Coloring for Various Classes of Graphs. MATCH Commun. Math. Comput. Chem 51 (1999), 111--118.","DOI":"10.7155\/jgaa.00012"}],"event":{"name":"the 2018 World Wide Web Conference","location":"Lyon, France","acronym":"WWW '18","number":"2018","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"start":{"date-parts":[[2018,4,23]]},"end":{"date-parts":[[2018,4,27]]}},"container-title":["Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178876.3186125","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3186125&ftid=1957456&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T17:25:46Z","timestamp":1751563546000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3178876.3186125"}},"subtitle":[],"proceedings-subject":"World Wide Web","short-title":[],"issued":{"date-parts":[[2018]]},"references-count":53,"URL":"https:\/\/doi.org\/10.1145\/3178876.3186125","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}