{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T13:49:49Z","timestamp":1764251389381},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>\n            Monitoring the formation and evolution of communities in large online social networks such as Twitter is an important problem that has generated considerable interest in both industry and academia. Fundamentally, the problem can be cast as studying evolving sugraphs (each subgraph corresponding to a topical community) on an underlying social graph - with users as nodes and the connection between them as edges. A key metric of interest in this setting is tracking the changes to the\n            <jats:italic>conductance<\/jats:italic>\n            of subgraphs induced by edge activations. This metric quantifies how well or poorly connected a subgraph is to the rest of the graph relative to its internal connections. Conductance has been demonstrated to be of great use in many applications, such as identifying bursty topics, tracking the spread of rumors, and so on. However, tracking this simple metric presents a considerable scalability challenge - the underlying social network is large, the number of communities that are active at any moment is large, the rate at which these communities evolve is high, and moreover, we need to track conductance in real-time. We address these challenges in this paper.\n          <\/jats:p>\n          <jats:p>\n            We propose an in-memory approximation called\n            <jats:italic>BloomGraphs<\/jats:italic>\n            to store and update these (possibly overlapping) evolving subgraphs. As the name suggests, we use Bloom filters to represent an approximation of the underlying graph. This representation is compact and computationally efficient to maintain in the presence of updates. This is especially important when we need to\n            <jats:italic>simultaneously<\/jats:italic>\n            maintain thousands of evolving subgraphs. BloomGraphs are used in computing and tracking conductance of these subgraphs as edge-activations arrive. BloomGraphs have several desirable properties in the context of this application, including a small memory footprint and efficient updateability. We also demonstrate mathematically that the error incurred in computing conductance is one-sided and that in the case of evolving subgraphs the change in approximate conductance has the same sign as the change in exact conductance in most cases. We validate the effectiveness of BloomGraphs through extensive experimentation on large Twitter graphs and other social networks.\n          <\/jats:p>","DOI":"10.14778\/2831360.2831370","type":"journal-article","created":{"date-parts":[[2015,9,30]],"date-time":"2015-09-30T12:16:36Z","timestamp":1443615396000},"page":"2170-2181","source":"Crossref","is-referenced-by-count":13,"title":["Tracking the conductance of rapidly evolving topic-subgraphs"],"prefix":"10.14778","volume":"8","author":[{"given":"Sainyam","family":"Galhotra","sequence":"first","affiliation":[{"name":"XRCI, Bangalore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amitabha","family":"Bagchi","sequence":"additional","affiliation":[{"name":"IIT Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srikanta","family":"Bedathur","sequence":"additional","affiliation":[{"name":"IBM Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maya","family":"Ramanath","sequence":"additional","affiliation":[{"name":"IIT Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vidit","family":"Jain","sequence":"additional","affiliation":[{"name":"American Express Big Data Labs, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.140"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505525"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2493175.2493178"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_5_1","volume-title":"Proc. 5th Intl. Conf. on Weblogs and Social Media (ICWSM '11)","author":"Becker H.","year":"2011","unstructured":"H. Becker , F. Chen , D. Iter , M. Naaman , and L. Gravano . Automatic identification and presentation of twitter content for planned events . In Proc. 5th Intl. Conf. on Weblogs and Social Media (ICWSM '11) , 2011 . H. Becker, F. Chen, D. Iter, M. Naaman, and L. Gravano. Automatic identification and presentation of twitter content for planned events. In Proc. 5th Intl. Conf. on Weblogs and Social Media (ICWSM '11), 2011."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","volume-title":"April","author":"Bora S.","year":"2015","unstructured":"S. Bora , H. Singh , A. Sen , A. Bagchi , and P. Singla . On the role of conductance, geography and topology in predicting hashtag virality. arXiv:1504.05351 {cs.SI} , April 2015 . S. Bora, H. Singh, A. Sen, A. Bagchi, and P. Singla. On the role of conductance, geography and topology in predicting hashtag virality. arXiv:1504.05351 {cs.SI}, April 2015."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_9_1","volume-title":"\u00dcber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen. J. f\u00fcr die reine und angewandte Mathematik, 77:258--262","author":"Cantor G.","year":"1874","unstructured":"G. Cantor . \u00dcber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen. J. f\u00fcr die reine und angewandte Mathematik, 77:258--262 , 1874 . G. Cantor. \u00dcber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen. J. f\u00fcr die reine und angewandte Mathematik, 77:258--262, 1874."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1814245.1814249"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-8-22"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109635"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142477"},{"key":"e_1_2_1_16_1","first-page":"536","volume-title":"Proc. 50th Ann. Meeting of the Assoc for Computational Lingustics (ACL 2012","volume":"1","author":"Diao Q.","year":"2012","unstructured":"Q. Diao , J. Jiang , F. Zhu , and E. Lim . Finding bursty topics from microblogs . In Proc. 50th Ann. Meeting of the Assoc for Computational Lingustics (ACL 2012 ), volume 1 , pages 536 -- 544 , 2012 . Q. Diao, J. Jiang, F. Zhu, and E. Lim. Finding bursty topics from microblogs. In Proc. 50th Ann. Meeting of the Assoc for Computational Lingustics (ACL 2012), volume 1, pages 536--544, 2012."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339628"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835815"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.57"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3160237.3160243"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_23_1","volume-title":"NOW","author":"Kannan R.","year":"2009","unstructured":"R. Kannan and S. Vempala . Spectral Algorithms . NOW , Delft, Netherlands , 2009 . R. Kannan and S. Vempala. Spectral Algorithms. NOW, Delft, Netherlands, 2009."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_42"},{"key":"e_1_2_1_26_1","unstructured":"R. Krikorian. New tweets per second record and how! Twitter Engineering Blog 16th August 2013. https:\/\/blog.twitter.com\/2013\/new-tweets-per-second-record-and-how.  R. Krikorian. New tweets per second record and how! Twitter Engineering Blog 16th August 2013. https:\/\/blog.twitter.com\/2013\/new-tweets-per-second-record-and-how."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772755"},{"key":"e_1_2_1_29_1","volume-title":"AMS","author":"Levin D. A.","year":"2009","unstructured":"D. A. Levin , Y. Peres , and E. L. Wilmer . Markov Chains and Mixing Times . AMS , 2009 . D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. AMS, 2009."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040402"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807306"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060753"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213854"},{"key":"e_1_2_1_34_1","article-title":"How One Stupid Tweet Blew Up Justine Sacco's Life","author":"Ronson J.","year":"2015","unstructured":"J. Ronson . How One Stupid Tweet Blew Up Justine Sacco's Life . New York Times Magazine , Feb 2015 . http:\/\/www.nytimes.com\/2015\/02\/15\/magazine\/how-one-stupid-tweet-ruined-justine-saccos-life.html. J. Ronson. How One Stupid Tweet Blew Up Justine Sacco's Life. New York Times Magazine, Feb 2015. http:\/\/www.nytimes.com\/2015\/02\/15\/magazine\/how-one-stupid-tweet-ruined-justine-saccos-life.html.","journal-title":"New York Times Magazine"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376928"},{"key":"e_1_2_1_36_1","volume-title":"8th Intl. AAAI Conference on Weblogs and Social Media (ICWSM 2013)","author":"Weng L.","year":"2013","unstructured":"L. Weng , F. Menczer , and Y.-Y. Ahn . Predicting successful memes using network and community structure . In 8th Intl. AAAI Conference on Weblogs and Social Media (ICWSM 2013) , 2013 . L. Weng, F. Menczer, and Y.-Y. Ahn. Predicting successful memes using network and community structure. In 8th Intl. AAAI Conference on Weblogs and Social Media (ICWSM 2013), 2013."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep02522"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2831360.2831370","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:29:30Z","timestamp":1672219770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2831360.2831370"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":37,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.14778\/2831360.2831370"],"URL":"https:\/\/doi.org\/10.14778\/2831360.2831370","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}