Influence Maximization on Undirected Graphs: Towards Closing the (1-1/e) Gap

ABSTRACT

We study the influence maximization problem in undirected networks, specifically focusing on the independent cascade and linear threshold models. We prove APX-hardness (NP-hardness of approximation within factor (1-τ) for some constant τ>0$) for both models, which improves the previous NP-hardness lower bound for the linear threshold model. No previous hardness result was known for the independent cascade model.

As part of the hardness proof, we show some natural properties of these cascades on undirected graphs. For example, we show that the expected number of infections of a seed set S is upper-bounded by the size of the edge cut of S in the linear threshold model and a special case of the independent cascade model called the weighted independent cascade model. Motivated by our upper bounds, we present a suite of highly scalable local greedy heuristics for the influence maximization problem on both the linear threshold model and the weighted independent cascade model on undirected graphs that, in practice, find seed sets which on average obtain 97.52% of the performance of the much slower greedy algorithm for the linear threshold model, and 97.39% of the performance of the greedy algorithm for the weighted independent cascade model. Our heuristics also outperform other popular local heuristics, such as the degree discount heuristic by Chen et al.

References

1. Rico Angell and Grant Schoenebeck. 2017. Don't be greedy: Leveraging community structure to find high quality seed sets for influence maximization. In International Conference on Web and Internet Economics. Springer, 16--29.
2. Akhil Arora, Sainyam Galhotra, and Sayan Ranu. 2017. Debunking the myths of influence maximization: An in-depth benchmarking study. In Proceedings of the 2017 ACM International Conference on Management of Data. ACM, 651--666.
3. Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014. Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 946--957.
4. Ning Chen. 2009. On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, Vol. 23, 3 (2009), 1400--1415.
5. Wei Chen. 2018. An issue in the martingale analysis of the influence maximization algorithm IMM. In International Conference on Computational Social Networks. Springer, 286--297.
6. Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In ACM SIGKDD. ACM, 199--208.
7. Wei Chen, Yifei Yuan, and Li Zhang. 2010a. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In 2010 IEEE International Conference on Data Mining. IEEE, 88--97.
8. Wei Chen, Yifei Yuan, and Li Zhang. 2010b. Scalable influence maximization in social networks under the linear threshold model. In Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 88--97.
9. Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, and Xueqi Cheng. 2013. Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management. ACM, 509--518.
10. Irit Dinur. 2007. The PCP theorem by gap amplification. Journal of the ACM (JACM), Vol. 54, 3 (2007), 12.
11. P. Domingos and M. Richardson. 2001. Mining the network value of customers. In ACM SIGKDD .
12. Uriel Feige. 1998. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), Vol. 45, 4 (1998), 634--652.
13. Sainyam Galhotra, Akhil Arora, and Shourya Roy. 2016. Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. In Conference on Management of Data. ACM, 743--758.
14. Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011a. Celf
15. : optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference WWW. ACM, 47--48.
16. Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011b. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 211--220.
17. Kyomin Jung, Wooram Heo, and Wei Chen. 2012. Irie: Scalable and robust influence maximization in social networks. In Data Mining (ICDM), 2012 IEEE 12th International Conference on. IEEE, 918--923.
18. David Kempe, Jon M. Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In ACM SIGKDD . 137--146.
19. David Kempe, Jon M. Kleinberg, and Éva Tardos. 2005. Influential Nodes in a Diffusion Model for Social Networks. In ICALP. 1127--1138.
20. Sanjeev Khanna and Brendan Lucier. 2014. Influence maximization in undirected networks. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1482--1496.
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.
22. Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data .
23. Qiang Li, Wei Chen, Xiaoming Sun, and Jialin Zhang. 2017. Influence Maximization with $varepsilon$-Almost Submodular Threshold Functions. In NIPS . 3804--3814.
24. Yongwhan Lim, Asuman Ozdaglar, and Alexander Teytelboym. 2015. A simple model of cascades in networks.
25. Elchanan Mossel and Sébastien Roch. 2010. Submodularity of Influence in Social Networks: From Local to Global. SIAM J. Comput., Vol. 39, 6 (2010), 2176--2188.
26. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, Vol. 14, 1 (1978), 265--294.
27. Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2014. Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations.. In AAAI. 138--144.
28. M. Richardson and P. Domingos. 2002. Mining knowledge-sharing sites for viral marketing. In ACM SIGKDD . 61--70.
29. Grant Schoenebeck and Biaoshuai Tao. 2017. Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization. In International Conference on Web and Internet Economics. Springer, 368--382.
30. Grant Schoenebeck and Biaoshuai Tao. 2019. Beyond worst-case (in)approximability of nonsubmodular influence maximization. ACM Transactions on Computation Theory (TOCT), Vol. 11, 3 (2019), 12.
31. 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.
32. Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-optimal time complexity meets practical efficiency. In SIGMOD international conference on Management of data. ACM, 75--86.
33. Yaron Singer Thibaut Horel. 2016. Maximization of Approximately Submodular Functions. In NIPS .

Index Terms

• Networks

  • Network algorithms

    • Network economics

• Theory of computation

  • Computational complexity and cryptography

    • Problems, reductions and completeness

  • Design and analysis of algorithms

    • Approximation algorithms analysis

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Social networks