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

Büyük Ölçekli Etki Enbüyükleme Problemi İçin Lagrange Gevşetmesi Tabanlı Etkin Bir Çözüm Yöntemi

Abstract

The 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-tooptimal 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 reallife 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.

Özet

Etki Enbüyükleme Problemi (EEP) büyük bir sosyal ağ içindeki en etkin K tane kişiyi seçen zor bir stokastikkombinatoryal 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ış modelleriile tasarlandığında, elde edilen problemin amaç fonksiyonunun alt-birimsel olduğu gözlemlenmiştir. Busebeple 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öntemarayışlarına neden olmuştur. Son yıllarda geliştirilen yeni yöntemler genelde büyük boyutlu ağlarda kısasü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ı veEEP’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 modelkurulmuş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şitliboyutlardaki sosyal ağ veri setleri (Facebook, Enron, Gnutella, arXiv) üzerinde test edilmiştir. Bütünsenaryolarda eniyi / eniyiye yakın çözümlere ulaşılırken yazındaki mevcut yöntemlere göre on katakadar hızlanma sağlanmıştır.