A robust optimization model for influence maximization in social networks with heterogeneous nodes
Tóm tắt
Influence maximization is the problem of trying to maximize the number of influenced nodes by selecting optimal seed nodes, given that influencing these nodes is costly. Due to the probabilistic nature of the problem, existing approaches deal with the concept of the expected number of nodes. In the current research, a scenario-based robust optimization approach is taken to finding the most influential nodes. The proposed robust optimization model maximizes the number of infected nodes in the last step of diffusion while minimizing the number of seed nodes. Nodes, however, are treated as heterogeneous with regard to their propensity to pass messages along; or as having varying activation thresholds. Experiments are performed on a real text-messaging social network. The model developed here significantly outperforms some of the well-known existing heuristic approaches which are proposed in previous works.
Tài liệu tham khảo
Jackson, M.O.: Social and Economic Networks. Princeton University Press, Princeton (2010)
Kross, E., Chandhok, S.: How do online social networks influence people’s emotional lives? In: Sydney Symposium of Social Psychology. Applications of Social Psychology, 2020
Kermani, M.A.M.A., Sani, S.A., Zand, H.: Resident’s Alzheimer disease and social networks within a nursing home. In: International Conference on Complex Networks and their Applications, Springer (2020)
Agha Mohammad Ali Kermani, M., Aliahmadi, A., Hanneman, R.: Optimizing the choice of influential nodes for diffusion on a social network. Int. J. Commun. Syst. 29, 1235–1250 (2015)
Lu, F., et al.: Scalable influence maximization under independent cascade model. J. Netw. Comput. Appl. 86, 15–23 (2017)
Bindu, P.V., Thilagam, P.S.: Mining social networks for anomalies: methods and challenges. J. Netw. Comput. Appl. 68, 213–229 (2016)
Hegeman, J., et al.: Sponsored advertisement ranking and pricing in a social networking system, Google Patents (2020)
Kempe, D., Kleinberg, J., 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, ACM (2003)
Zhao, J., et al.: Competitive seeds-selection in complex networks. Physica A Stat. Mech. Appl. 467, 240–248 (2017)
Wang, Y., et al.: Real-time influence maximization on dynamic social streams. Proc. VLDB Endow. 10(7), 805–816 (2017)
Ju, W., et al.: A new algorithm for positive influence maximization in signed networks. Inf. Sci. 512, 1571–1591 (2020)
Yan, Q., et al.: Group-level influence maximization with budget constraint. In: International Conference on Database Systems for Advanced Applications, Springer (2017)
Agha Mohammad Ali Kermani, M., Aliahmadi, A., Hanneman, R.: Optimizing the choice of influential nodes for diffusion on a social network. Int. J. Commun. Syst. 29(7), 1235–1250 (2016)
Kermani, M.A.M.A., et al.: A novel game theoretic approach for modeling competitive information diffusion in social networks with heterogeneous nodes. Physica A Stat. Mech. Appl. 466, 570–582 (2017)
Kermani, M.A.M.A., Ghesmati, R., Jalayer, M.: Opinion-aware influence maximization: how to maximize a favorite opinion in a social network? Adv. Complex Syst. 21(06n07), 1850022 (2018)
He, X., Kempe, D.: Robust influence maximization. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 885–894. ACM, San Francisco (2016)
He, X., Kempe, D.: Stability and robustness in influence maximization. ACM Trans. Knowl. Discov. Data (TKDD) 12(6), 1–34 (2018)
Chen, W., et al.: Robust influence maximization. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 795–804. ACM, San Francisco (2016)
Jung, K., Heo, W., Chen, W.: Irie: scalable and robust influence maximization in social networks. In: Data Mining (ICDM), 2012 IEEE 12th International Conference on, IEEE (2012)
Marotta, A., et al.: A fast robust optimization-based heuristic for the deployment of green virtual network functions. J. Netw. Comput. Appl. 95, 42–53 (2017)
Arminen, I.: Mobile communication society? Acta Sociol 50, 431–437 (2007)
Campbell, S.W., Russo, T.C.: The cocial construction of mobile telephony: an application of the social influence model to perceptions and uses of mobile phones within personal communication networks. Commun. Monogr. 70(4), 317–334 (2003)
Alon, N., et al.: A note on competitive diffusion through social networks. Inf. Process. Lett. 110(6), 221–225 (2010)
Small, L., Mason, O.: Nash Equilibria for competitive information diffusion on trees. Inf. Process. Lett. 113(7), 217–219 (2013)
Shang, J., et al.: CoFIM: a community-based framework for influence maximization on large-scale networks. Knowl.-Based Syst. 117, 88–100 (2017)
Jalayer, M., Azheian, M., Kermani, M.A.M.A.: A hybrid algorithm based on community detection and multi attribute decision making for influence maximization. Comput. Ind. Eng. 120, 234–250 (2018)
Lu, Z., et al.: The complexity of influence maximization problem in the deterministic linear threshold model. J. Comb. Optim. 24(3), 374–378 (2012)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM (2009)
Wang, Y., et al.: Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM (2010)
Chen, W., Wang, C., Wang, Y.: 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 (2010)
Kimura, M., et al.: Extracting influential nodes on a social network for information diffusion. Data Min. Knowl. Discov. 20(1), 70–97 (2010)
Wang, C., et al.: A global optimization algorithm for target set selection problems. Inf. Sci. 267, 101–118 (2013)
Leskovec, J., et al.: Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM (2007)
Yang, W.-S., et al.: Application of the ant colony optimization algorithm to the influence-maximization problem. Int. J. Swarm Intell. Evol. Comput. 1(1), 1–8 (2012)
Bucur, D., Iacca, G.: Influence maximization in social networks with genetic algorithms. In: EvoApplications, No 1 (2016)
Jiang, Q., et al.: Simulated annealing based influence maximization in social networks. In: AAAI (2011)
Liu, S.-J., Chen, C.-Y., Tsai, C.-W.: An effective simulated annealing for influence maximization problem of online social networks. Procedia Comput. Sci. 113, 478–483 (2017)
Gong, M., et al.: Influence maximization in social networks based on discrete particle swarm optimization. Inf. Sci. 367, 600–614 (2016)
Tang, J., et al.: Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization. Physica A Stat. Mech. Appl. 513, 477–496 (2019)
Gandomi, A.H., Yang, X.-S., Alavi, A.H.: Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems. Eng. Comput. 29, 17–35 (2013)
He, Q., et al.: Heuristics-based influence maximization for opinion formation in social networks. Appl. Soft Comput. 66, 360–369 (2018)
Samadi, M., et al.: Seed activation scheduling for influence maximization in social networks. Omega 77, 96–114 (2018)
Tanınmış, K., Aras, N., Altınel, I.K.: Influence maximization with deactivation in social networks. Eur. J. Oper. Res. 278(1), 105–119 (2019)
Güney, E.: An efficient linear programming based method for the influence maximization problem in social networks. Inf. Sci. 503, 589–605 (2019)
He, X., Kempe, D.: Stability of influence maximization. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2014)
Kalimeris, D., Kaplun, G., Singer, Y.: Robust influence maximization for hyperparametric models. arXiv preprint arXiv:1903.03746 (2019)
Wu, H.-H., Küçükyavuz, S.: A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3), 563–595 (2018)
Pishvaee, M., Razmi, J., Torabi, S.A.: Robust possibilistic programming for socially responsible supply chain network design: a new approach. Fuzzy Sets Syst. 206, 1–20 (2012)
Soyster, A.L.: Technical note—convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5), 1154–1157 (1973)
Mulvey, J.M., Vanderbei, R.J., Zenios, S.A.: Robust optimization of large-scale systems. Oper. Res. 43(2), 264–281 (1995)
Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1), 1–13 (1999)
Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769–805 (1998)
Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88(3), 411–424 (2000)
El Ghaoui, L., Oustry, F., Lebret, H.: Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9(1), 33–52 (1998)
Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1), 49–71 (2003)
Yu, C.-S., Li, H.-L.: A robust optimization model for stochastic logistic problems. Int. J. Prod. Econ. 64(1–3), 385–397 (2000)
Leung, S.C., et al.: A robust optimization model for multi-site production planning problem in an uncertain environment. Eur. J. Oper. Res. 181(1), 224–238 (2007)
Chircop, K., Zammit-Mangion, D.: On-constraint based methods for the generation of Pareto frontiers. J. Mech. Eng. Autom. 3(5), 279–289 (2013)
Kermani, M., et al.: A note on predicting how people interact in attributed social networks. Int. J. Curr. Life Sci. (IJCLS) 4(6), 2510–2514 (2014)
Mesgari, I., et al.: Identifying key nodes in social networks using multi-criteria decision-making tools. In: Mathematical technology of networks, pp. 137–150. Springer, Berlin (2015)
Inderbitzen, H.M., Foster, S.L.: The teenage inventory of social skills: development, reliability, and validity. Psychol. Assess. 4(4), 451 (1992)
Kermani, M.A.M.A., et al.: Introducing a procedure for developing a novel centrality measure (Sociability Centrality) for social networks using TOPSIS method and genetic algorithm. Comput. Hum. Behav. 56, 295–305 (2016)
Cordeau, J.-F.: A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3), 573–586 (2006)
Reinhardt, L.B., Pisinger, D.: A branch and cut algorithm for the container shipping network design problem. Flex. Serv. Manuf. J. 24(3), 349–374 (2012)
Erkol, Ş, Castellano, C., Radicchi, F.: Systematic comparison between methods for the detection of influential spreaders in complex networks. Sci. Rep. 9(1), 1–11 (2019)
Banerjee, A., et al.: The diffusion of microfinance. Science 341(6144), 1236498 (2013)
Hu, J., et al.: A modified weighted TOPSIS to identify influential nodes in complex networks. Physica A Stat. Mech. Appl. 444, 73–85 (2016)
Fox, W., Everton, S.: Mathematical modeling in social network analysis: using TOPSIS to find node influences in a social network. J. Math. Syst. Sci. 3(10), 531–541 (2013)
Du, Y., et al.: A new method of identifying influential nodes in complex networks based on TOPSIS. Physica A Stat. Mech. Appl. 399, 57–69 (2014)