An Efficient Lagrangean Relaxation Based Solution Method For Large Scale Influence Maximization Problem

Etki Enbüyükleme Problemi (EEP) büyük bir sosyal ağ içindeki en etkin K tane kişiyi seçen zor bir stokastik kombinatoryal eniyileme problemidir. Son yıllarda pek çok araştırmacının ilgisini çeken bu problem için çok sayıda etkin yöntem geliştirilmiştir. Sosyal ağdaki bilginin / etkinin yayılımı çeşitli ağ akış modelleri ile tasarlandığında, elde edilen problemin amaç fonksiyonunun alt-birimsel olduğu gözlemlenmiştir. Bu sebeple basit bir açgözlü algoritma ile (1-1/e) en kötü performans garantisine erişilmiştir. Ancak, aç gözlü algoritmanın büyük boyutlu problemlerde çok uzun çözüm süreleri gerektirmesi alternatif yöntem arayışlarına neden olmuştur. Son yıllarda geliştirilen yeni yöntemler genelde büyük boyutlu ağlarda kısa sürede iyi çözümler elde ederken (1-1/e) performans garantisini de korumaktadır. Ancak pek az sayıda çalışma problemin sadece en-iyi çözümüne odaklanmıştır. Bu çalışmada Lagrange gevşetmesi tabanlı ve EEP’yi eniyi / eniyiye yakın çözen ve ölçeklenebilen bir yöntem geliştirilmiştir. Bu çerçevede, öncelikle Örneklem Ortalama Yakınsaması ile özgün probleme yakınsayan belirgin bir matematiksel model kurulmuştur. Daha sonra bu model üzerinde düğüm tabanlı Lagrange gevşetmesi tekniği uygulanmıştır. İlgili yöntem bağımsız çağlayan ve doğrusal eşik bilgi yayılım modelleri varsayımı altında çeşitli boyutlardaki sosyal ağ veri setleri (Facebook, Enron, Gnutella, arXiv) üzerinde test edilmiştir. Bütün senaryolarda eniyi / eniyiye yakınThe Influence Maximization Problem (IMP) is defined as identifying the most influential K individuals in a social network, which is a challenging stochastic combinatorial optimization problem. IMP has attracted great interest among researchers in the last years and many efficient solution methods for this problem has been developed. Under IMP the flow of information through the social network is assumed to be following certain information diffusion models and in certain cases the resulting objective function of the optimization problem is a sub-modular function. Therefore, a naive greedy heuristic can achieve a (1-1/e) worst-case bound. However, the greedy method is not scalable and results in very long computation time for large social networks. Upon this observation, many researchers proposed fast and scalable heuristics that still preserve the (1-1/e) worst-case bound. Contrarily, very few researchers focused on finding methods that provide optimal solutions to IMP. In this work a Lagrangean Relaxation based, fast and scalable method that provides optimal / close-to-optimal solutions is proposed. First, a deterministic optimization problem is constructed by using Sample Average Approximation for the original problem. Then, a node based Lagrangean Relaxation approach is developed to solve the approximation of the original problem. The method is tested with both Independent Cascade and Linear Threshold information diffusion models over various size real-life network instances (Facebook, Enron, Gnutella, arXiv). In all scenarios optimal / close-to-optimal solutions are obtained and our approach outperforms the state-of-the-art approaches up to ten times in terms of solution time