Optimizing influence propagation in directed networks: Novel formulations

Abstract

This paper aims to identify influential nodes in complex networks in a short period of time by proposing novel formulations. Traditional centrality metrics have ranked nodes based on individual centrality values, which fall short in identifying several influential nodes simultaneously. Recent literature has introduced an optimization model as a solution to this limitation; however, this model has some shortcomings such as long solution return time and high memory usage. In this paper, two novel formulations are presented as alternatives to this optimization model, with a primary goal of reducing the time needed to obtain solutions. Computational tests have shown that whereas the existing model is unable to return a solution within a 5hour time frame for a small network with approximately 5,000 nodes, the proposed formulations can identify the most influential nodes within minutes, even for large networks with more than 100,000 nodes. The superiority of the proposed models actually lies in their significant reduction in the number of constraints and variables compared to the existing model. Additionally, this paper introduces a novel alternative formulation that addresses the overlapping effect observed in the previous formulations. Computational tests have shown that this model surpasses its predecessors in accelerating the spread of influence throughout the network without causing additional computational burden, thereby setting a better benchmark for future studies in this field.

Keywords

• Influence maximization
• Influential nodes
• Optimization
• Degree centrality
• Mathematical modelling

Yönlendirilmiş ağlarda etki yayılımını eniyileme: Yeni formülasyonlar

Öz

Bu makale, yeni formülasyonlar önererek karmaşık ağlardaki etkili düğümleri kısa zaman diliminde belirlemeyi amaçlamaktadır. Geleneksel merkeziyet ölçümleri, düğümleri bireysel merkeziyet değerlerine göre sıralamaktadır, bu da aynı anda birden fazla etkili düğümün belirlenmesinde yetersiz kalmaktadır. Güncel literatür bu kısıtlamaya çözüm olarak bir optimizasyon modeli sunmuştur, ancak bu modelin uzun süren çözüm döndürme süresi ve yüksek bellek kullanımı gibi bazı eksiklikleri vardır. Bu makalede, çözümleri elde etmede gereken süreyi azaltma ana amacıyla bu optimizasyon modeline alternatif olarak iki yeni formülasyon sunulmuştur. Hesaplamalı testler, mevcut modelin yaklaşık 5,000 düğümlü küçük bir ağ için 5 sa.’lik bir zaman dilimi içinde çözümü döndürmezken, önerilen formülasyonların 100,000'den fazla düğümlü büyük ağlar için bile en etkili düğümleri dakikalar içinde belirleyebildiğini göstermiştir. Önerilen modellerin üstünlüğü aslında mevcut modele kıyasla kısıtların ve değişkenlerin sayısının önemli ölçüde azaltılmasında yatmaktadır. Ek olarak, bu makale, önceki formülasyonlarda gözlenen örtüşen etki sorununu ele alan yeni bir alternatif formülasyon tanıtmaktadır. Hesaplamalı testler, bu modelin, ek hesaplama yüküne neden olmadan etki yayılımını ağ boyunca hızlandırmada öncekilerden daha üstün olduğunu, böylece bu alanda gelecekteki çalışmalar için daha iyi bir kıyaslama oluşturduğunu göstermiştir.

Anahtar Kelimeler

• Etki maksimizasyonu
• Etkili düğümler
• Optimizasyon
• Derece merkezlilik
• Matematiksel modelleme

Kaynakça

1. [1] Wang Z, Andrews MA, Wu ZX, Wang L, Bauch CT. “Coupled disease-behavior dynamics on complex networks: A review”. Physics of Life Reviews, 15, 1-29, 2015
2. [2] Barabási AL, Gulbahce N, Loscalzo J. “Network medicine: a network-based approach to human disease”. Nature Reviews Genetics, 12(1), 56-68, 2011.
3. [3] Xiao F, Aritsugi M, Wang Q, Zhang R. “Efficient processing of multiple nested event pattern queries over multidimensional event streams based on a triaxial hierarchical model”. Artificial Intelligence in Medicine, 72, 56-71, 2016.
4. [4] Xiao F, Zhan C, Lai H, Tao L, Qu Z. “New parallel processing strategies in complex event processing systems with data streams”. International Journal of Distributed Sensor Networks, 13(8), 1-1, 2017.
5. [5] Vega-Oliveros DA, da Fontoura Costa L, Rodrigues FA. “Influence maximization by rumor spreading on correlated networks through community identification”. Communications in Nonlinear Science and Numerical Simulation, 83, 1-13, 2020.
6. [6] Yan Z, Zhou X, Ren J, Zhang Q, Du R. “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), 1-20, 2023.
7. [7] Zhang X, Zhu J, Wang Q, Zhao H. “Identifying influential nodes in complex networks with community structure”. Knowledge-Based Systems, 42, 74-84, 2013.
8. [8] Wang Z, Xia CY, Meloni S, Zhou CS, Moreno Y. “Impact of Social Punishment on Cooperative Behavior in Complex Networks”. Scientific Reports, 3(1), 1-7, 2013.

9. [9] Chang S, Pierson E, Koh PW, Gerardin J, Redbird B, Grusky D, et al. “Mobility network models of COVID-19 explain inequities and inform reopening”. Nature, 589(7840), 8287, 2021.
10. [10] Yang Y, Wang X, Chen Y, Hu M, Ruan C. “A novel centrality of ınfluential nodes ıdentification in complex networks”. IEEE Access, 8, 58742-58751, 2020.
11. [11] Zhang J, Yang C, Jin Z, Li J. “Dynamics analysis of SIR epidemic model with correlation coefficients and clustering coefficient in networks.” Journal of Theoretical Biology, 449, 1-13, 2018.
12. [12] Banerjee S, Jenamani M, Pratihar DK. “A survey on influence maximization in a social network”. Knowledge and Information Systems, 62, 3417-3455, 2020.
13. [13] Dedeturk BA, Gungor BB. “Evaluation of sub-network search programs in epilepsy-related GWAS dataset”. Pamukkale University Journal of Engineering Sciences, 28(2), 292-298, 2020.
14. [14] Zhao Y, Kou G, Peng Y, Chen Y. “Understanding influence power of opinion leaders in e-commerce networks: An opinion dynamics theory perspective”. Information Sciences, 426, 131-147, 2018.
15. [15] Cheng CH, Kuo YH, Zhou Z. “Outbreak minimization v.s. influence maximization: an optimization framework”. BMC Medical Informatics and Decision Making, 20(1), 1-13, 2020.
16. [16] Chaharborj SS, Nabi KN, Feng KL, Chaharborj SS, Phang PS. “Controlling COVID-19 transmission with isolation of influential nodes”. Chaos, Solitons & Fractals, 159, 1-11, 2020.
17. [17] Kynoch G. “Marashea on the mines: economic, social and criminal networks on the South African Gold Fields, 1947-1999.” Journal of Southern African Studies, 26(1), 79-103, 2000.
18. [18] Xu T, Chen J, He Y, He DR. “Complex network properties of Chinese power grid”. International Journal of Modern Physics B, 18(17-19), 2599-2603, 2004.
19. [19] Szklarczyk D, Morris JH, Cook H, Kuhn M, Wyder S, Simonovic M, et al. “The STRING database in 2017: qualitycontrolled protein-protein association networks, made broadly accessible”. Nucleic Acids Research, 45, 362-368, 2017.
20. [20] Pal C, Acharyya A. A novel architecture design for complex network measures of brain connectivity aiding diagnosis. Editors: Garguilo GD, Naik GRG. Wearable/Personal Monitoring Devices Present to Future, 281-302, Singapore, Springer, 2022.
21. [21] Freeman LC. “Centrality in social networks conceptual clarification”. Social Networks. 1(3), 215-39, 1978.
22. [22] Bonacich P, Lloyd P. “Eigenvector-like measures of centrality for asymmetric relations”. Social Networks, 23(3), 191-201, 2001.
23. [23] Katz L. “A new status index derived from sociometric analysis”. Psychometrika, 18(1), 39-43, 1953.
24. [24] Salehi A, Masoumi B. “KATZ centrality with biogeographybased optimization for influence maximization problem”. Journal of Combinatorial Optimization, 40(1), 205-26, 2020.
25. [25] Rehm H, Matar M, Rombach P, McIntyre L. “The effect of the Katz parameter on node ranking, with a medical application”. Social Network Analysis and Mining, 13, 1-8 2023.
26. [26] Goh KI, Kahng B, Kim D. “Universal Behavior of Load Distribution in Scale-Free Networks”. Physical Review Letters, 87(27), 1-4, 2001.
27. [27] Boldi P, Vigna S. “Axioms for Centrality”. Internet Mathematics, 10(3-4), 222-262, 2013.
28. [28] Qi X, Fuller E, Wu Q, Wu Y, Zhang CQ. “Laplacian centrality: A new centrality measure for weighted networks”. Information Sciences, 194, 240-253, 2012.
29. [29] Zhang JX, Chen DB, Dong Q, Zhao ZD. “Identifying a set of influential spreaders in complex networks”. Scientific Reports, 6(1), 1-10, 2016.
30. [30] Ma N, Guan J, Zhao, Y. “Bringing PageRank to the citation analysis”. Information Processing 44(2), 800-810, 2008. & Management, 44(2), 800-810, 2008.
31. [31] Langville AN, Meyer CD. “A survey of eigenvector methods for web information retrieval”. SIAM review, 47(1), 135-161, 2005.
32. [32] Tunali V, Tüysüz MAA. “Analysis of function-call graphs of open-source software systems using complex network analysis”. Pamukkale University Journal of Engineering Sciences, 26(2), 352-358, 2020.
33. [33] Li Q, Zhou T, Lü L, Chen D. “Identifying influential spreaders by weighted LeaderRank”. Physica A: Statistical Mechanics and its Applications, 404, 47-55, 2014.
34. [34] He Q, Lei Z, Wang X, Huang M, Cai Y. “An effective scheme to address influence maximization for opinion formation in social networks”. Transactions on Emerging Telecommunications Technologies, 30(6), 1-15, 2019.
35. [35] Fei L, Zhang Q, Deng Y. “Identifying influential nodes in complex networks based on the inverse-square law”. Physica A: Statistical Mechanics and its Applications, 512, 1044-1059, 2018.
36. [36] Wang Y, Li H, Zhang L, Zhao L, Li W. “Identifying influential nodes in social networks: Centripetal centrality and seed exclusion approach”. Chaos, Solitons & Fractals, 162, 1-15, 2022. 164 Pamukkale Univ Muh Bilim Derg, 31(2), 155-165, 2025 G. Karaköse
37. [37] Pu J, Chen X, Wei D, Liu Q, Deng Y. “Identifying influential nodes based on local dimension”. Europhysics Letters, 107(1), 1-6, 2014.
38. [38] Huang M, Zou G, Zhang B, Gan Y, Jiang S, Jiang K. “Identifying influential individuals in microblogging networks using graph partitioning”. Expert Systems with Applications, 102, 70-82, 2018.
39. [39] Shang Q, Deng Y, Cheong KH. “Identifying influential nodes in complex networks: Effective distance gravity model”. Information Sciences, 577, 162-179, 2021.
40. [40] Curado M, Tortosa L, Vicent J. F. “A novel measure to identify influential nodes: return random walk gravity centrality”. Information Sciences, 628, 177-195, 2023.
41. [41] Xu G, Dong C. “CAGM: A communicability-based adaptive gravity model for influential nodes identification in complex networks”. Expert Systems with Applications, 235, 1-15, 2024.
42. [42] Venunath M, Sujatha P, Koti P. “Identification of influential users in social media network using golden ratio optimization method”. Soft Computing, 28(3), 2207-2222, 2024.
43. [43] Jiang C, Liu X, Zhang J, Yu X. “Compact models for influential nodes identification problem in directed networks”. Chaos: An Interdisciplinary Journal of Nonlinear Science, 30(5), 1-12, 2020.
44. [44] Davis TA, Hu Y. “The University of Florida Sparse Matrix Collection”. ACM Transactions on Mathematical Software (TOMS), 38(1), 1-25, 2011.
45. [45] Transportation Networks for Research Team. “Transportation Networks for Research”. Core https://github.com/bstabler/TransportationNetworks. (05.10.2023).