{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T23:04:51Z","timestamp":1708038291679},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T00:00:00Z","timestamp":1454889600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"International Conference on Machine Learning"},{"name":"Neural Information Processing Systems"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2016,4,20]]},"abstract":"\n If a piece of information is released from a set of media sites, can it spread, in 1 month, to a million web pages? Can we efficiently find a small set of media sites among millions that can maximize the spread of the information, in 1 month? The two problems are called influence estimation and maximization problems respectively, which are very challenging since both the time-sensitive nature of the problems and the issue of scalability need to be addressed simultaneously. In this article, we propose two algorithms for influence estimation in continuous-time diffusion networks. The first one uses continuous-time Markov chains to estimate influence\n exactly<\/jats:italic>\n on networks with exponential, or, more generally, phase-type transmission functions, but does not scale to large-scale networks, and the second one is a highly efficient randomized algorithm, which estimates the influence of every node in a network with general transmission functions, |\u03bd| nodes and |\u03b5| edges to an accuracy of \u03f5 using\n n<\/jats:italic>\n =\n O<\/jats:italic>\n (1\/\u03f5\n 2<\/jats:sup>\n ) randomizations and up to logarithmic factors\n O<\/jats:italic>\n (\n n<\/jats:italic>\n |\u03b5|+\n n<\/jats:italic>\n |\u03bd| computations. We then show that finding the set of most influential source nodes in a continuous time diffusion network is an NP-hard problem and develop an efficient greedy algorithm with provable near-optimal performance. When used as subroutines in the influence maximization algorithm, the exact influence estimation algorithm is guaranteed to find a set of\n C<\/jats:italic>\n nodes with an influence of at least (1 \u2212 1\/\n e<\/jats:italic>\n )OPT and the randomized algorithm is guaranteed to find a set with an influence of at least 1 \u2212 1\/\n e<\/jats:italic>\n )OPT \u2212 2\n C<\/jats:italic>\n \u03b5, where OPT is the optimal value. Experiments on both synthetic and real-world data show that the proposed algorithms significantly improve over previous state-of-the-art methods in terms of the accuracy of the estimated influence and the quality of the selected nodes to maximize the influence, and the randomized algorithm can easily scale up to networks of millions of nodes.\n <\/jats:p>","DOI":"10.1145\/2824253","type":"journal-article","created":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T22:37:07Z","timestamp":1454971027000},"page":"1-33","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Influence Estimation and Maximization in Continuous-Time Diffusion Networks"],"prefix":"10.1145","volume":"34","author":[{"given":"Manuel","family":"Gomez-Rodriguez","sequence":"first","affiliation":[{"name":"MPI for Software Systems, Kaiserslautern, Germany"}]},{"given":"Le","family":"Song","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, GA, USA"}]},{"given":"Nan","family":"Du","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, GA, USA"}]},{"given":"Hongyuan","family":"Zha","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, GA, USA"}]},{"given":"Bernhard","family":"Sch\u00f6lkopf","sequence":"additional","affiliation":[{"name":"MPI for Intelligent Systems, T\u00fcbingen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2016,2,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"419","article-title":"Fitting phase-type distributions via the EM algorithm","volume":"23","author":"Asmussen S.","year":"1996","unstructured":"S. Asmussen and O. Nerman . 1996 . Fitting phase-type distributions via the EM algorithm . Scandinavian Journal of Statistics 23 , 4 (1996), 419 -- 441 . S. Asmussen and O. Nerman. 1996. Fitting phase-type distributions via the EM algorithm. Scandinavian Journal of Statistics 23, 4 (1996), 419--441.","journal-title":"Scandinavian Journal of Statistics"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0646-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"S. Bharathi D. Kempe and M. Salek. 2007. Competitive influence maximization in social networks. Internet and Network Economics (2007) 306--311. S. Bharathi D. Kempe and M. Salek. 2007. Competitive influence maximization in social networks. Internet and Network Economics (2007) 306--311.","DOI":"10.1007\/978-3-540-77105-0_31"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 4th ACM International Conference on Web Search and Data Mining.","author":"Budak C.","unstructured":"C. Budak , D. Agrawal , and A. El Abbadi . 2011. Limiting the spread of misinformation in social networks . In Proceedings of the 4th ACM International Conference on Web Search and Data Mining. C. Budak, D. Agrawal, and A. El Abbadi. 2011. Limiting the spread of misinformation in social networks. In Proceedings of the 4th ACM International Conference on Web Search and Data Mining."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1282100.1282167"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the SIAM Conference on Data Mining. 379--390","author":"Chen W.","unstructured":"W. Chen , A. Collins , R. Cummings , T. Ke , Z. Liu , D. Rincon , X. Sun , Y. Wang , W. Wei , and Y. Yuan . 2011. Influence maximization in social networks when negative opinions may emerge and propagate . In Proceedings of the SIAM Conference on Data Mining. 379--390 . W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rincon, X. Sun, Y. Wang, W. Wei, and Y. Yuan. 2011. Influence maximization in social networks when negative opinions may emerge and propagate. In Proceedings of the SIAM Conference on Data Mining. 379--390."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 26th AAAI Conference on Artificial Intelligence.","author":"Chen W.","unstructured":"W. Chen , W. Lu , and N. Zhang . 2012. Time-critical influence maximization in social networks with time-delayed diffusion process . In Proceedings of the 26th AAAI Conference on Artificial Intelligence. W. Chen, W. Lu, and N. Zhang. 2012. Time-critical influence maximization in social networks with time-delayed diffusion process. In Proceedings of the 26th AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_10_1","volume-title":"Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191","author":"Clauset A.","year":"2008","unstructured":"A. Clauset , C. Moore , and M. E. J. Newman . 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191 ( 2008 ), 98--101. A. Clauset, C. Moore, and M. E. J. Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191 (2008), 98--101."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_12_1","unstructured":"E. Cohen D. Delling T. Pajor and R. F. Werneck. 2014. Timed influence: Computation and maximization. arXiv Preprint arXiv:1410.6976 (2014). E. Cohen D. Delling T. Pajor and R. F. Werneck. 2014. Timed influence: Computation and maximization. arXiv Preprint arXiv:1410.6976 (2014)."},{"key":"e_1_2_1_13_1","unstructured":"N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In Neural Information Processing Systems (NIPS). N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_14_1","unstructured":"N. Du L. Song A. Smola and M. Yuan. 2012. Learning networks of heterogeneous influence. In Advances in Neural Information Processing Systems. N. Du L. Song A. Smola and M. Yuan. 2012. Learning networks of heterogeneous influence. In Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS).","author":"Du N.","unstructured":"N. Du , L. Song , H. Woo , and H. Zha . 2013. Uncover topic-sensitive information diffusion networks . In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS). N. Du, L. Song, H. Woo, and H. Zha. 2013. Uncover topic-sensitive information diffusion networks. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS)."},{"key":"e_1_2_1_16_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s P.","year":"1960","unstructured":"P. Erd\u0151s and A. R\u00e9nyi . 1960 . On the evolution of random graphs . Publication of the Mathematical Institute of the Hungarian Academy of Science 5 (1960), 17 -- 67 . P. Erd\u0151s and A. R\u00e9nyi. 1960. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Science 5 (1960), 17--67.","journal-title":"Publication of the Mathematical Institute of the Hungarian Academy of Science"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00119"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 28th International Conference on Machine Learning.","author":"Gomez-Rodriguez M.","unstructured":"M. Gomez-Rodriguez , D. Balduzzi , and B. Sch\u00f6lkopf . 2011. Uncovering the temporal dynamics of diffusion networks . In Proceedings of the 28th International Conference on Machine Learning. M. Gomez-Rodriguez, D. Balduzzi, and B. Sch\u00f6lkopf. 2011. Uncovering the temporal dynamics of diffusion networks. In Proceedings of the 28th International Conference on Machine Learning."},{"key":"e_1_2_1_19_1","unstructured":"M. Gomez-Rodriguez J. Leskovec D. Balduzzi and B. Sch\u00f6lkopf. 2013c. Uncovering the structure and temporal dynamics of information propagation. Network Science (2013). M. Gomez-Rodriguez J. Leskovec D. Balduzzi and B. Sch\u00f6lkopf. 2013c. Uncovering the structure and temporal dynamics of information propagation. Network Science (2013)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835933"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning (ICML).","author":"Gomez-Rodriguez M.","unstructured":"M. Gomez-Rodriguez , J. Leskovec , and B. Sch\u00f6lkopf . 2013a. Modeling information propagation with survival theory . In Proceedings of the 30th International Conference on Machine Learning (ICML). M. Gomez-Rodriguez, J. Leskovec, and B. Sch\u00f6lkopf. 2013a. Modeling information propagation with survival theory. In Proceedings of the 30th International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433402"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning.","author":"Gomez-Rodriguez M.","unstructured":"M. Gomez-Rodriguez and B. Sch\u00f6lkopf . 2012a. Influence maximization in continuous time diffusion networks . In Proceedings of the 29th International Conference on Machine Learning. M. Gomez-Rodriguez and B. Sch\u00f6lkopf. 2012a. Influence maximization in continuous time diffusion networks. In Proceedings of the 29th International Conference on Machine Learning."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning.","author":"Gomez-Rodriguez M.","unstructured":"M. Gomez-Rodriguez and B. Sch\u00f6lkopf . 2012b. Submodular inference of diffusion networks from multiple trees . In Proceedings of the 29th International Conference on Machine Learning. M. Gomez-Rodriguez and B. Sch\u00f6lkopf. 2012b. Submodular inference of diffusion networks from multiple trees. In Proceedings of the 29th International Conference on Machine Learning."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-012-0062-z"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of 3rd International Conference on Matrix-Analytic Methods in Stochastic models.","author":"Horvath A.","unstructured":"A. Horvath and M. Telek . 2000. Approximating heavy tailed behaviour with phase type distributions . In Proceedings of 3rd International Conference on Matrix-Analytic Methods in Stochastic models. A. Horvath and M. Telek. 2000. Approximating heavy tailed behaviour with phase type distributions. In Proceedings of 3rd International Conference on Matrix-Analytic Methods in Stochastic models."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2010.127"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 25th Conference on Artificial Intelligence (AAAI).","author":"Irfan M. T.","unstructured":"M. T. Irfan and L. E. Ortiz . 2011. A game-theoretic approach to influence in networks . In Proceedings of the 25th Conference on Artificial Intelligence (AAAI). M. T. Irfan and L. E. Ortiz. 2011. A game-theoretic approach to influence in networks. In Proceedings of the 25th Conference on Artificial Intelligence (AAAI)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487624"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3120676.3120705"},{"key":"e_1_2_1_33_1","unstructured":"A. Krause. 2008. Optimizing Sensing: Theory and Applications. Ph.D. Thesis. CMU. A. Krause. 2008. Optimizing Sensing: Theory and Applications. Ph.D. Thesis. CMU."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230160303"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835937"},{"key":"e_1_2_1_36_1","volume-title":"Statistical Models and Methods for Lifetime Data","author":"Lawless J. F.","unstructured":"J. F. Lawless . 1982. Statistical Models and Methods for Lifetime Data . Wiley New York . J. F. Lawless. 1982. Statistical Models and Methods for Lifetime Data. Wiley New York."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134732"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557077"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1756039"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.158"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0006528"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 12th ACM SIGMETRICS\/Performance.","author":"Netrapalli P.","unstructured":"P. Netrapalli and S. Sanghavi . 2012. Finding the graph of epidemic cascades . In Proceedings of the 12th ACM SIGMETRICS\/Performance. P. Netrapalli and S. Sanghavi. 2012. Finding the graph of epidemic cascades. In Proceedings of the 12th ACM SIGMETRICS\/Performance."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.3.516"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01961544"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the European conference on Machine Learning and knowledge Discovery in Databases (PKDD).","author":"Saito K.","unstructured":"K. Saito , M. Kimura , K. Ohara , and H. Motoda . 2010. Selecting information diffusion models over social networks for behavioral analysis . In Proceedings of the European conference on Machine Learning and knowledge Discovery in Databases (PKDD). K. Saito, M. Kimura, K. Ohara, and H. Motoda. 2010. Selecting information diffusion models over social networks for behavioral analysis. In Proceedings of the European conference on Machine Learning and knowledge Discovery in Databases (PKDD)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/285861.285868"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124381"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1093\/aje\/kwh255"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2824253","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T07:59:05Z","timestamp":1672473545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2824253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,8]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4,20]]}},"alternative-id":["10.1145\/2824253"],"URL":"http:\/\/dx.doi.org\/10.1145\/2824253","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":["Computer Science Applications","General Business, Management and Accounting","Information Systems"],"published":{"date-parts":[[2016,2,8]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}