Two-level influence maximization problem under deterministic linear threshold model

Abstract

Data-driven decision-making strategies can make online marketing more efficient and help companies reach a larger number of customers using limited resources. In this respect, the Influence Maximization Problem searches for a certain number of influential individuals on a social network so that the information/product spread initiated from such individuals is maximized. We introduce a novel problem, the Two-Level Influence Maximization Problem, which allows influencing neighbors without eventually adopting the product. To solve this problem, we develop a Greedy Algorithm and two variants, namely Modified Greedy Algorithm and Update Limited Algorithm. Modified Greedy Algorithm reaches the same objective function value in a much lower runtime. In Update Limited Greedy Algorithm, runtime is further reduced but objective function value may be compromised. We also introduce a Simulated Annealing-based metaheuristic with a tabu strategy that exploits the problem-specific neighborhood moves. We apply the Simulated Annealing algorithm with the proposed Greedy Algorithm and its variants on small scale random networks and with PageRank and HITS algorithms as initial solutions on large scale real social networks. We also show that following alternative strategies such as maximizing number of individuals that influence their neighbors without adopting the product can also return an effective starting solution for Simulated Annealing algorithm. Computational experiments on simulated and real social networks show that our heuristics can provide high-quality solutions.Veri bazlı karar alma stratejileri çevrimiçi pazarlama yöntemlerini çok daha verimli hale getirebilir ve şirketlerin sınırlı kaynak kullanarak çok sayıda müşteriye ulaşmasına yardımcı olabilir. Bu amaçla Etki Enbüyükleme Problemi, sosyal ağlar üzerinde kendilerinden başlatılacak bir bilgi/ürün yayılmasının ençoklandığı belirli sayıda etkili bireyi bulmayı hedefler. Bireylerin ürünü satın almadan da komşularını etkileyebilmesine olanak sağlayan İki-Seviyeli Etki Enbüyükleme Problemi, tarafımızdan tanıtılmıştır. Bu problemi çözmek için, bir Açgözlü Algoritma ve iki varyantı, Değiştirilmiş Açgözlü Algoritma ve Güncelleme Kısıtlı Açgözlü Algoritma geliştirilmiştir. Değiştirilmiş Açgözlü Algoritma'da, aynı amaç fonksiyonu değeri daha kısa bir çalışma süresinde elde edilir. Güncelleme Kısıtlı Açgözlü Algoritma'da, Açgözlü Algoritma'nın amaç fonksiyonuna yakınsaması garanti edilmez ancak çalışma süresi çok daha kısaltılmıştır. Ayrıca probleme özgü komşuluk hareketlerini hedefleyen ve tabu stratejisi kullanan Benzetimli Tavlama bazlı metasezgisel algoritması önerilmiştir. Bu algoritmayı küçük ölçekli ağlar üzerinde önerilen Açgözlü Algoritma ve varyantları ile ve büyük ölçekli ağlar üzerinde literatürde iyi bilinen bağlantı analizi algoritmaları ile birlikte uyguluyoruz. Ayrıca, ürünü satın almadan komşularını etkileyen kişi sayısını ençoklamaya çalışmak gibi alternatif stratejilerin de Benzetimli Tavlama bazlı algoritma için etkili başlangıç sonuçları oluşturabildiğini gösteriyoruz. Simüle edilmiş ve gerçek ağlar üzerindeki hesaplamasal sonuçlar sezgisel algoritmalarımızın yüksek kaliteli sonuç elde edebildiğini gösteriyor.