skip to main content
research-article
Open access

Maximizing Boosted Influence Spread with Edge Addition in Online Social Networks

Published: 30 May 2020 Publication History

Abstract

Influence maximization with application to viral marketing is a well-studied problem of finding a small number of influential users in a social network to maximize the spread of influence under certain influence cascade models. However, almost all previous studies have focused on node-level mining, where they consider identifying nodes as the initial seeders to achieve the desired outcomes. In this article, instead of targeting nodes, we investigate a new boosted influence maximization problem from the edge-level perspective, which asks for finding an edge set that is added to the network to maximize the increased influence spread of a given seed set. We show that the problem is NP-hard and the influence spread function no longer exhibits the property of submodularity, which impose more challenging on the problem. Therefore, we devise a restricted form that is submodular and propose a greedy algorithm with approximate guarantee to solve the problem. However, because of its poor computational efficiency, we further propose an improved greedy algorithm that integrates several effective optimization strategies to significantly speed up the edge selection without sacrificing its accuracy. Extensive experiments over real-world available social networks of different sizes demonstrate the effectiveness and efficiency of the proposed methods.

References

[1]
Stefanos Antaris, Dimitrios Rafailidis, and Alexandros Nanopoulos. 2014. Link injection for boosting information spread in social networks. Soc. Netw. Anal. Min. 4, 1 (2014), 1--16.
[2]
Ilija Bogunovic, Junyao Zhao, and Volkan Cevher. 2018. Robust maximization of nonsubmodular objectives. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS’18).
[3]
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, 946--957.
[4]
Erik Cambria, Marco Grassi, Amir Hussain, and Catherine Havasi. 2012. Sentic computing for social media marketing. Multimedia Tools Appl. 59, 2 (2012), 557--577.
[5]
Vineet Chaoji, Sayan Ranu, Rajeev Rastogi, and Rushi Bhatt. 2012. Recommendations to boost content spread in social networks. In Proceedings of the 21st ACM International Conference on World Wide Web, 529--539.
[6]
Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1029--1038.
[7]
Wei Chen, Yifei Yuan, and Li Zhang. 2011. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 10th IEEE International Conference on Data Mining, 88--97.
[8]
Yi-Cheng Chen, Wen-Yuan Zhu, Wen-Chih Peng, Wang-Chien Lee, and Suh-Yin Lee. 2014. CIM: Community-based influence maximization in social networks. ACM Trans. Intell. Syst. Technol. 5, 2 (2014), 1--31.
[9]
Judith A. Chevalier and Dina Mayzlin. 2006. The effect of word-of-mouth on sales: Online book reviews. J. Market. Res. 43, 3 (2006), 345--354.
[10]
Pierluigi Crescenzi, Gianlorenzo D’angelo, Lorenzo Severini, and Yllka Velaj. 2016. Greedily improving our own closeness centrality in a network. ACM Trans. Knowl. Discov. Data 11, 1, Article 9 (2016), 32 pages.
[11]
Gianlorenzo D’Angelo, Lorenzo Severini, and Yllka Velaj. 2019. Recommending links through influence maximization. Theoretical Computer Science 764 (2019), 30--41.
[12]
Abhimanyu Das and David Kempe. 2011. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of International Conference on Machine Learning, 1057--1064.
[13]
Erik D. Demaine and Morteza Zadimoghaddam. 2010. Minimizing the diameter of a network using shortcut edges. In Proceedings of theScandinavian Conference on Algorithm Theory, 420--431.
[14]
Pedro Domingos and Matthew Richardson. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 57--66.
[15]
Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, and Luke Mathieson. 2015. Augmenting graphs to minimize the diameter. Algorithmica 72, 4 (2015), 995--1010.
[16]
Valiant Leslie G. 1979. The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 3 (1979), 410--421.
[17]
Chao Gao, Jiming Liu, and Ning Zhong. 2011. Network immunization and virus propagation in email networks: experimental evaluation and analysis. Knowl. Inf. Syst. 27, 2 (2011), 253--279.
[18]
Arpita Ghosh and Stephen Boyd. 2006. Growing well-connected graphs. In Proceedings of the IEEE Conference on Decision and Control, 6605--6611.
[19]
Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Market. Lett. 12, 3 (2001), 211--223.
[20]
Amit Goyal, Wei Lu, and Laks V. S. Lakshmanan. 2011. Celf++: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the ACM International Conference Companion on World Wide Web, 47--48.
[21]
Kyomin Jung, Wooram Heo, and Wei Chen. 2013. IRIE: Scalable and robust influence maximization in social networks. In Proceedings of the IEEE International Conference on Data Mining, 918--923.
[22]
Richard Karp. 2010. Reducibility among combinatorial problems. J. Symbol. Logic 40, 4 (2010), 618--619.
[23]
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, 137--146.
[24]
Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2008. Minimizing the spread of contamination by blocking links in a network. In Proceedings of the 23rd National Conference on Artificial Intelligence, 1175--1180.
[25]
Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2008. Solving the contamination minimization problem on networks for the linear threshold model. Malay. J. Med. Sci. 12, 2 (2008), 50--55.
[26]
Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2009. Blocking links to minimize contamination spread in a social network. ACM Trans. Knowl. Discov. Data 3, 2 Article 9 (2009), 23.
[27]
Chris J. Kuhlman, Gaurav Tuli, Samarth Swarup, Madhav V. Marathe, and S. S. Ravi. 2013. Blocking simple and complex contagion by edge removal. In Proceedings of the IEEE International Conference on Data Mining, 399--408.
[28]
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Natalie Glance, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 420--429.
[29]
Yanhua Li, Wei Chen, Yajun Wang, and Zhi-Li Zhang. 2013. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. Proceedings of the ACM International Conference on Web Search and Data Mining, 657--666.
[30]
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. 128--134.
[31]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. 1978. An analysis of the approximations for maximizing submodular set functions. Math. Program. 14, 1 (1978), 265--294.
[32]
M. E. J. Newman. 2003. The structure and function of complex networks. SIAM Rev. 45, 2 (2003), 167--256.
[33]
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 ACM International Conference on Management of Data, 695--710.
[34]
Manos Papagelis. 2015. Refining social graph connectivity via shortcut edge addition. ACM Trans. Knowl. Discov. Data 10, 2, Article 12 (2015), 35 pages.
[35]
Guido Proietti. 2012. Improved approximability and non-approximability results for graph diameter decreasing problems. Theor. Comput. Sci. 417, 1 (2012), 12--22.
[36]
Khadije Rahimkhani, Abolfazl Aleahmad, Maseud Rahgozar, and Ali Moeini. 2015. A fast algorithm for finding most influential people based on the linear threshold model. Exp. Syst. Appl. 42, 3 (2015), 1353--1361.
[37]
Matthew Richardson and Pedro Domingos. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 61--70.
[38]
SNAP Datasets. 2014. Retrieved from http://snap.stanford.edu/data/.
[39]
Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence maximization in near-linear time: A martingale approach. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1539--1554.
[40]
Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of ACM SIGMOD International Conference on Management of Data, 75--86.
[41]
Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. 2010. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1039--1048.
[42]
Chuan Zhou, Peng Zhang, Wenyu Zang, and Li Guo. 2014. Maximizing the long-term integral influence in social networks under the voter model. In Proceedings of the ACM International Conference on World Wide Web, 423--424.

Cited By

View all
  • (2024)Defending Against Malicious Influence Control in Online Leader-Follower Social NetworksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.338324419(4809-4819)Online publication date: 29-Mar-2024
  • (2023)Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.331626836:5(2151-2165)Online publication date: 18-Sep-2023
  • (2022)Minimizing the Importance Inequality of Nodes in a Social Network GraphProceedings of the 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM55673.2022.10068586(194-201)Online publication date: 10-Nov-2022

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM/IMS Transactions on Data Science
ACM/IMS Transactions on Data Science  Volume 1, Issue 2
May 2020
169 pages
ISSN:2691-1922
DOI:10.1145/3403596
Issue’s Table of Contents
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: 30 May 2020
Accepted: 01 September 2019
Revised: 01 July 2019
Received: 01 March 2019
Published in TDS Volume 1, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Boosted influence maximization
  2. edge addition
  3. online social networks
  4. viral marketing

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)157
  • Downloads (Last 6 weeks)27
Reflects downloads up to 15 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Defending Against Malicious Influence Control in Online Leader-Follower Social NetworksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.338324419(4809-4819)Online publication date: 29-Mar-2024
  • (2023)Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.331626836:5(2151-2165)Online publication date: 18-Sep-2023
  • (2022)Minimizing the Importance Inequality of Nodes in a Social Network GraphProceedings of the 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM55673.2022.10068586(194-201)Online publication date: 10-Nov-2022
  • (2020)Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approachesInternational Transactions in Operational Research10.1111/itor.1285428:3(1242-1264)Online publication date: 2-Aug-2020

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media