{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T05:08:25Z","timestamp":1778562505796,"version":"3.51.4"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>\n            Due to their\n            <jats:italic>real time<\/jats:italic>\n            nature, microblog streams are a rich source of dynamic information, for example, about\n            <jats:italic>emerging events<\/jats:italic>\n            . Existing techniques for discovering such events from a microblog stream in real time (such as Twitter trending topics), have several lacunae when used for discovering emerging events; extant graph based event detection techniques are not practical in microblog settings due to their complexity; and conventional techniques, which have been developed for blogs, web-pages, etc., involving the use of keyword search, are only useful for finding information about\n            <jats:italic>known<\/jats:italic>\n            events. Hence, in this paper, we present techniques to discover events that are unraveling in microblog message streams in real time so that such events can be reported as soon as they occur. We model the problem as discovering dense clusters in highly dynamic graphs. Despite many recent advances in graph analysis, ours is the first technique to identify dense clusters in massive and highly dynamic graphs in real time. Given the characteristics of microblog streams, in order to find clusters without missing any events, we propose and exploit a novel graph property which we call\n            <jats:italic>short-cycle property<\/jats:italic>\n            . Our algorithms find these clusters efficiently in spite of rapid changes to the microblog streams. Further we present a novel ranking function to identify the important events. Besides proving the correctness of our algorithms we show their practical utility by evaluating them using real world microblog data. These demonstrate our technique's ability to discover, with high precision and recall, emerging events in high intensity data streams in real time. Many recent web applications create data which can be represented as massive dynamic graphs. Our technique can be easily extended to discover, in real time, interesting patterns in such graphs.\n          <\/jats:p>","DOI":"10.14778\/2336664.2336671","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"980-991","source":"Crossref","is-referenced-by-count":62,"title":["Real time discovery of dense clusters in highly dynamic graphs"],"prefix":"10.14778","volume":"5","author":[{"given":"Manoj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"IBM Research-India, New Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krithi","family":"Ramamritham","sequence":"additional","affiliation":[{"name":"IIT-Bombay, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manish","family":"Bhide","sequence":"additional","affiliation":[{"name":"IBM India Software Labs, Hyderabad"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775233"},{"key":"e_1_2_1_2_1","volume-title":"VLDB","author":"Bansal N.","year":"2007","unstructured":"Bansal N. , Chiang F. , Koudas N. , Tompa F. Seeking Stable Clusters in the Blogosphere , VLDB 2007 . Bansal N., Chiang F., Koudas N., Tompa F. Seeking Stable Clusters in the Blogosphere, VLDB 2007."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972788.64"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956816"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2000.839448"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_2_1_9_1","volume-title":"ICALP","author":"Zvi Galil","year":"1991","unstructured":"Zvi Galil , Maintaining biconnected components of a dynamic planar graph . ICALP 1991 . Zvi Galil, Maintaining biconnected components of a dynamic planar graph. ICALP 1991."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772777"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_12_1","unstructured":"http:\/\/blog.seevibes.com\/social-media\/10-historic-moments-that-broke-records-on-twitter\/  http:\/\/blog.seevibes.com\/social-media\/10-historic-moments-that-broke-records-on-twitter\/"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989473"},{"key":"e_1_2_1_14_1","volume-title":"STOC","author":"Matsuda","year":"1999","unstructured":"H. Matsuda , Classifying Molecular Sequences using a Linkage Graph with their Pairwise Similarities . STOC 1999 . H. Matsuda, Classifying Molecular Sequences using a Linkage Graph with their Pairwise Similarities. STOC 1999."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_1_16_1","unstructured":"http:\/\/nlp.stanford.edu\/software\/tagger.shtml  http:\/\/nlp.stanford.edu\/software\/tagger.shtml"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807306"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1814245.1814249"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2336664.2336671","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:45:49Z","timestamp":1672224349000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2336664.2336671"}},"subtitle":["identifying real world events in highly dynamic environments"],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":18,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.14778\/2336664.2336671"],"URL":"https:\/\/doi.org\/10.14778\/2336664.2336671","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}