{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:13Z","timestamp":1779174793598,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            The problem of finding locally dense components of a graph is an important primitive in data analysis, with wide-ranging applications from community mining to spam detection and the discovery of biological network modules. In this paper we present new algorithms for finding the densest subgraph in the streaming model. For any \u03b5 &gt; 0, our algorithms make\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sub>1+\u03b5<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            ) passes over the input and find a subgraph whose density is guaranteed to be within a factor 2(1 + \u03b5) of the optimum. Our algorithms are also easily parallelizable and we illustrate this by realizing them in the MapReduce model. In addition we perform extensive experimental evaluation on massive real-world graphs showing the performance and scalability of our algorithms in practice.\n          <\/jats:p>","DOI":"10.14778\/2140436.2140442","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"454-465","source":"Crossref","is-referenced-by-count":151,"title":["Densest subgraph in streaming and MapReduce"],"prefix":"10.14778","volume":"5","author":[{"given":"Bahman","family":"Bahmani","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Yahoo! Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"C. C. Aggarwal and H. Wang. Managing and Mining Graph Data. Springer Publishing Company Inc. 1st edition 2010.   C. C. Aggarwal and H. Wang. Managing and Mining Graph Data . Springer Publishing Company Inc. 1st edition 2010.","DOI":"10.1007\/978-1-4419-6045-0_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"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.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_5_1","first-page":"623","volume-title":"SODA","author":"Bar-Yossef Z.","year":"2002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80068-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341547"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214414"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772715"},{"key":"e_1_2_1_14_1","first-page":"937","volume-title":"SODA","author":"Cohen E.","year":"2002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_1_16_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242635"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824786"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"A. Gajewar and A. D. Sarma. Multi-skill collaborative teams based on densest subgraphs. CoRR abs\/1102.3340 2011.  A. Gajewar and A. D. Sarma. Multi-skill collaborative teams based on densest subgraphs. CoRR abs\/1102.3340 2011.","DOI":"10.1137\/1.9781611972825.15"},{"key":"e_1_2_1_21_1","first-page":"721","volume-title":"VLDB","author":"Gibson D.","year":"2005"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_24_1","unstructured":"R. Kannan and V. Vinay. Analyzing the structure of large graphs 1999. Manuscript.  R. Kannan and V. Vinay. Analyzing the structure of large graphs 1999. Manuscript."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_2_1_29_1","unstructured":"E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt Rinehart and Winston 1976.  E. Lawler. Combinatorial Optimization: Networks and Matroids . Holt Rinehart and Winston 1976."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_33_1","first-page":"460","volume-title":"PVLDB","author":"Morales G. D. F.","year":"2011"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767884"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2140436.2140442","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:40:39Z","timestamp":1672220439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2140436.2140442"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.14778\/2140436.2140442"],"URL":"https:\/\/doi.org\/10.14778\/2140436.2140442","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}