{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:45:33Z","timestamp":1761597933279,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Prime Minister's Office, Singapore"},{"name":"Pinnacle Lab for Analytics @ Singapore Management University"},{"name":"International Research Centres in Singapore Funding Initiative"},{"DOI":"10.13039\/501100001321","name":"National Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001321","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>Social network services have become important and efficient platforms for users to share all kinds of information. The capability to monitor user-generated information and detect bursts from information diffusions in these social networks brings value to a wide range of real-life applications, such as viral marketing. However, in reality, as a third party, there is always a cost for gathering information from each user or so-called social network sensor. The question then arises how to select a budgeted set of social network sensors to form the data stream for burst detection without compromising the detection performance. In this article, we present a general sensor selection solution for different burst detection approaches. We formulate this problem as a constraint satisfaction problem that has high computational complexity. To reduce the computational cost, we first reduce most of the constraints by making use of the fact that bursty cascades are rare among the whole population. We then transform the problem into an Linear Programming (LP) problem. Furthermore, we use the sub-gradient method instead of the standard simplex method or interior-point method to solve the LP problem, which makes it possible for our solution to scale up to large social networks. Evaluating our solution on millions of real information cascades, we demonstrate both the effectiveness and efficiency of our approach.<\/jats:p>","DOI":"10.1145\/3178048","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Social Network Monitoring for Bursty Cascade Detection"],"prefix":"10.1145","volume":"12","author":[{"given":"Wei","family":"Xie","sequence":"first","affiliation":[{"name":"Singapore Management University, Singapore"}]},{"given":"Feida","family":"Zhu","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}]},{"given":"Jing","family":"Xiao","sequence":"additional","affiliation":[{"name":"Ping An Technology (Shenzhen) Co., Ltd., Shenzhen, China"}]},{"given":"Jianzong","family":"Wang","sequence":"additional","affiliation":[{"name":"Ping An Technology (Shenzhen) Co., Ltd., Shenzhen, China"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247636"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939852"},{"volume-title":"Convex Optimization","author":"Boyd Stephen","key":"e_1_2_1_3_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0012948"},{"volume-title":"Linear Programming and Extensions","author":"Dantzig George Bernard","key":"e_1_2_1_6_1","unstructured":"George Bernard Dantzig . 1998. Linear Programming and Extensions . Princeton University press . George Bernard Dantzig. 1998. Linear Programming and Extensions. Princeton University press."},{"key":"e_1_2_1_7_1","unstructured":"Rina Dechter. 2003. Constraint Processing. Morgan Kaufmann.   Rina Dechter. 2003. Constraint Processing. Morgan Kaufmann."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Conference of the 50th Annual Meeting of the Association for Computational Linguistics","volume":"544","author":"Diao Qiming","year":"2012","unstructured":"Qiming Diao , Jing Jiang , Feida Zhu , and Ee-Peng Lim . 2012 . Finding bursty topics from microblogs . In Proceedings of the Conference of the 50th Annual Meeting of the Association for Computational Linguistics , Volume 1: Long Papers, 536-- 544 . Qiming Diao, Jing Jiang, Feida Zhu, and Ee-Peng Lim. 2012. Finding bursty topics from microblogs. In Proceedings of the Conference of the 50th Annual Meeting of the Association for Computational Linguistics, Volume 1: Long Papers, 536--544."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783411"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1086\/229693"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0092413"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835862"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024940629314"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989734.1989736"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"volume-title":"Optimization Techniques","author":"Minoux Michel","key":"e_1_2_1_18_1","unstructured":"Michel Minoux . 1978. Accelerated greedy algorithms for maximizing submodular set functions . In Optimization Techniques . Springer , 234--243. Michel Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques. Springer, 234--243."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2013.130610"},{"key":"e_1_2_1_20_1","series-title":"Princeton Mathematics Series","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"Rockafellar R. Tyrrell","year":"1970","unstructured":"R. Tyrrell Rockafellar . 1970. Convex Analysis , volume 28 of Princeton Mathematics Series . ( 1970 ). R. Tyrrell Rockafellar. 1970. Convex Analysis, volume 28 of Princeton Mathematics Series. (1970)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772777"},{"key":"e_1_2_1_22_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency.","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24 . Springer Science 8 Business Media. Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer Science 8 Business Media."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623740"},{"key":"e_1_2_1_24_1","unstructured":"Huijuan Shao K. S. M. Tozammel Hossain Hao Wu Maleq Khan Anil Vullikanti B. Aditya Prakash Madhav V. Marathe and Naren Ramakrishnan. 2016. Forecasting the flu: Designing social network sensors for epidemics. arXiv preprint arXiv:1602.06866. http:\/\/arxiv.org\/abs\/1602.06866.  Huijuan Shao K. S. M. Tozammel Hossain Hao Wu Maleq Khan Anil Vullikanti B. Aditya Prakash Madhav V. Marathe and Naren Ramakrishnan. 2016. Forecasting the flu: Designing social network sensors for epidemics. arXiv preprint arXiv:1602.06866. http:\/\/arxiv.org\/abs\/1602.06866."},{"key":"e_1_2_1_25_1","volume-title":"Efficient detection of contagious outbreaks in massive metropolitan encounter networks. CoRR abs\/1401.2815","author":"Sun Lijun","year":"2014","unstructured":"Lijun Sun , Kay W. Axhausen , Der-Horng Lee , and Manuel Cebri\u00e1n . 2014. Efficient detection of contagious outbreaks in massive metropolitan encounter networks. CoRR abs\/1401.2815 ( 2014 ). http:\/\/arxiv.org\/abs\/1401.2815. Lijun Sun, Kay W. Axhausen, Der-Horng Lee, and Manuel Cebri\u00e1n. 2014. Efficient detection of contagious outbreaks in massive metropolitan encounter networks. CoRR abs\/1401.2815 (2014). http:\/\/arxiv.org\/abs\/1401.2815."},{"volume-title":"Advances in Natural Language Processing -- 8th International Conference on NLP (JapTAL\u201912). 239--249.","author":"Takahashi Yusuke","key":"e_1_2_1_26_1","unstructured":"Yusuke Takahashi , Takehito Utsuro , Masaharu Yoshioka , Noriko Kando , Tomohiro Fukuhara , Hiroshi Nakagawa , and Yoji Kiyota . 2012. Applying a burst model to detect bursty topics in a topic model . In Advances in Natural Language Processing -- 8th International Conference on NLP (JapTAL\u201912). 239--249. Yusuke Takahashi, Takehito Utsuro, Masaharu Yoshioka, Noriko Kando, Tomohiro Fukuhara, Hiroshi Nakagawa, and Yoji Kiyota. 2012. Applying a burst model to detect bursty topics in a topic model. In Advances in Natural Language Processing -- 8th International Conference on NLP (JapTAL\u201912). 239--249."},{"key":"e_1_2_1_27_1","unstructured":"Johan Ugander Brian Karrer Lars Backstrom and Cameron Marlow. 2011. The anatomy of the facebook social graph. arXiv preprint arXiv:1111.4503. http:\/\/arxiv.org\/abs\/1111.4503.  Johan Ugander Brian Karrer Lars Backstrom and Cameron Marlow. 2011. The anatomy of the facebook social graph. arXiv preprint arXiv:1111.4503. http:\/\/arxiv.org\/abs\/1111.4503."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2556661"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2014.08.024"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178048","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3178048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:55Z","timestamp":1750215775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3178048"],"URL":"https:\/\/doi.org\/10.1145\/3178048","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}