{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:17:09Z","timestamp":1773886629870,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>Recent years have witnessed an unprecedented proliferation of social media. People around the globe author, every day, millions of blog posts, micro-blog posts, social network status updates, etc. This rich stream of information can be used to identify, on an ongoing basis, emerging stories, and events that capture popular attention. Stories can be identified via groups of tightly-coupled real-world entities, namely the people, locations, products, etc., that are involved in the story. The sheer scale, and rapid evolution of the data involved necessitate highly efficient techniques for identifying important stories at every point of time.<\/jats:p>\n          <jats:p>The main challenge in real-time story identification is the maintenance of dense subgraphs (corresponding to groups of tightly-coupled entities) under streaming edge weight updates (resulting from a stream of user-generated content). This is the first work to study the efficient maintenance of dense subgraphs under such streaming edge weight updates. For a wide range of definitions of density, we derive theoretical results regarding the magnitude of change that a single edge weight update can cause. Based on these, we propose a novel algorithm, DynDens, which outperforms adaptations of existing techniques to this setting, and yields meaningful results. Our approach is validated by a thorough experimental evaluation on large-scale real and synthetic datasets.<\/jats:p>","DOI":"10.14778\/2168651.2168658","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"574-585","source":"Crossref","is-referenced-by-count":98,"title":["Dense subgraph maintenance under streaming edge weight updates for real-time story identification"],"prefix":"10.14778","volume":"5","author":[{"given":"Albert","family":"Angel","sequence":"first","affiliation":[{"name":"University of Toronto"}]},{"given":"Nikos","family":"Sarkas","sequence":"additional","affiliation":[{"name":"University of Toronto"}]},{"given":"Nick","family":"Koudas","sequence":"additional","affiliation":[{"name":"University of Toronto"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs-Research"}]}],"member":"320","published-online":{"date-parts":[[2012,2]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"598","volume-title":"LATIN","author":"Abello J.","year":"2002","unstructured":"J. Abello , M. G. C. Resende , and S. Sudarsky . Massive quasi-clique detection . In LATIN , pages 598 -- 612 , 2002 . J. Abello, M. G. C. Resende, and S. Sudarsky. Massive quasi-clique detection. In LATIN, pages 598--612, 2002."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989405"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559977"},{"key":"e_1_2_1_4_1","volume-title":"Dense subgraph maintenance under streaming edge weight updates for real-time story identification. Tr","author":"Angel A.","year":"2011","unstructured":"A. Angel , N. Koudas , N. Sarkas , and D. Srivastava . Dense subgraph maintenance under streaming edge weight updates for real-time story identification. Tr , 2011 . Available at http:\/\/tinyurl.com\/dyndens. A. Angel, N. Koudas, N. Sarkas, and D. Srivastava. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. Tr, 2011. Available at http:\/\/tinyurl.com\/dyndens."},{"key":"e_1_2_1_5_1","first-page":"806","volume-title":"VLDB","author":"Bansal N.","year":"2007","unstructured":"N. Bansal , F. Chiang , N. Koudas , and F. W. Tompa . Seeking stable clusters in the blogosphere . In VLDB , pages 806 -- 817 , 2007 . N. Bansal, F. Chiang, N. Koudas, and F. W. Tompa. Seeking stable clusters in the blogosphere. In VLDB, pages 806--817, 2007."},{"key":"e_1_2_1_6_1","first-page":"623","volume-title":"SODA","author":"Bar-Yossef Z.","year":"2002","unstructured":"Z. Bar-Yossef , R. Kumar , and D. Sivakumar . Reductions in streaming algorithms, with an application to counting triangles in graphs . In SODA , pages 623 -- 632 , 2002 . Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA, pages 623--632, 2002."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150467"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258657"},{"issue":"4","key":"e_1_2_1_9_1","first-page":"950","article-title":"Computational methods for dynamic graphs","volume":"12","author":"Cortes C.","year":"2003","unstructured":"C. Cortes , D. Pregibon , and C. Volinsky . Computational methods for dynamic graphs . JCGS , 12 ( 4 ): 950 -- 970 , 2003 . C. Cortes, D. Pregibon, and C. Volinsky. Computational methods for dynamic graphs. JCGS, 12(4):950--970, 2003.","journal-title":"JCGS"},{"key":"e_1_2_1_10_1","volume-title":"Algorithms and Theory of Computation Handbook","author":"Eppstein D.","year":"1999","unstructured":"D. Eppstein , Z. Galil , and G. F. Italiano . Dynamic graph algorithms . In Algorithms and Theory of Computation Handbook , chapter 8. 1999 . D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algorithms. In Algorithms and Theory of Computation Handbook, chapter 8. 1999."},{"key":"e_1_2_1_11_1","first-page":"323","volume-title":"VLDB","author":"Ester M.","year":"1998","unstructured":"M. Ester , H.-P. Kriegel , J. Sander , M. Wimmer , and X. Xu . Incremental clustering for mining in a data warehousing environment . In VLDB , pages 323 -- 333 , 1998 . M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, and X. Xu. Incremental clustering for mining in a data warehousing environment. In VLDB, pages 323--333, 1998."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347121"},{"key":"e_1_2_1_13_1","first-page":"721","volume-title":"VLDB","author":"Gibson D.","year":"2005","unstructured":"D. Gibson , R. Kumar , and A. Tomkins . Discovering large dense subgraphs in massive graphs . In VLDB , pages 721 -- 732 , 2005 . D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense subgraphs in massive graphs. In VLDB, pages 721--732, 2005."},{"key":"e_1_2_1_14_1","volume-title":"Finding a maximum density subgraph. Technical report","author":"Goldberg A.","year":"1984","unstructured":"A. Goldberg . Finding a maximum density subgraph. Technical report , University of California at Berkeley , 1984 . A. Goldberg. Finding a maximum density subgraph. Technical report, University of California at Berkeley, 1984."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198387"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v50:1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1198\/106186006X139162"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04747-3_14"},{"issue":"1","key":"e_1_2_1_22_1","first-page":"1","article-title":"An incremental algorithm for the maximum flow problem","volume":"2","author":"Kumar S.","year":"2003","unstructured":"S. Kumar and P. Gupta . An incremental algorithm for the maximum flow problem . JMMA , 2 ( 1 ): 1 -- 16 , 2003 . S. Kumar and P. Gupta. An incremental algorithm for the maximum flow problem. JMMA, 2(1):1--16, 2003.","journal-title":"JMMA"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq514"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807306"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098364"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447820"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:COAP.0000008651.28952.b6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9238-3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376663"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516422"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2168651.2168658","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:18:26Z","timestamp":1672219106000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2168651.2168658"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.14778\/2168651.2168658"],"URL":"https:\/\/doi.org\/10.14778\/2168651.2168658","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,2]]}}}