{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:39Z","timestamp":1779174819041,"version":"3.51.4"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"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. Algorithms"],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:p>\n            We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay [1999]. The algorithm takes as input a bipartite graph\n            <jats:italic>G<\/jats:italic>\n            , a starting vertex\n            <jats:italic>v<\/jats:italic>\n            , and a parameter\n            <jats:italic>k<\/jats:italic>\n            , and outputs an induced subgraph of\n            <jats:italic>G<\/jats:italic>\n            . It is local in the sense that it does not examine the entire input graph; instead, it adaptively explores a region of the graph near the starting vertex. The running time of the algorithm is bounded by\n            <jats:italic>O<\/jats:italic>\n            (\u0394\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), which depends on the maximum degree \u0394, but is otherwise independent of the graph. We prove the following approximation guarantee: for any subgraph\n            <jats:italic>S<\/jats:italic>\n            with\n            <jats:italic>k\u2032<\/jats:italic>\n            vertices and density \u03b8, there exists a set\n            <jats:italic>S<\/jats:italic>\n            \u2032 \u2286\n            <jats:italic>S<\/jats:italic>\n            for which the algorithm outputs a subgraph with density \u03a9(\u03b8\/log \u0394) whenever\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>S<\/jats:italic>\n            \u2032 and\n            <jats:italic>k<\/jats:italic>\n            \u2265\n            <jats:italic>k<\/jats:italic>\n            \u2032. We prove that\n            <jats:italic>S<\/jats:italic>\n            \u2032 contains at least half of the edges in\n            <jats:italic>S<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/1824777.1824780","type":"journal-article","created":{"date-parts":[[2010,9,2]],"date-time":"2010-09-02T13:14:24Z","timestamp":1283433264000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["A local algorithm for finding dense subgraphs"],"prefix":"10.1145","volume":"6","author":[{"given":"Reid","family":"Andersen","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08)","author":"Andersen R.","year":"2008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_4_1","first-page":"1501","article-title":"Spectral densest subgraph and independence number of a graph","volume":"13","author":"Andersen R.","year":"2007","journal-title":"J. Univer. Comput. Sci."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.19"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_2_1_8_1","unstructured":"Feige U. and Seltser M. 1997. On the densest k-subgraph problem. Tech. rep. CS97-16. 1 .   Feige U. and Seltser M. 1997. On the densest k-subgraph problem. Tech. rep. CS97-16. 1 ."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05)","author":"Gibson D."},{"key":"e_1_2_1_11_1","unstructured":"Goldberg A. 1984. Finding a maximum density subgraph. Tech. rep. UCB CSD 84\/71 University of California Berkeley.   Goldberg A. 1984. Finding a maximum density subgraph. Tech. rep. UCB CSD 84\/71 University of California Berkeley."},{"key":"e_1_2_1_12_1","unstructured":"Kannan R. and Vinay V. 1999. Analyzing the structure of large graphs. Manuscript. http:\/\/research.microsoft.com\/en-us\/um\/people\/kannan\/Papers\/webgraph.pdf.  Kannan R. and Vinay V. 1999. Analyzing the structure of large graphs. Manuscript. http:\/\/research.microsoft.com\/en-us\/um\/people\/kannan\/Papers\/webgraph.pdf."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 8th World Wide Web Conference (WWW'99)","author":"Kumar R."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_18_1","unstructured":"Spielman D. A. and Teng S.-H. 2008. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR abs\/0809.3232.  Spielman D. A. and Teng S.-H. 2008. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR abs\/0809.3232."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824780","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1824777.1824780","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:53Z","timestamp":1750246793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824780"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1145\/1824777.1824780"],"URL":"https:\/\/doi.org\/10.1145\/1824777.1824780","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}