Proximity-Aware Degree-Based Heuristics for the Influence Maximization Problem

Document Type : Semantic Technology-Kahani

Authors

Maryam Adineh

Mostafa Nouri Baygi

Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.

10.22067/cke.2022.63265.0

Abstract

The problem of influence maximization is selecting the most influential individuals in a social network. With the popularity of social network sites and the development of viral marketing, the importance of the problem has increased. The influence maximization problem is NP-hard, and therefore, there will not exist any polynomial-time algorithm to solve the problem unless P = NP. Many heuristics are proposed for finding a nearly good solution in a shorter time. This study proposes two heuristic algorithms for finding good solutions. The heuristics are based on two ideas: 1) vertices of high degree have more influence in the network, and 2) nearby vertices influence on almost analogous sets of vertices. We evaluate our algorithms on several well-known data sets and show that our heuristics achieve better results (up to 15% in the influence spread) for this problem in a shorter time (up to 85% improvement in the running time).

Keywords

Degree centrality

Heuristic algorithm

Independent cascade model

Influence maximization

Subjects

• Computer Science

---

References

1. Domingos and M. Richardson, "Mining the network value of customers", in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 57–66, ACM, (2001).
2. Richardson and P. Domingos, "Mining knowledge-sharing sites for viral marketing", in Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 61–70, ACM, (2002).
3. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network", in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137–146, ACM, (2003).
4. Adineh and M. Nouri-Baygi, "Maximum degree based heuristics for influence maximization", in 2018 8th International Conference on Computer and Knowledge Engineering (ICCKE), pp. 256–261, Oct (2018).
5. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, "Cost-effective outbreak detection in networks", in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 420–429, ACM, (2007).
6. Chen, Y. Wang, and S. Yang, "Efficient influence maximization in social networks", in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 199–208, ACM, (2009).
7. Borgs, M. Brautbar, J. Chayes, and B. Lucier, "Maximizing social influence in nearly optimal time", in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 946– 957, SIAM, (2014).
8. Tang, X. Xiao, and Y. Shi, "Influence maximization: Near-optimal time complexity meets practical efficiency", in Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 75–86, ACM, (2014).
9. Tang, Y. Shi, and X. Xiao, "Influence maximization in near-linear time: A martingale approach", in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1539– 1554, ACM, (2015).
10. Bucur and G. Iacca, "Influence maximization in social networks with genetic algorithms", in European Conference on the Applications of Evolutionary Computation, pp. 379–392, Springer, (2016).
11. Krömer and J. Nowaková, "Guided genetic algorithm for the influence maximization problem", in International Computing and Combinatorics Conference, pp. 630–641, Springer, (2017).
12. Weskida and R. Michalski, "Evolutionary algorithm for seed selection in social influence process", in Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on, pp. 1189–1196, IEEE, (2016).
13. -C. Chen, W.-Y. Zhu, W.-C. Peng, W.-C. Lee, and S.-Y. Lee, "Cim: Community-based influence maximization in social networks", ACM Transactions on Intelligent Systems and Technology (TIST), vol. 5, No. 2, p. 25, (2014).
14. Manaskasemsak, N. Dejkajonwuth, and A. Rungsawang, "Community centrality-based greedy approach for identifying top-k influencers in social networks", in International Conference on ContextAware Systems and Applications, pp. 141–150, Springer, (2015).
15. Song, X. Zhou, Y. Wang, and K. Xie, "Influence maximization on large-scale mobile social network: a divide-and-conquer method", IEEE Transactions on Parallel and Distributed Systems, vol. 26, No. 5, pp. 1379–1392, (2015).
16. Kempe, J. Kleinberg, and E. Tardos, "Maximizing the spread of influence through a social network", Theory of Computing, vol. 11, no. 4, pp. 105–147, 2015.
17. Leskovec and A. Krevl, "SNAP Datasets: Stanford large network dataset collection", http://snap. stanford.edu/data, (2014).