{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:08Z","timestamp":1773481928868,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"\n Decomposing a graph into a hierarchical structure via\n k<\/jats:italic>\n -core analysis is a standard operation in any modern graph-mining toolkit.\n k<\/jats:italic>\n -core decomposition is a simple and efficient method that allows to analyze a graph beyond its mere degree distribution. More specifically, it is used to identify areas in the graph of increasing centrality and connectedness, and it allows to reveal the structural organization of the graph.\n <\/jats:p>\n \n Despite the fact that\n k<\/jats:italic>\n -core analysis relies on vertex degrees,\n k<\/jats:italic>\n -cores do not satisfy a certain, rather natural, density property. Simply put, the most central\n k<\/jats:italic>\n -core is not necessarily the densest subgraph. This inconsistency between\n k<\/jats:italic>\n -cores and graph density provides the basis of our study.\n <\/jats:p>\n \n We start by defining what it means for a subgraph to be\n locally dense<\/jats:italic>\n , and we show that our definition entails a nested chain decomposition of the graph, similar to the one given by\n k<\/jats:italic>\n -cores, but in this case the components are arranged in order of increasing density. We show that such a\n locally dense decomposition<\/jats:italic>\n for a graph\n G<\/jats:italic>\n =(\n V<\/jats:italic>\n ,\n E<\/jats:italic>\n ) can be computed in polynomial time. The running time of the exact decomposition algorithm is\n O<\/jats:italic>\n (|\n V<\/jats:italic>\n |\n 2<\/jats:sup>\n |\n E<\/jats:italic>\n |) but is significantly faster in practice. In addition, we develop a linear-time algorithm that provides a factor-2 approximation to the optimal locally dense decomposition. Furthermore, we show that the\n k<\/jats:italic>\n -core decomposition is also a factor-2 approximation, however, as demonstrated by our experimental evaluation, in practice\n k<\/jats:italic>\n -cores have different structure than locally dense subgraphs, and as predicted by the theory,\n k<\/jats:italic>\n -cores are not always well-aligned with graph density.\n <\/jats:p>","DOI":"10.1145\/3344210","type":"journal-article","created":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T12:57:52Z","timestamp":1569416272000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Density-Friendly Graph Decomposition"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2087-5360","authenticated-orcid":false,"given":"Nikolaj","family":"Tatti","sequence":"first","affiliation":[{"name":"Helsinki Institute for Information Technology, University of Helsinki, and Aalto University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"LATIN 2002: Theoretical Informatics","author":"Abello James","unstructured":"James Abello , Mauricio G. C. Resende , and Sandra Sudarsky . 2002. Massive quasi-clique detection . In LATIN 2002: Theoretical Informatics . Springer , 598--612. James Abello, Mauricio G. C. Resende, and Sandra Sudarsky. 2002. Massive quasi-clique detection. In LATIN 2002: Theoretical Informatics. Springer, 598--612."},{"key":"e_1_2_1_2_1","volume-title":"Analysis of Ordinal Categorical Data","author":"Agresti Alan","unstructured":"Alan Agresti . 2010. Analysis of Ordinal Categorical Data ( 2 nd ed.). John Wiley 8 Sons. Alan Agresti. 2010. Analysis of Ordinal Categorical Data (2nd ed.). John Wiley 8 Sons.","edition":"2"},{"key":"e_1_2_1_3_1","unstructured":"J. Ignacio Alvarez-Hamelin Luca Dall\u2019Asta Alain Barrat and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. Advances in Neural Information Processing Systems. 41--50. J. Ignacio Alvarez-Hamelin Luca Dall\u2019Asta Alain Barrat and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. Advances in Neural Information Processing Systems. 41--50."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61422-2_127"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728423"},{"key":"e_1_2_1_6_1","volume-title":"An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4, 1","author":"Bader Gary","year":"2003","unstructured":"Gary Bader and Christopher Hogue . 2003. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4, 1 ( 2003 ). Gary Bader and Christopher Hogue. 2003. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4, 1 (2003)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/1999405"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"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.1016\/j.is.2012.01.005"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_14_1","volume-title":"Newman","author":"Clauset Aaron","year":"2008","unstructured":"Aaron Clauset , Cristopher Moore , and Mark E. J . Newman . 2008 . Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191 (2008), 98--101. Aaron Clauset, Cristopher Moore, and Mark E. J. Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191 (2008), 98--101."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.492"},{"key":"e_1_2_1_17_1","volume-title":"Finding a Maximum Density Subgraph","author":"Goldberg Andrew V.","unstructured":"Andrew V. Goldberg . 1984. Finding a Maximum Density Subgraph . University of California Berkeley Technical report. Andrew V. Goldberg. 1984. Finding a Maximum Density Subgraph. University of California Berkeley Technical report."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132873"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.0060159"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS\u201996)","author":"H\u00e5stad Johan","year":"1996","unstructured":"Johan H\u00e5stad . 1996 . Clique is hard to approximate within n1 − \u03b5 . In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS\u201996) . 627--636. Johan H\u00e5stad. 1996. Clique is hard to approximate within n1 − \u03b5. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS\u201996). 627--636."},{"key":"e_1_2_1_21_1","first-page":"597","article-title":"On finding dense subgraphs. In Proceedings of the 36th International Colloquium on Automata","volume":"5555","author":"Khuller Samir","year":"2009","unstructured":"Samir Khuller and Barna Saha . 2009 . On finding dense subgraphs. In Proceedings of the 36th International Colloquium on Automata , Languages and Programming , Vol. 5555. 597 -- 608 . Samir Khuller and Barna Saha. 2009. On finding dense subgraphs. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, Vol. 5555. 597--608.","journal-title":"Languages and Programming"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1746"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00139635"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.09.007"},{"key":"e_1_2_1_29_1","unstructured":"Nikolaj Tatti and Aristides Gionis. 2013. Discovering nested communities. In Machine Learning and Knowledge Discovery in Databases\u2014European Conference (ECML PKDD\u201913). 32--47. Nikolaj Tatti and Aristides Gionis. 2013. Discovering nested communities. In Machine Learning and Knowledge Discovery in Databases\u2014European Conference (ECML PKDD\u201913). 32--47."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201913)","author":"Tsourakakis Charalampos E.","unstructured":"Charalampos E. Tsourakakis , Francesco Bonchi , Aristides Gionis , Francesco Gullo , and Maria A. Tsiarli . 2013. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees . In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201913) . 104--112. Charalampos E. Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria A. Tsiarli. 2013. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201913). 104--112."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1116502109"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118242.3118587"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344210","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:24Z","timestamp":1750203864000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,24]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3344210"],"URL":"https:\/\/doi.org\/10.1145\/3344210","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,24]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}