research-article

Continuous Influence Maximization

Authors:

Xiaofei HeAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 14, Issue 3

Article No.: 29, Pages 1 - 38

https://doi.org/10.1145/3380928

Published: 13 March 2020 Publication History

Abstract

Imagine we are introducing a new product through a social network, where we know for each user in the network the function of purchase probability with respect to discount. Then, what discounts should we offer to those social network users so that, under a predefined budget, the adoption of the product is maximized in expectation? Although influence maximization has been extensively explored, this appealing practical problem still cannot be answered by the existing influence maximization methods. In this article, we tackle the problem systematically. We formulate the general continuous influence maximization problem, investigate the essential properties, and develop a general coordinate descent algorithmic framework as well as the engineering techniques for practical implementation. Our investigation does not assume any specific influence model and thus is general and principled. At the same time, using the most popularly adopted triggering model as a concrete example, we demonstrate that more efficient methods are feasible under specific influence models. Our extensive empirical study on four benchmark real-world networks with synthesized purchase probability curves clearly illustrates that continuous influence maximization can improve influence spread significantly with very moderate extra running time comparing to the classical influence maximization methods.

References

[1]

Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014. Maximizing social influence in nearly optimal time. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 946--957.

[2]

Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. CUP.

[3]

Mike Brennan. 1995. Constructing demand curves from purchase probability data: An application of the juster scale. Marketing Bulletin 6, May (1995), 51--58.

[4]

Wei Chen, Laks V. S. Lakshmanan, and Carlos Castillo. 2013. Information and influence propagation in social networks. Synthesis Lectures on Data Management 5, 4 (2013), 1--177.

[5]

Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1029--1038.

Digital Library

[6]

Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 199--208.

Digital Library

[7]

Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the IEEE 10th International Conference on Data Mining. IEEE, 88--97.

Digital Library

[8]

Yeong Bin Cho, Yoon Ho Cho, and Soung Hie Kim. 2005. Mining changes in customer buying behavior for collaborative recommendations. Expert Systems with Applications 28, 2 (2005), 359--369.

Digital Library

[9]

Paul Dagum, Richard Karp, Michael Luby, and Sheldon Ross. 2000. An optimal algorithm for Monte Carlo estimation. SIAM Journal on Computing 29, 5 (2000), 1484--1496.

Digital Library

[10]

Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, and Morteza Zadimoghadam. 2014. How to influence people with partial incentives. In Proceedings of the 23rd International Conference on World Wide Web. ACM, 937--948.

Digital Library

[11]

Pedro Domingos and Matt Richardson. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 57--66.

Digital Library

[12]

Nan Du, Le Song, Manuel Gomez-Rodriguez, and Hongyuan Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In Proceedings of the 26th International Conference on Neural Information Processing Systems. 3147--3155.

[13]

Milad Eftekhar, Yashar Ganjali, and Nick Koudas. 2013. Information cascade at group scale. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 401--409.

Digital Library

[14]

Mehrdad Farajtabar, Nan Du, Manuel Gomez-Rodriguez, Isabel Valera, Hongyuan Zha, and Le Song. 2014. Shaping social activity by incentivizing users. In Proceedings of the 27th International Conference on Neural Information Processing Systems. ACM, 2474–2482.

[15]

Amit Goyal, Wei Lu, and Laks V. S. Lakshmanan. 2011. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In Proceedings of the IEEE 11th International Conference on Data Mining. IEEE, 211--220.

[16]

Keke Huang, Sibo Wang, Glenn Bevilacqua, Xiaokui Xiao, and Laks V. S. Lakshmanan. 2017. Revisiting the stop-and-stare algorithms for influence maximization. Proceedings of the VLDB Endowment 10, 9 (2017), 913--924.

Digital Library

[17]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 137--146.

Digital Library

[18]

David Kempe, Jon M. Kleinberg, and Éva Tardos. 2015. Maximizing the spread of influence through a social network. Theory of Computing 11, 4 (2015), 105--147.

[19]

Aradhna Krishna. 1994. The impact of dealing patterns on purchase behavior. Marketing Science 13, 4 (1994), 351--373.

Digital Library

[20]

Siyu Lei, Silviu Maniu, Luyi Mo, Reynold Cheng, and Pierre Senellart. 2015. Online influence maximization. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 645--654.

Digital Library

[21]

Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 420--429.

Digital Library

[22]

Hairong Liu, Longin Jan Latecki, and Shuicheng Yan. 2013. Fast detection of dense subgraphs with iterative shrinking and expansion. IEEE Transactions on Pattern Analysis and Machine Intelligence 35, 9 (2013), 2131--2142.

Digital Library

[23]

Qi Liu, Biao Xiang, Enhong Chen, Hui Xiong, Fangshuang Tang, and Jeffrey Xu Yu. 2014. Influence maximization over large-scale social networks: A bounded linear approach. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. ACM, 171--180.

Digital Library

[24]

Qi Liu, Biao Xiang, Nicholas Jing Yuan, Enhong Chen, Hui Xiong, Yi Zheng, and Yu Yang. 2017. An influence propagation view of pagerank. ACM Transactions on Knowledge Discovery from Data 11, 3 (2017), 30.

[25]

Cheng Long and R. C.-W. Wong. 2011. Minimizing seed set for viral marketing. In Proceedings of the IEEE 11th International Conference onData Mining. IEEE, 427--436.

Digital Library

[26]

Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. CUP.

[27]

Elchanan Mossel and Sebastien Roch. 2007. On the submodularity of influence in social networks. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. ACM, 128--134.

Digital Library

[28]

Katta G. Murty and Santosh N. Kabadi. 1987. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming 39, 2 (1987), 117--129.

Digital Library

[29]

Huy Nguyen and Rong Zheng. 2013. On budgeted influence maximization in social networks. IEEE Journal on Selected Areas in Communications 31, 6 (2013), 1084--1094.

[30]

Hung T. Nguyen, My T. Thai, and Thang N. Dinh. 2016. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In Proceedings of the 2016 International Conference on Management of Data. ACM, 695--710.

[31]

Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. CUP.

[32]

Yaron Singer. 2012. How to win friends and influence people, truthfully: Influence maximization mechanisms for social networks. In Proceedings of the 5th ACM International Conference on Web Search and Data Mining. ACM, 733--742.

Digital Library

[33]

Euiho Suh, Seungjae Lim, Hyunseok Hwang, and Suyeon Kim. 2004. A prediction model for the purchase probability of anonymous customers to support real time web marketing: A case study. Expert Systems with Applications 27, 2 (2004), 245--255.

[34]

Maxim Sviridenko. 2004. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters 32, 1 (2004), 41--43.

Digital Library

[35]

Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 1539–1554.

Digital Library

[36]

Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. ACM, 75--86.

Digital Library

[37]

Gaebler Ventures. 2013. Business Advertising. Retrieved from http://www.gaebler.com/Business-Advertising.htm.

[38]

Yue Wang, WeiJing Huang, Lang Zong, TengJiao Wang, and DongQing Yang. 2013. Influence maximization with limit cost in social network. Science China Information Sciences 56, 7 (2013), 1--14.

[39]

Zhefeng Wang, Enhong Chen, Qi Liu, Yu Yang, Yong Ge, and Biao Chang. 2015. Maximizing the coverage of information propagation in social networks. In Proceedings of the 24th International Joint Conference on Artificial Intelligence. ACM, 2104–2110.

[40]

Yu Yang, Xiangbo Mao, Jian Pei, and Xiaofei He. 2016. Continuous influence maximization: What discounts should we offer to social network users? In Proceedings of the 2016 International Conference on Management of Data. ACM, 727--741.

Digital Library

[41]

Jing Yuan and Shao-Jie Tang. 2017. Adaptive discount allocation in social networks. In Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 22.

Digital Library

Cited By

HUSSAIN OZAIDI F(2024)IMine: A CUSTOMIZABLE FRAMEWORK FOR INFLUENCE MINING IN COMPLEX NETWORKSAdvances in Complex Systems10.1142/S021952592450004827:01n02Online publication date: 27-Jun-2024
https://doi.org/10.1142/S0219525924500048
Garg PWu W(2022)Social network analysis and applications: A review of the broad research aspects of social network structureDiscrete Mathematics, Algorithms and Applications10.1142/S179383092230001614:06Online publication date: 20-Jun-2022
https://doi.org/10.1142/S1793830922300016
Ni QGuo JDu HWang H(2022)Multi-attribute based influence maximization in social networks: Algorithms and analysisTheoretical Computer Science10.1016/j.tcs.2022.03.041921(50-62)Online publication date: Jun-2022
https://doi.org/10.1016/j.tcs.2022.03.041
Show More Cited By

Index Terms

Continuous Influence Maximization

Recommendations

Continuous Influence Maximization: What Discounts Should We Offer to Social Network Users?
SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Imagine we are introducing a new product through a social network, where we know for each user in the network the purchase probability curve with respect to discount. Then, what discount should we offer to those social network users so that the adoption ...
Diversified social influence maximization
ASONAM '14: Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

For better viral marketing, there has been a lot of research on social influence maximization. However, the problem that who is influenced and how diverse the influenced population is, which is important in real-world marketing, has largely been ...
On the Robustness of Influence Maximization Algorithms against Non-Adversarial Perturbations
ASONAM '17: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017

Influence maximization is a combinatorial optimization problem on a graph: Given a social network, an influence maximization algorithm aims to find a set of influential (seed) nodes in the network such that the expected number of nodes influenced by the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 14, Issue 3

June 2020

381 pages

ISSN:1556-4681

EISSN:1556-472X

DOI:10.1145/3388473

Editors:
Charu Aggarwal
IBM T. J. Watson Research, USA
,
Xindong Wu
Minginglamp Academy of Sciences, China

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 March 2020

Accepted: 01 November 2019

Revised: 01 August 2019

Received: 01 August 2018

Published in TKDD Volume 14, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
649
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)7

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

HUSSAIN OZAIDI F(2024)IMine: A CUSTOMIZABLE FRAMEWORK FOR INFLUENCE MINING IN COMPLEX NETWORKSAdvances in Complex Systems10.1142/S021952592450004827:01n02Online publication date: 27-Jun-2024
https://doi.org/10.1142/S0219525924500048
Garg PWu W(2022)Social network analysis and applications: A review of the broad research aspects of social network structureDiscrete Mathematics, Algorithms and Applications10.1142/S179383092230001614:06Online publication date: 20-Jun-2022
https://doi.org/10.1142/S1793830922300016
Ni QGuo JDu HWang H(2022)Multi-attribute based influence maximization in social networks: Algorithms and analysisTheoretical Computer Science10.1016/j.tcs.2022.03.041921(50-62)Online publication date: Jun-2022
https://doi.org/10.1016/j.tcs.2022.03.041
Xiao MLi PHuang WXiao JNie L(2022)Community Influence Maximization Based on Flexible Budget in Social NetworksCollaborative Computing: Networking, Applications and Worksharing10.1007/978-3-030-92635-9_31(534-553)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-92635-9_31
Li DWang YLi MSun XPan JMa J(2021)Net positive influence maximization in signed social networksJournal of Intelligent & Fuzzy Systems10.3233/JIFS-191908(1-12)Online publication date: 24-Jun-2021
https://doi.org/10.3233/JIFS-191908
Ahmadi Beni HBouyer A(2021)Identifying Influential Nodes Using a Shell-Based Ranking and Filtering Method in Social NetworksBig Data10.1089/big.2020.02599:3(219-232)Online publication date: 1-Jun-2021
https://doi.org/10.1089/big.2020.0259
Ni QGuo JDu H(2021)Multi-attribute Based Influence Maximization in Social NetworksAlgorithmic Aspects in Information and Management10.1007/978-3-030-93176-6_21(240-251)Online publication date: 20-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-93176-6_21

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents