Evaluating Centrality-Based Seed Node Strategies for Influence Diffusion in OSNs: A Study across SCC, WCC and Full Networks using SIR, LT and IC Diffusion Models

Halima Baabcha, Meriem Laifa, Samir Akhrouf

Abstract


This study investigates influence diffusion in online social networks (OSNs) through a comprehensive analysis of centrality measures and diffusion models using the Higgs Twitter dataset. We model OSNs as directed graphs, focusing on strongly connected components (SCCs) and weakly connected components (WCCs). Seven centrality measures (out-degree, in-degree, betweenness, closeness, eigenvector, PageRank, and Katz centrality) are calculated to identify key influential nodes. The top-ranked nodes are then subjected to influence diffusion simulations using three models: Linear Threshold (LT), Independent Cascade (IC), and Susceptible-Infected-Recovered (SIR) across three types of activity networks with different structural characteristics. Our findings reveal significant variations in centrality performance depending on network topology and diffusion dynamics. This methodology integrates structural network analysis with dynamic diffusion modeling to evaluate the effectiveness of influence spread. The experimental results show that out-degree and betweenness centralities are most effective for influence propagation, with the SIR model supporting sustained diffusion. The experimental results reveal that out-degree and betweenness centralities are the most effective measures for influence propagation, with out-degree being particularly impactful for initiating diffusion. The SIR model demonstrated superior efficacy for sustained influence spread, aligning more closely with real-world influence dynamics. Additionally, analyzing influence propagation within WCCs enables more computationally efficient identification of key influencers, without significant loss in accuracy. This work offers actionable insights for influence modeling and provides a practical methodology for selecting centrality measures tailored to specific diffusion scenarios. It explores the influence diffusion across different platforms, enabling researchers to assess and compare user impact by offering a detailed examination of network structures, key node significance and influence diffusion.


Full Text:

PDF

References


Safari, R. M., Rahmani, A. M., & Alizadeh, S. H. (2019). User behavior mining on social media: a systematic literature review. Multimedia Tools and Applications,78(23),33747-33804. https://doi.org/10.1007/s11042-019-08046-6

Peng, S., Zhou, Y., Cao, L., Yu, S., Niu, J., & Jia, W. (2018). Influence analysis in social networks: A survey. Journal of Network and Computer Applications,106,17-32. https://doi.org/10.1016/j.jnca.2018.01.005

Yan, Z., Zhou, X., Ren, J., Zhang, Q., & Du, R. (2023). Identifying underlying influential factors in information diffusion process on social media platform: A hybrid approach of data mining and time series regression. Information Processing & Management,60(5),103438. https://doi.org/10.1016/j.ipm.2023.103438

Shen, B., Guan, T., Ma, J., Yang, L., & Liu, Y. (2021). Social network research hotspots and trends in public health: A bibliometric and visual analysis. Public Healt in Practice, 2, 100155. https://doi.org/10.1016/j.puhip.2021.100155

Ni, P., Zhu, J., Gao, Y., & Wang, G. (2024). Minimizing the misinformation concern over social networks. Information Processing & Management, 61(1),103562. https://doi.org/10.1016/j.ipm.2023.103562

Zheng, H., Zhao, H., & Ahmadi, G. (2024). Towards improving community detection in complex networks using influential nodes. Journal of Complex Networks, 12(1),cnae001. https://doi.org/10.1093/comnet/cnae001

Wang, W., & Street, W. N. (2018). Modeling and maximizing influence diffusion in social networks for viral marketing. Applied network science, 3, 1-26. https://doi.org/10.1007/s41109-018-0062-7

Medjahed, F., Molina, E., & Tejada, J. (2025). Effectiveness of Centrality Measures for Competitive Influence Diffusion in Social Networks. Mathematics (2227-7390),13(2). https://doi.org/10.3390/math13020292

Meshcheryakova, N., & Shvydun, S. (2024). A comparative analysis of centrality measures in complex networks. Automation and Remote Control, 85(8), 685-695. https://doi.org/10.1134/S0005117924700127

Baabcha, H., Laifa, M., & Akhrouf, S. (2022). Social Influence Analysis in Online Social Networks for Viral Marketing: A Survey. In International Conference on Managing Business Through Web Analytics (pp. 143-166). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-031-06971-0_11

Sarkar, D., Kole, D. K., & Jana, P. (2016). Survey of influential nodes identification in online social networks. International Journal of Virtual Communities and Social Networking (IJVCSN), 8(4), 57-69. https://doi.org/ 10.4018/IJVCSN.2016100104

Singh, S. S., Singh, K., Kumar, A., Shakya, H. K., & Biswas, B. (2019). A survey on information diffusion models in social networks. In Advanced Informatics for Computing Research: Second International Conference, ICAICR 2018, Shimla, India, July 14–15, 2018, Revised Selected Papers, Part II 2 (pp. 426-439). Springer Singapore.

https://doi.org/10.1007/978-981-13-3140-4

Arrami, S., Oueslati, W., & Akaichi, J. (2018). Detection of opinion leaders in social networks: A survey. In Intelligent Interactive Multimedia Systems and Services 2017 10 (pp. 362-370). Springer International Publishing.

https://doi.org/10.1007/978-3-319-59480-4_36

Ribeiro, A. C., Azevedo, B., Oliveira e Sá, J., & Baptista, A. A. (2020). How to measure influence in social networks? In International Conference on Research Challenges in Information Science (pp. 38-57). Cham: Springer International Publishing.

https://doi.org/10.1007/978-3-030-50316-1_3

Singh, R. R. (2022). Centrality measures: a tool to identify key actors in social networks. Principles of Social Networking: The New Horizon and Emerging Challenges, 1-27.

https://doi.org/10.1007/978-981-16-3398-0_1

Yujie, Y. (2020). A survey on information diffusion in online social networks. In Proceedings of the 2020 European Symposium on Software Engineering (pp. 181-186). https://doi.org/10.1145/3393822.343232

Li, M., Wang, X., Gao, K., & Zhang, S. (2017). A Survey on Information Diffusion in Online Social Networks: Models and Methods. Information, 8(4), 118. https://doi.org/10.3390/info8040118

Khatri, I., Choudhry, A., Rao, A., Tyagi, A., Vishwakarma, D. K., & Prasad, M. (2023). Influence Maximization in social networks using discretized Harris’ Hawks Optimization algorithm. Applied Soft Computing, 149, 111037. https://doi.org/10.1016/j.asoc.2023.111037

Dhingra, S., Dodwad, P. S., & Madan, M. (2016). Finding strongly connected components in a social network graph. International Journal of Computer Applications, 136(7), 1-5. https://doi.org/10.5120/ijca201690848

Bonifazi, G., Buratti, C., Corradini, E., Marchetti, M., Parlapiano, F., Ursino, D., & Virgili, L. (2025). Defining, Detecting, and Characterizing Power Users in Threads. Big Data and Cognitive Computing, 9(3), 69. https://doi.org/10.3390/bdcc9030069

Puigbò, J. Y., Sánchez-Hernández, G., Casabayó, M., & Agell, N. (2014). Influencer detection approaches in social networks: A current state-of-the-art. In Artificial intelligence research and development (pp. 261-264). https://doi.org/10.3233/978-1-61499-452-7-261

Guzman, J. D., Deckro, R. F., Robbins, M. J., Morris, J. F., & Ballester, N. A. (2014). An analytical comparison of social network measures. IEEE Transactions on Computational Social Systems, 1(1), 35-45. https://doi.org/10.1109/TCSS.2014.2307451

Zafarani, R. (2014). Social Media Mining: An Introduction. Cambridge University Press. https://doi.org/10.1017/CBO9781139088510

Wang, Y., Zhang, L., Yang, J., Yan, M., & Li, H. (2024). Multi-factor information matrix: A directed weighted method to identify influential nodes in social networks. Chaos, Solitons & Fractals, 180, 114485. https://doi.org/10.1016/j.chaos.2024.114485

Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry https://doi.org/10.2307/3033543

Pereira, F. S., Gama, J., de Amo, S., & Oliveira, G. M. (2018). On analyzing user preference dynamics with temporal social networks. Machine Learning, 107, 1745-1773.

https://doi.org/10.1007/s10994-018-5740-2

Rashid, Y., & Bhat, J. I. (2024). Topological to deep learning era for identifying influencers in online social networks: a systematic review. Multimedia Tools and Applications, 83(5), 14671-14714. https://doi.org/10.1007/s11042-023-16002-8

Borgatti, S. P., & Everett, M. G. (2006). A graph-theoretic perspective on centrality. Social networks, 28(4), 466-484. https://doi.org/10.1016/j.socnet.2005.11.005

Duda, R. O., & Hart, P. E. (2006). Pattern classification. John Wiley & Sons

Lü, L., Chen, D., Ren, X. L., Zhang, Q. M., Zhang, Y. C., & Zhou, T. (2016). Vital nodes identification in complex networks. Physics reports, 650, 1-63. https://doi.org/10.1016/j.physrep.2016.06.007

Liao, H., Mariani, M. S., Medo, M., Zhang, Y. C., & Zhou, M. Y. (2017). Ranking in evolving complex networks. Physics Reports, 689, 1-54. https://doi.org/10.1016/j.physrep.2017.05.001

Wenji, C., Bo, Y., Ruigang, Z., Qiong, W., Binsha, Z., Zengbo, L., & Kai, N. (2022). Research on Key Node Identification Method of Transmission Network based on Improved PageRank Algorithm. In 2022 41st Chinese Control Conference (CCC) (pp. 5056-5061). IEEE. https://doi.org/10.23919/CCC55666.2022.9902364

Zhao, L., Sun, P., Zhang, J., Peng, M., Zhong, Y., & Liang, W. (2023). A complex network important node identification based on the KPDN method. Applied Sciences, 13(14), 8303. https://doi.org/10.3390/app13148303

Kempe, D., Kleinberg, J., & Tardos, É. (2003). 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). https://doi.org/10.1145/956750.956769

Pastor-Satorras, R., Castellano, C., Van Mieghem, P., & Vespignani, A. (2015). Epidemic processes in complex networks. Reviews of Modern Physics, 87(3), 925. https://doi.org/10.1103/RevModPhys.87.925

Badr, N., Abdel-Kader, H., & Ali, A. H. (2021). Diffusion Models for Social Analysis, Influence and Learning. IJCI. International Journal of Computers and Information, 8(2), 162-169.

https://doi.org/ 10.21608/ijci.2021.207863

Tian, S., Mo, S., Wang, L., & Peng, Z. (2020). Deep reinforcement learning-based approach to tackle topic- aware influence maximization. Data Science and Engineering, 5, 1-11.

https://doi.org/10.1007/s41019-020-00117-1

Khalife, S., Read, J., & Vazirgiannis, M. (2021). Structure and influence in a global capital–ownership network. Applied Network Science, 6, 1-21.

https://doi.org/10.1007/s41109-021-00359-6

Ji, F., & Jin, J. (2025). A map-reduce algorithm to find strongly connected components of directed graphs. Soft Computing, 1-20. https://doi.org/10.1007/s00500-025-10451-z

Zhong, Z., Lin, L., Jiang, Z., Yuan, X., Ngai, E., Lam, J., & Kwok, K. W. (2025). Connectivity Determination Algorithm for Complex Directed Networks. IEEE Transactions on Network Science and Engineering. https://doi.org/10.1109/TNSE.2025.3549777

Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2), 146-160. https://doi.org/10.1137/0201010

Tarjan, R. E., & Zwick, U. (2024). Finding strong components using depth-first search. European Journal of Combinatorics, 119, 103815. https://doi.org/10.1016/j.ejc.2023.103815

Sobhi, N. A. M. Detection of terminal strongly connected components using a novel DFS-like algorithm (Doctoral dissertation, Universiteit van Amsterdam).

Bakshy, E., Rosenn, I., Marlow, C., & Adamic, L. (2012). The role of social networks in information diffusion. In Proceedings of the 21st international conference on World Wide Web (pp. 519-528). https://doi.org/10.1145/2187836.2187907

Yanchenko, E., Murata, T., & Holme, P. (2024). Influence maximization on temporal networks: a review. Applied Network Science, 9(1), 16. https://doi.org/10.1007/s41109-024-00625-3

Yang, W., Shi, Q., Yan, J., Wang, C., Song, M., & Wu, M. (2024). Complementary influence maximization under comparative linear threshold model. Expert Systems with Applications, 238, 121826. https://doi.org/10.1016/j.eswa.2023.121826

Jaouadi, M., & Romdhane, L. B. (2024). A survey on influence maximization models. Expert Systems with Applications, 248, 123429. https://doi.org/10.1016/j.eswa.2024.123429

Monserrat, T. J. K. P., Pabico, J. P., & Albacea, E. A. (2015). A Hybrid Graph-drawing Algorithm for Large, Naturally-clustered, Disconnected Graphs. arXiv preprint arXiv:1507.02766. https://doi.org/10.48550/arXiv.1507.02766

Veerman, J. J. P., & Kummel, E. (2019). Diffusion and consensus on weakly connected directed graphs. Linear Algebra and its Applications, 578, 184-206.

https://doi.org/10.1016/j.laa.2019.05.014

Tang, L., Zhou, Y., Wang, L., Purkayastha, S., Zhang, L., He, J., ... & Song, P. X. K. (2020). A review of multi‐compartment infectious disease models. International Statistical Review, 88(2), 462-513. https://doi.org/10.1111/insr.12402

Bhat, N., Aggarwal, N., & Kumar, S. (2020). Identification of influential spreaders in social networks using improved hybrid rank method. Procedia Computer Science, 171, 662-671. https://doi.org/10.1016/j.procs.2020.04.072

Zhao, X., Liu, F. A., Wang, J., & Li, T. (2017). Evaluating influential nodes in social networks by local centrality with a coefficient. ISPRS International Journal of Geo-Information, 6(2), 35. https://doi.org/10.3390/ijgi6020035

Talukder, A., Alam, M. G. R., Tran, N. H., Niyato, D., Park, G. H., & Hong, C. S. (2019). Threshold estimation models for linear threshold-based influential user mining in social networks. IEEE Access,7,105441-105461. https://doi.org/10.1109/ACCESS.2019.2931925

Ishfaq, U., Khan, H. U., & Iqbal, S. (2022). Identifying the influential nodes in complex social networks using centrality-based approach. Journal of King Saud University-Computer and Information Sciences, 34(10), 9376-9392. https://doi.org/10.1016/j.jksuci.2022.09.016

Şimşek, A. (2022). Lexical sorting centrality to distinguish spreading abilities of nodes in complex networks under the Susceptible-Infectious-Recovered (SIR) model. Journal of King Saud University-Computer and Information Sciences, 34(8), 4810-4820.

https://doi.org/10.1016/j.jksuci.2021.06.010

Waniek, M., Michalak, T. P., Wooldridge, M. J., & Rahwan, T. (2018). Hiding individuals and communities in a social network. Nature Human Behaviour, 2(2), 139-147.

https://doi.org/10.1038/s41562-017-0290-3

Ghalmane, Z., El Hassouni, M., & Cherifi, H. (2018, October). Betweenness centrality for networks with non-overlapping community structure. In 2018 IEEE workshop on complexity in engineering (COMPENG) (pp.1-5).IEEE. https://doi.org/10.1109/CompEng.2018.8536229

Doostmohammadian, M., Rabiee, H. R., & Khan, U. A. (2020). Centrality-based epidemic control in complex social networks. Social Network Analysis and Mining, 10, 1-11.

https://doi.org/10.1007/s13278-020-00638-7

More, J. S., & Lingam, C. (2019). A gradient-based methodology for optimizing time for influence diffusion in social networks. Social Network Analysis and Mining, 9(1), 5.

https://doi.org/10.1007/s13278-018-0548-4

Shelke, S., & Attar, V. (2019). Source detection of rumor in social network–a review. Online Social Networks and Media, 9, 30-42.

https://doi.org/10.1016/j.osnem.2018.12.001




DOI: https://doi.org/10.31449/inf.v49i22.9193

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.