Journal of Soft Computing and Information Technology

Journal of Soft Computing and Information Technology

Identifying Key Influencers in Social Networks: A New Neighborhood-Based Method

Document Type : Persian Original Article

Authors
Yahya Dorostkar Navaei
Mohammad Hossein Rezvani
Amir Masoud Eftekhari Moghadam
Department of Computer and Information Technology Engineering, Qa.C., Islamic Azad University, Qazvin, Iran.
10.22034/jscit.2025.219059
Abstract
Abstract- One of the key challenges for social network designers is to identify influential users. Such users, by influencing other users, can play an important role in the rapid spread of information in the network. The goal here is influence maximization. This means finding the smallest number of users who have the greatest influence on other users. However, traditional metrics can only address the importance of the node in the network and ignore the importance of the node among its neighbors. An influential node found by traditional metrics is likely to be in the neighborhood of weakly connected nodes. This can slow down the spread of information, especially in advertising applications. To address this problem, in this paper, we present a new metric called neighborhood similarity. It determines the social importance of a user based on a combination of information about his/her neighbors. Due to the NP-hardness of the problem, we use our newly developed metric with a well-known metaheuristic method called Non-dominated Sorting Genetic Algorithm (NSGA-III). To reduce the cost, a centrality threshold is used so that only nodes with high connections act as influential users. We use sorting of users based on social similarity criteria to improve exploration and exploitation. Extensive tests are performed under different scenarios with a limited number of influential users on four well-known datasets from Caltech, Reed, Simmons, and Haverford. The results of the experiments show that our proposed neighborhood similarity metric can identify influential users better than traditional metrics. It improves the number of affected users by 9.5%, 16.5%, and 6.5%, respectively, in terms of centrality, closeness, and betweenness criteria.
Keywords
Social network
influence maximization
neighborhood similarity
metaheuristics
NSGA-III
[1] S. Yang, Q. Du, G. Zhu, J. Cao, L. Chen, W. Qin, and Y. Wang, “Balanced influence maximization in social networks based on deep reinforcement learning,” Neural Netw., vol. 169, pp. 334–351, Jan. 2024, doi: 10.1016/j.neunet.2023.10.030.
[2] A. Zareie and R. Sakellariou, “Fuzzy influence maximization in social networks,” ACM Trans. Web, vol. 18, no. 3, Art. no. 32:1–32:28, Aug. 2024, doi: 10.1145/3650179.
[3] R. Cantini, F. Marozzo, S. Mazza, D. Talia, and P. Trunfio, “A weighted artificial bee colony algorithm for influence maximization,” Online Soc. Netw. Media, vol. 26, Art. no. 100167, Sep. 2021, doi: 10.1016/j.osnem.2021.100167.
[4] T. K. Biswas, A. Abbasi, and R. K. Chakrabortty, “An MCDM integrated adaptive simulated annealing approach for influence maximization in social networks,” Inf. Sci., vol. 556, pp. 27–48, May 2021, doi: 10.1016/j.ins.2020.12.048.
[5] Z. Aghaee, M. M. Ghasemi, H. A. Beni, A. Bouyer, and A. Fatemi, “A survey on meta-heuristic algorithms for the influence maximization problem in the social networks,” Computing, vol. 103, no. 11, pp. 2437–2477, Sep. 2021, doi: 10.1007/s00607-021-00945-7.
[6] A. Karczmarczyk, J. Jankowski, and J. Wątrobski, “Multi-criteria seed selection for targeted influence maximization within social networks,” in Proc. Int. Conf. Comput. Sci. (ICCS), Cham, Switzerland: Springer, Jul. 2021, pp. 454–461, doi: 10.1007/978-3-030-69101-1_36.
[7] R. R. Singh, “Centrality measures: a tool to identify key actors in social networks,” in Principles of Social Networking: The New Horizon and Emerging Challenges, Cham, Switzerland: Springer, 2022, pp. 1–27, doi: 10.1007/978-3-030-91949-8_1.
[8] Y. D. Navaei, M. H. Rezvani, and A. M. E. Moghaddam, “A novel neighborhood-based importance measure for social network influence maximization using NSGA-III,” in Proc. 10th Int. Conf. Artif. Intell. Robot. (QICAR), Tehran, Iran, Feb. 2024, pp. 113–118, doi: 10.1109/QICAR57417.2024.1234567.
[9] H. Ishibuchi, R. Imada, Y. Setoguchi, and Y. Nojima, "Performance comparison of NSGA-II and NSGA-III on various many-objective test problems," in Proc. IEEE Congr. Evol. Comput. (CEC), Vancouver, BC, Canada, Jul. 2016, pp. 3045–3052, doi: 10.1109/CEC.2016.7744174.
[10] J. J. Lotf, M. A. Abdollahi Azgomi, and M. R. Ebrahimi Dishabi, "An improved influence maximization method for social networks based on genetic algorithm," Physica A, vol. 586, Art. no. 126480, Jan. 2022, doi: 10.1016/j.physa.2021.126480.
[11] E. A. Abbas and H. N. Nawaf, "Influence maximization based on a non-dominated sorting genetic algorithm," Karbala Int. J. Mod. Sci., vol. 7, no. 2, Art. no. 5, Jun. 2021, doi: 10.33640/2405-609X.2891.
[12] T. K. Biswas, A. Abbasi, and R. K. Chakrabortty, "An improved clustering-based multi-objective evolutionary algorithm for influence maximization under variable-length solutions," Knowl.-Based Syst., vol. 256, Art. no. 109856, Sep. 2022, doi: 10.1016/j.knosys.2022.109856.
[13] B. Chatterjee, T. Bhattacharyya, K. K. Ghosh, A. Chatterjee, and R. Sarkar, "A novel meta-heuristic approach for influence maximization in social networks," Expert Systems, vol. 40, no. 4, p. e12676, 2023, doi: 10.1111/exsy.12676.
[14] H. Li, R. Zhang, Z. Zhao, X. Liu, and Y. Yuan, "Identification of top-k influential nodes based on discrete crow search algorithm optimization for influence maximization," Applied Intelligence, vol. 51, no. 11, pp. 7749–7765, 2021, doi: 10.1007/s10489-021-02283-9.
[15] L. Han, K.-C. Li, A. Castiglione, J. Tang, H. Huang, and Q. Zhou, "A clique-based discrete bat algorithm for influence maximization in identifying top-k influential nodes of social networks," Soft Computing, vol. 25, pp. 8223–8240, 2021, doi: 10.1007/s00500-021-05749-7.
[16] D. Borkin, A. Némethová, G. Michaľčonok, and K. Maiorov, "Impact of data normalization on classification model accuracy," Research Papers Faculty of Materials Science and Technology Slovak University of Technology, vol. 27, no. 45, pp. 79–84, 2019, doi: 10.2478/rput-2019-0029.
[17] S. Peng, Y. Zhou, L. Cao, S. Yu, J. Niu, and W. Jia, "Influence analysis in social networks: A survey," Journal of Network and Computer Applications, vol. 106, pp. 17–32, Jan. 2018, doi: 10.1016/j.jnca.2018.01.005.
[18] A. L. Traud, E. D. Kelsic, P. J. Mucha, and M. A. Porter, "Comparing community structure to characteristics in online collegiate social networks," SIAM Review, vol. 53, no. 3, pp. 526–543, Sep. 2011, doi: 10.1137/080734315.
[19] 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, Jan. 2023, doi: 10.1109/MCI.2022.3222050.
[20] A. Gupta, Y.-S. Ong, and L. Feng, "Multifactorial evolution: Toward evolutionary multitasking," IEEE Transactions on Evolutionary Computation, vol. 20, no. 3, pp. 343–357, Jun. 2016, doi: 10.1109/TEVC.2015.2458037.
[21] K. K. Bali, Y.-S. Ong, A. Gupta, and P. S. Tan, "Multifactorial evolutionary algorithm with online transfer parameter estimation: MFEA-II," IEEE Trans. Evol. Comput., vol. 24, no. 1, pp. 69–83, Feb. 2020, doi: 10.1109/TEVC.2019.2906927.
[22] R.-T. Liaw and C.-K. Ting, "Evolutionary manytasking optimization based on symbiosis in biocoenosis," in Proc. AAAI Conf. Artif. Intell., vol. 33, no. 1, pp. 4295–4303, Jan. 2019, doi: 10.1609/aaai.v33i01.33014295.
[23] L. Feng, L. Zhou, J. Zhong, A. Gupta, Y.-S. Ong, K. C. Tan, and A. K. Qin, "Evolutionary multitasking via explicit autoencoding," IEEE Trans. Cybern., vol. 49, no. 9, pp. 3457–3470, Sep. 2019, doi: 10.1109/TCYB.2019.2902865.
[24] L. Page, S. Brin, R. Motwani, and T. Winograd, "The PageRank citation ranking: Bringing order to the web," Stanford InfoLab, Tech. Rep. SIDL-WP-1999-0120, Jan. 1998. [Online]. Available: https://ilpubs.stanford.edu/422/
Journal of Soft Computing and Information Technology
Volume 14, Issue 1
Spring - June
Spring 2025
Pages 11-26