Optimizing influence propagation in directed networks: Novel formulations
Gokhan KarakoseDepartment of Industrial Engineering, Faculty of Engineering, Architecture and Design, Bartin University, Bartin, TurkeyThis 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 5-hour 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 ModellingYönlendirilmiş ağlarda etki yayılımını eniyileme: Yeni formülasyonlar
Gokhan KarakoseBartın Üniversitesi, Mühendislik, Mimarlık ve Tasarım Fakültesi Endüstri Mühendisliği Bölümü, BartınBu 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 saatlik 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 ModellemeManuscript Language: English