Volume 21, Issue 4 (3-2025)
JSDP 2025, 21(4): 29-48 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Abdolrazzagh-Nezhad M, Kherad M. Discovering Influential Nodes in Social Networks based on modified independent cascade model and Fuzzy Multi-Objective Genetic Algorithm. JSDP 2025; 21 (4) : 3
URL: http://jsdp.rcisp.ac.ir/article-1-1380-en.html
URL: http://jsdp.rcisp.ac.ir/article-1-1380-en.html
Bozorgmehr University of Qaenat
Abstract: (318 Views)
In recent years, social networks have become an integral part of people's lives and play a significant role in the real world. The primary aim of influence maximization problem is finding a set of nodes in the network which can maximize the influence if the diffusion process starts from them. Therefore, the problem’s goal is to find influential people in large scale real social networks. The penetration phenomenon is carried out according to an influence model in the network. Two independent cascade and linear threshold influence models, the most common of which is the independent cascade model, are utilized for broadcasting in the network. Theoreticaly, optimizing the selection influential nodes problem is NP-hard in both models.
The problem will start by considering the social network’s graph, a specific influence model and a given number k. The problem’s goal is to select k nodes (users) from the graph (network) as influential nodes, so that the number of active nodes is maximized at the end of the diffusion process. Due to the influence maximization problem and finding influential people is an NP-hard optimization problem in the social network, meta-heuristic algorithms can be used to solve the problem. With regard to the privous researches, there is just one objective function as the problem’s goal and it is maximizing the number of effective nodes of the diffusion model. While other objective functions such as maximizing the number of effective nodes in the diffusion model and minimizing the budget value k (the number of initial nodes as seed) are not considered, minimizing the time required for effective diffusion can be achieved by having k initial nodes. Although various models for the problem and various optimization algorithms have been presented to discover influential nodes in social networks, paying attention to the multi-objective nature of the problem and improving the performance of the proposed optimization algorithms are a serious research challenge in this field.
In this paper. A fuzzy version of the NSGA-II as a multi-objective genetic algorithm, whose mutation and crossover rates are adjusted by Fuzzy Inference System, is utilized to simultaneously optimize the three objectives of maximizing the number of effective nodes, minimizing the number of initial nodes and minimizing the required diffusion time. In the proposed method, the Expected Diffusion Value (EDV) of the diffusion model is replaced instead the simulation of the independent cascade diffusion model with heavy calculations to calculate the diffusion spread (the number of effective nodes of the diffusion model). Therefore, the EDV function is satisfied as the thied objective (minimizing the required diffusion time). The second objective function can also be converted into a maximization function by considering N-k nodes, where k is the number of selected initial nodesand N is the total graph nodes.
The decimal numerical coding with fixed length is used in the proposed method. Based on the coding, each chromosome has k genes in the search space. The integer part of each gene is the selected node number. The decimal part is also used to determine whether that initial node exists or not. In the maximizing influence process using the fuzzy NSGA-II algorithm, the solution space (chromosomes) consists of k number of initial nodes, which should be encoded into the fuzzy NSGA-II comprehensible space. Also, a Fuzzy Inference System is proposed to adjust the mutation and recombination rates for filling up a serious challenge of genetic algorithms. In the fuzzy system, NF and FitBest are considered as two input variables, and Pm (mutation rate) and Pc (crossover rate) are returned as outputs NF is the number of chromosomes in the first frontier (F1) of the multi-objective genetic algorithm and FitBest is the average of the normalized objective functions for the chromosomes in F1.
To analysis the efficiency of the proposed method, the obtained exprimental results have been compared with conventional maximizing influence methods, i.e., degree centrality, distance centrality, closeness centerality, betweenness, eigenvector and page rank methods, non-fuzzy version of NSGA-II, the latest methods presented for maximizing penetration based on multi-objective meta-heuristic algorithms, i.e. µGP multi-objective evolutionary algorithm, multi-objective crow search algorithm (MOCSA), greedy randomized adaptive search process algorithm (GRASP) and the Multi-Transformation Evolutionary Framework (MTEF) on five benchmark graph datasets Arenasjazz, Canetscience, EgoFacebook, Higgs-Reply and Slashdot. This comparison is based on four criteria: EDV, cost (the number of nodes selected as seed), the influence expansion criterion σ(s), i.e. the number of active nodes with the independent cascade (IC) propagation model, and the execution time of the method in seconds. The obtained results show the superiority of the proposed method over the other methods.
The problem will start by considering the social network’s graph, a specific influence model and a given number k. The problem’s goal is to select k nodes (users) from the graph (network) as influential nodes, so that the number of active nodes is maximized at the end of the diffusion process. Due to the influence maximization problem and finding influential people is an NP-hard optimization problem in the social network, meta-heuristic algorithms can be used to solve the problem. With regard to the privous researches, there is just one objective function as the problem’s goal and it is maximizing the number of effective nodes of the diffusion model. While other objective functions such as maximizing the number of effective nodes in the diffusion model and minimizing the budget value k (the number of initial nodes as seed) are not considered, minimizing the time required for effective diffusion can be achieved by having k initial nodes. Although various models for the problem and various optimization algorithms have been presented to discover influential nodes in social networks, paying attention to the multi-objective nature of the problem and improving the performance of the proposed optimization algorithms are a serious research challenge in this field.
In this paper. A fuzzy version of the NSGA-II as a multi-objective genetic algorithm, whose mutation and crossover rates are adjusted by Fuzzy Inference System, is utilized to simultaneously optimize the three objectives of maximizing the number of effective nodes, minimizing the number of initial nodes and minimizing the required diffusion time. In the proposed method, the Expected Diffusion Value (EDV) of the diffusion model is replaced instead the simulation of the independent cascade diffusion model with heavy calculations to calculate the diffusion spread (the number of effective nodes of the diffusion model). Therefore, the EDV function is satisfied as the thied objective (minimizing the required diffusion time). The second objective function can also be converted into a maximization function by considering N-k nodes, where k is the number of selected initial nodesand N is the total graph nodes.
The decimal numerical coding with fixed length is used in the proposed method. Based on the coding, each chromosome has k genes in the search space. The integer part of each gene is the selected node number. The decimal part is also used to determine whether that initial node exists or not. In the maximizing influence process using the fuzzy NSGA-II algorithm, the solution space (chromosomes) consists of k number of initial nodes, which should be encoded into the fuzzy NSGA-II comprehensible space. Also, a Fuzzy Inference System is proposed to adjust the mutation and recombination rates for filling up a serious challenge of genetic algorithms. In the fuzzy system, NF and FitBest are considered as two input variables, and Pm (mutation rate) and Pc (crossover rate) are returned as outputs NF is the number of chromosomes in the first frontier (F1) of the multi-objective genetic algorithm and FitBest is the average of the normalized objective functions for the chromosomes in F1.
To analysis the efficiency of the proposed method, the obtained exprimental results have been compared with conventional maximizing influence methods, i.e., degree centrality, distance centrality, closeness centerality, betweenness, eigenvector and page rank methods, non-fuzzy version of NSGA-II, the latest methods presented for maximizing penetration based on multi-objective meta-heuristic algorithms, i.e. µGP multi-objective evolutionary algorithm, multi-objective crow search algorithm (MOCSA), greedy randomized adaptive search process algorithm (GRASP) and the Multi-Transformation Evolutionary Framework (MTEF) on five benchmark graph datasets Arenasjazz, Canetscience, EgoFacebook, Higgs-Reply and Slashdot. This comparison is based on four criteria: EDV, cost (the number of nodes selected as seed), the influence expansion criterion σ(s), i.e. the number of active nodes with the independent cascade (IC) propagation model, and the execution time of the method in seconds. The obtained results show the superiority of the proposed method over the other methods.
Article number: 3
Keywords: Influence Maximization Problem, Social Network, Genetic Algorithm with Non-Dominant Sorting, Fuzzy System
Type of Study: Research |
Subject:
Paper
Received: 2023/05/11 | Accepted: 2024/12/4 | Published: 2025/04/2 | ePublished: 2025/04/2
Received: 2023/05/11 | Accepted: 2024/12/4 | Published: 2025/04/2 | ePublished: 2025/04/2
References
1. J. Zhou, Y. Zhang, and J. Cheng, "Preference-based mining of top-K influential nodes in social networks," Future Generation Computer Systems, vol. 31, pp. 40-47, 2014. [DOI:10.1016/j.future.2012.06.011]
2. e. Mazaheri, a. Talebpour, and a. Rzaian, Identification Power Nodes in Social Networks Using Data Mining (no. 2). Tarbiat Modares University, 2021, pp. 161-182.
3. C. Zhou, P. Zhang, J. Guo, X. Zhu, and L. Guo, "Ublf: An upper bound based approach to discover influential nodes in social networks," in Data Mining (ICDM), 2013 IEEE 13th International Conference on, 2013, pp. 907-916: IEEE. [DOI:10.1109/ICDM.2013.55] []
4. J. Scripps, "Discovering Influential Nodes in Social Networks through Community Finding," in WEBIST, 2013, pp. 403-412. [DOI:10.5220/0004350704030412]
5. F. sharifzadeh, S. Kafi, and M. barari, "Providing a new method to identify active and influential nodes in social networks," presented at the National Conference of Computer Engineering and Information Technology Management, Tehran, 2004. Available: https://civilica.com/doc/282629
6. M. 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, 2002, pp. 61-70: ACM. [DOI:10.1145/775047.775057] [PMID]
7. D. Kempe, J. M. Kleinberg, and É. Tardos, "Maximizing the Spread of Influence through a Social Network," Theory of computing, vol. 11, no. 4, pp. 105-147, 2015. [DOI:10.4086/toc.2015.v011a004]
8. E. Mossel and S. Roch, "On the submodularity of influence in social networks," in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 128-134: ACM. [DOI:10.1145/1250790.1250811]
9. m. Abbaspour orangi and A. Hashemi golpayegani, "Identifying Influential Nodes to Diffuse the Trusting Behavior in Social Networks," (in eng), Signal and Data Processing, Research vol. 18, no. 2, pp. 57-74, 2021. [DOI:10.52547/jsdp.18.2.57]
10. R. A. Formato, "Central force optimization: A new deterministic gradient-like optimization metaheuristic," Opsearch, vol. 46, no. 1, pp. 25-51, 2009. [DOI:10.1007/s12597-009-0003-4]
11. K. Deb and H. Jain, "An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints," IEEE Trans. Evolutionary Computation, vol. 18, no. 4, pp. 577-601, 2014. [DOI:10.1109/TEVC.2013.2281535]
12. P. Wang and R. Zhang, "A Multi-Objective Crow Search Algorithm for Influence Maximization in Social Networks," Electronics, vol. 12, no. 8, p. 1790, 2023. [DOI:10.3390/electronics12081790]
13. I. Lozano-Osorio, J. Sanchez-Oro, A. Duarte, and Ó. Cordón, "A quick GRASP-based method for influence maximization in social networks," Journal of Ambient Intelligence and Humanized Computing, vol. 14, no. 4, pp. 3767-3779, 2023. [DOI:10.1007/s12652-021-03510-4]
14. C. Wang, J. Zhao, L. Li, L. Jiao, J. Liu, and K. Wu, "A multi-transformation evolutionary framework for influence maximization in social networks," IEEE Computational Intelligence Magazine, vol. 18, no. 1, pp. 52-67, 2023. [DOI:10.1109/MCI.2022.3222050]
15. T. K. Biswas, A. Abbasi, and R. K. Chakrabortty, "An improved clustering based multi-objective evolutionary algorithm for influence maximization under variable-length solutions," Knowledge-Based Systems, vol. 256, p. 109856, 2022. [DOI:10.1016/j.knosys.2022.109856]
16. R. Olivares, F. Muñoz, and F. Riquelme, "A multi-objective linear threshold influence spread model solved by swarm intelligence-based methods," Knowledge-Based Systems, vol. 212, p. 106623, 2021. [DOI:10.1016/j.knosys.2020.106623]
17. A. Sheikhahmadi and A. Zareie, "Identifying influential spreaders using multi-objective artificial bee colony optimization," Applied Soft Computing, vol. 94, p. 106436, 2020. [DOI:10.1016/j.asoc.2020.106436]
18. A. Mohammadi and M. Saraee, "Finding influential users for different time bounds in social networks using multi-objective optimization," Swarm and evolutionary computation, vol. 40, pp. 158-165, 2018. [DOI:10.1016/j.swevo.2018.02.003]
19. J. Tang, R. Zhang, P. Wang, Z. Zhao, L. Fan, and X. Liu, "A discrete shuffled frog-leaping algorithm to identify influential nodes for influence maximization in social networks," Knowledge-Based Systems, vol. 187, p. 104833, 2020. [DOI:10.1016/j.knosys.2019.07.004]
20. D. Bucur, G. Iacca, A. Marcelli, G. Squillero, and A. Tonda, "Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks," in European Conference on the Applications of Evolutionary Computation, 2017, pp. 221-233: Springer. [DOI:10.1007/978-3-319-55849-3_15]
21. M. Gong, J. Yan, B. Shen, L. Ma, and Q. Cai, "Influence maximization in social networks based on discrete particle swarm optimization," Information Sciences, vol. 367, pp. 600-614, 2016. [DOI:10.1016/j.ins.2016.07.012]
22. D. Li, C. Wang, S. Zhang, G. Zhou, D. Chu, and C. Wu, "Positive influence maximization in signed social networks based on simulated annealing," Neurocomputing, 2017. [DOI:10.1016/j.neucom.2017.03.003]
23. K. Zhang, H. Du, and M. W. Feldman, "Maximizing influence in a social network: Improved results using a genetic algorithm," Physica A: Statistical Mechanics and its Applications, vol. 478, pp. 20-30, 2017. [DOI:10.1016/j.physa.2017.02.067]
24. M. 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, 2016, pp. 1189-1196: IEEE. [DOI:10.1109/ASONAM.2016.7752390]
25. Q. Jiang, G. Song, G. Cong, Y. Wang, W. Si, and K. Xie, "Simulated Annealing Based Influence Maximization in Social Networks," in AAAI, 2011, vol. 11, pp. 127-132. [DOI:10.1609/aaai.v25i1.7838]
26. D. Bucur and G. Iacca, "Influence maximization in social networks with genetic algorithms," in European Conference on the Applications of Evolutionary Computation, 2016, pp. 379-392: Springer. [DOI:10.1007/978-3-319-31204-0_25]
27. Y. Gui-sheng, W. Ji-jie, D. Hong-bin, and L. Jia, "Intelligent Viral Marketing algorithm over online social network," in Networking and Distributed Computing (ICNDC), 2011 Second International Conference on, 2011, pp. 319-323: IEEE. [DOI:10.1109/ICNDC.2011.69]
28. C.-W. Tsai, Y.-C. Yang, and M.-C. Chiang, "A Genetic NewGreedy Algorithm for Influence Maximization in Social Network," in Systems, Man, and Cybernetics (SMC), 2015 IEEE International Conference on, 2015, pp. 2549-2554: IEEE. [DOI:10.1109/SMC.2015.446]
29. J. Zhou et al., "Graph neural networks: A review of methods and applications," AI open, vol. 1, pp. 57-81, 2020. [DOI:10.1016/j.aiopen.2021.01.001]
30. W. Liu, S. Wang, and J. Ding, "Influence Maximization Based on Adaptive Graph Convolution Neural Network in Social Networks," Electronics, vol. 13, no. 16, p. 3110, 2024. [DOI:10.3390/electronics13163110]
31. X. Zhang and W. Xie, "Social network influence maximization based on graph attention mechanisms," in 2024 9th International Conference on Electronic Technology and Information Science (ICETIS), 2024, pp. 543-548: IEEE. [DOI:10.1109/ICETIS61828.2024.10593670]
32. Y. Wang, P. Li, and W. Huang, "Influence Maximization With Graph Neural Network in Multi-Feature Social Network," in 2022 IEEE 24th Int Conf on High Performance Computing & Communications; 8th Int Conf on Data Science & Systems; 20th Int Conf on Smart City; 8th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys), 2022, pp. 1751-1756: IEEE. [DOI:10.1109/HPCC-DSS-SmartCity-DependSys57074.2022.00264]
33. E. Yanchenko, T. Murata, and P. Holme, "Influence maximization on temporal networks: a review," Applied Network Science, vol. 9, no. 1, p. 16, 2024. [DOI:10.1007/s41109-024-00625-3]
34. C. C. Aggarwal, "An introduction to social network data analytics," Social network data analytics, pp. 1-15, 2011. [DOI:10.1007/978-1-4419-8462-3_1]
35. M. E. Newman, "Spread of epidemic disease on networks," Physical review E, vol. 66, no. 1, p. 016128, 2002. [DOI:10.1103/PhysRevE.66.016128] [PMID]
36. D. 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, 2003, pp. 137-146: ACM. [DOI:10.1145/956750.956769]
37. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE transactions on evolutionary computation, vol. 6, no. 2, pp. 182-197, 2002. [DOI:10.1109/4235.996017]
38. A. P. Engelbrecht, Computational intelligence: an introduction., 2 ed. England: John Wiley & Sons, 2007, p. 597. [DOI:10.1002/9780470512517]
39. E. Mamdani and S. Assilian, "An experiment in linguistic synthesis with a fuzzy logic controller," International journal of human-computer studies, vol. 51, no. 2, pp. 135-147, 1999. [DOI:10.1006/ijhc.1973.0303]
40. M. De Domenico, A. Lima, P. Mougel, and M. Musolesi, "The anatomy of a scientific rumor," Scientific reports, vol. 3, no. 1, p. 2980, 2013. [DOI:10.1038/srep02980] [PMID] []
41. J. Kunegis, A. Lommatzsch, and C. Bauckhage, "The slashdot zoo: mining a social network with negative edges," in Proceedings of the 18th international conference on World wide web, 2009, pp. 741-750. [DOI:10.1145/1526709.1526809]
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
