P-centrality: An Improvement for Information Diffusion Maximization in Weighted Social Networks

Document Type : Special Issue

Authors

Najva Hafizi ¹

Mojtaba Mazoochi ²

Ali moeini ¹

Leila Rabiei ³

Seyed Mohammadreza Ghaffariannia ¹

Farzaneh Rahmani ³

¹ Department of Algorithms and Computation, Faculty of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran.

² ICT Research Institute (ITRC), Tehran, Iran.

³ Innovation and Development Center of Artificial Intelligence, ICT Research Institute (ITRC), Tehran, Iran.

10.22067/cke.2023.74745.1047

Abstract

Online social networks (OSNs) such as Facebook, Twitter, Instagram, etc. have attracted many users all around the world. Based on the centrality concept, many methods are proposed in order to find influential users in an online social network. However, the performance of these methods is not always acceptable. In this paper, we proposed a new improvement on centrality measures called P-centrality measure in which the effects of node predecessors are considered. In an extended measure called EP-centrality, the effect of the preceding predecessors of node predecessors are also considered. We also defined a combination of two centrality measures called NodePower (NP) to improve the effectiveness of the proposed metrics. The performance of utilizing our proposed centrality metrics in comparison with the conventional centrality measures is evaluated by Susceptible-Infected-Recovered (SIR) model. The results show that the proposed metrics display better performance finding influential users than normal ones due to Kendall’s τ coefficient metric.

Keywords

Online Social Networks

Centrality measures

Influential users

Susceptible-Infected-Recovered model

Subjects

• Special Issues

---

References

• Kempe, David, Jon Kleinberg, and Éva 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. 4 137-146. 2003.
• Al-Garadi, Mohammed Ali, Kasturi Dewi Varathan, Sri Devi Ravana, Ejaz Ahmed, Ghulam Mujtaba, Muhammad Usman Shahid Khan, and Samee U. Khan. ”Analysis of online social network connections for identification of influential users: Survey and open research issues.” ACM Computing Surveys (CSUR) 51, no. 1 (2018): 1-37.
• Freeman, Linton C. ”Centrality in social networks conceptual clarification.” Social networks 1, no. 3 (1978): 215-239.
• Kitsak, Maksim, Lazaros K. Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H. Eugene Stanley, and Hernán A. Makse. ”Identification of influential spreaders in complex networks.” Nature physics 6, no. 11 (2010): 888-893. 11
• Wei, Daijun, Xinyang Deng, Xiaoge Zhang, Yong Deng, and Sankaran Mahadevan. ”Identifying influential nodes in weighted networks based on evidence theory.” Physica A: Statistical Mechanics and its Applications 392, no. 10 (2013): 2564-2575.
• Freeman, Linton C. ”A set of measures of centrality based on betweenness.” Sociometry (1977): 35-41.
• Brandes, Ulrik. ”A faster algorithm for betweenness centrality.” Journal of mathematical sociology 25, no. 2 (2001): 163-177.
• Estrada, Ernesto. The structure of complex networks: theory and applications. Oxford University Press, 2012.
• Sabidussi, Gert. ”The centrality index of a graph.” Psychometrika 31, no. 4 (1966): 581-603.
• Chen, Duanbing, Linyuan Lü, Ming-Sheng Shang, Yi-Cheng Zhang, and Tao Zhou. ”Identifying influential nodes in complex networks.” Physica a: Statistical mechanics and its applications 391, no. 4 (2012): 1777-1787.
• Brin, Sergey, and Lawrence Page. ”The anatomy of a large-scale hypertextual web search engine.” Computer networks and ISDN systems 30, no. 1-7 (1998): 107-117.
• Al-Garadi, Mohammed Ali, Kasturi Dewi Varathan, Sri Devi Ravana, Ejaz Ahmed, and Victor Chang. ”Identifying the influential spreaders in multilayer interactions of online social networks.” Journal of Intelligent & Fuzzy Systems 31, no. 5 (2016): 2721-2735.
• Al-garadi, Mohammed Ali, Kasturi Dewi Varathan, and Sri Devi Ravana. ”Identification of influential spreaders in online social networks using interaction weighted K-core decomposition method.” Physica A: Statistical Mechanics and its Applications 468 (2017): 278-288.
• Newman, Mark. Networks. Oxford university press, 2018. 30
• Zhu, Zhiguo. ”Discovering the influential users oriented to viral marketing based on online social networks.” Physica A: Statistical Mechanics and its Applications 392, no. 16 (2013): 3459-3469
• Gao, Zhenxiang, Yan Shi, and Shanzhi Chen. ”Measures of node centrality in mobile social networks.” International Journal of Modern Physics C 26, no. 09 (2015): 1550107.
• Kendall, Maurice G. ”A new measure of rank correlation.” Biometrika 30, no. 1/2 (1938): 81-93.
• Kunegis, Jérôme. ”Konect: the koblenz network collection.” In Proceedings of the 22nd international conference on world wide web, pp. 1343-1350. 2013.
• Li, Yuchen, Ju Fan, Yanhao Wang, and Kian-Lee Tan. ”Influence maximization on social graphs: A survey.” IEEE Transactions on Knowledge and Data Engineering 30, no. 10 (2018): 1852-1872.
• Katz, Leo. ”A new status index derived from sociometric analysis.” Psychometrika 18, no. 1 (1953): 39-43.
• Bonacich, Phillip. ”Factoring and weighting approaches to status scores and clique identification.” Journal of mathematical sociology 2, no. 1 (1972): 113-120.
• Anderson, Roy M., and Robert M. May. Infectious diseases of humans: dynamics and control. Oxford university press, 1992.
• Leskovec, J., Rajaraman, A. and Ullman, J.D., 2020. Mining of massive data sets. Cambridge university press.