{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T04:35:38Z","timestamp":1784349338109,"version":"3.55.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,3]],"date-time":"2017-07-03T00:00:00Z","timestamp":1499040000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"wholly owned subsidiary of Lockheed Martin Corporation"},{"name":"Laboratory Directed Research and Development (LDRD) Program of Sandia National Laboratories"},{"name":"U.S. Department of Energy's National Nuclear Security Administration","award":["DE-AC04-94AL85000"],"award-info":[{"award-number":["DE-AC04-94AL85000"]}]},{"name":"DARPA GRAPHS program"},{"name":"Sandia Corporation"},{"name":"DOE Applied Mathematics Research Program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>Finding dense substructures in a graph is a fundamental graph mining operation, with applications in bioinformatics, social networks, and visualization to name a few. Yet most standard formulations of this problem (like clique, quasi-clique, densest at-least-<jats:italic>k<\/jats:italic>subgraph) are NP-hard. Furthermore, the goal is rarely to find the \u201ctrue optimum\u201d but to identify many (if not all) dense substructures, understand their distribution in the graph, and ideally determine relationships among them. Current dense subgraph finding algorithms usually optimize some objective and only find a few such subgraphs without providing any structural relations.<\/jats:p><jats:p>We define the<jats:italic>nucleus decomposition<\/jats:italic>of a graph, which represents the graph as a<jats:italic>forest of nuclei<\/jats:italic>. Each nucleus is a subgraph where smaller cliques are present in many larger cliques. The forest of nuclei is a hierarchy by containment, where the edge density increases as we proceed towards leaf nuclei. Sibling nuclei can have limited intersections, which enables discovering overlapping dense subgraphs. With the right parameters, the nucleus decomposition generalizes the classic notions of<jats:italic>k<\/jats:italic>-core and<jats:italic>k<\/jats:italic>-truss decompositions.<\/jats:p><jats:p>We present practical algorithms for nucleus decompositions and empirically evaluate their behavior in a variety of real graphs. The tree of nuclei consistently gives a global, hierarchical snapshot of dense substructures and outputs dense subgraphs of comparable quality with the state-of-the-art solutions that are dense and have non-trivial sizes. Our algorithms can process real-world graphs with tens of millions of edges in less than an hour. We demonstrate how proposed algorithms can be utilized on a citation network. Our analysis showed that dense units identified by our algorithms correspond to coherent articles on a specific area. Our experiments also show that we can identify dense structures that are lost within larger structures by other methods and find further finer grain structure within dense groups.<\/jats:p>","DOI":"10.1145\/3057742","type":"journal-article","created":{"date-parts":[[2017,7,5]],"date-time":"2017-07-05T12:19:53Z","timestamp":1499257193000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Nucleus Decompositions for Identifying Hierarchy of Dense Subgraphs"],"prefix":"10.1145","volume":"11","author":[{"given":"Ahmet Erdem","family":"Sariy\u00fcce","sequence":"first","affiliation":[{"name":"Sandia National Laboratories, East Ave. Livermore, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California Santa Cruz, Santa Cruz, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, East Ave. Livermore, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00dcmit V.","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta GA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,7,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the IEEE International Conference on Data Mining (ICDM). 1--10","author":"Adcock A. B."},{"key":"e_1_2_1_2_1","unstructured":"J. Ignacio Alvarez-Hamelin Alain Barrat and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems 18. 41--50. J. Ignacio Alvarez-Hamelin Alain Barrat and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems 18. 41--50."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1037\/0021-9010.88.6.989"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554819"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746592"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341547"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_16_1","unstructured":"UF Sparse Matrix Collection. University of Florida Sparse Matrix Collection. Retrieved March 2014 from http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/. UF Sparse Matrix Collection. University of Florida Sparse Matrix Collection. Retrieved March 2014 from http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"P. Colomer de Simon M. Serrano M. G. Beiro J. I. Alvarez-Hamelin and M. Boguna. 2013. Deciphering the global organization of clustering in real complex networks. Sci. Rep. 3 2517 (2013). P. Colomer de Simon M. Serrano M. G. Beiro J. I. Alvarez-Hamelin and M. Boguna. 2013. Deciphering the global organization of clustering in real complex networks. Sci. Rep. 3 2517 (2013).","DOI":"10.1038\/srep02517"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242635"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557142"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020444"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_2_1_23_1","unstructured":"D. R. Forsyth. 2010. Group Dynamics. Cengage Learning. D. R. Forsyth. 2010. Group Dynamics. Cengage Learning."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"A. P. Francisco and A. L. Oliveira. 2011. Fully generalized graph cores. In Complex Networks. Vol. 116. 22--34. A. P. Francisco and A. L. Oliveira. 2011. Fully generalized graph cores. In Complex Networks. Vol. 116. 22--34.","DOI":"10.1007\/978-3-642-25501-4_3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_2_1_27_1","volume-title":"Proc. of the 31st International Conference on Very Large Data Bases (VLDB\u201905)","author":"Gibson D."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536342"},{"key":"e_1_2_1_29_1","unstructured":"A. V. Goldberg. 1984. Finding a Maximum Density Subgraph. Technical Report. Berkeley CA USA. A. V. Goldberg. 1984. Finding a Maximum Density Subgraph. Technical Report. Berkeley CA USA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554840"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. 1996. Clique is hard to approximate within n(1 &minus; &epsi;). In Acta Mathematica. 627--636. J. H\u00e5stad. 1996. Clique is hard to approximate within n (1 &minus; &epsi;) . In Acta Mathematica. 627--636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1049"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBME.2003.810689"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_38_1","volume-title":"Proc. of the Eighth International Conference on World Wide Web (WWW\u201999)","author":"Kumar R."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"V. E. Lee N. Ruan R. Jin and C. Aggarwal. 2010. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data. Vol. 40. V. E. Lee N. Ruan R. Jin and C. Aggarwal. 2010. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data. Vol. 40.","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00139635"},{"key":"e_1_2_1_44_1","unstructured":"R. A. Rossi D. F. Gleich A. H. Gebremedhin and Md. M. A. Patwary. 2013. A fast parallel maximum clique algorithm for large sparse graphs and temporal strong components. CoRR abs\/1302.6256 (2013). R. A. Rossi D. F. Gleich A. H. Gebremedhin and Md. M. A. Patwary. 2013. A fast parallel maximum clique algorithm for large sparse graphs and temporal strong components. CoRR abs\/1302.6256 (2013)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2006.76"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772778"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"S. B. Seidman and B. Foster. 1978. A graph-theoretic generalization of the clique concept. J. Math. Sociol. (1978). S. B. Seidman and B. Foster. 1978. A graph-theoretic generalization of the clique concept. J. Math. Sociol. (1978).","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11224"},{"key":"e_1_2_1_53_1","unstructured":"SNAP. retrieved March 2014. Stanford Network Analysis Package. Retrieved March 2014 http:\/\/snap.stanford.edu\/snap. SNAP. retrieved March 2014. Stanford Network Analysis Package. Retrieved March 2014 http:\/\/snap.stanford.edu\/snap."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"S. Wasserman and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press. S. Wasserman and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","unstructured":"B. Zhang and S. Horvath. 2005. A general framework for weighted gene co-expression network analysis. Stat. Appl. Genet. Molec. Biol. 4 1 (2005) Article 17+. B. Zhang and S. Horvath. 2005. A general framework for weighted gene co-expression network analysis. Stat. Appl. Genet. Molec. Biol. 4 1 (2005) Article 17+.","DOI":"10.2202\/1544-6115.1128"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.35"},{"key":"e_1_2_1_64_1","volume-title":"Proc. VLDB Endow. 85--96","author":"Zhao F.","year":"2013"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3057742","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3057742","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:06:10Z","timestamp":1750493170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3057742"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,3]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3057742"],"URL":"https:\/\/doi.org\/10.1145\/3057742","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,3]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}