- Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi
- Vol: 20 Issue: 1
- Büyük Ölçekli Etki Enbüyükleme Problemi İçin Lagrange Gevşetmesi Tabanlı Etkin Bir Çözüm Yöntemi...
Büyük Ölçekli Etki Enbüyükleme Problemi İçin Lagrange Gevşetmesi Tabanlı Etkin Bir Çözüm Yöntemi
Authors : Evren GÜNEY
Pages : 47-58
Doi:10.35414/akufemubid.621330
View : 11 | Download : 3
Publication Date : 2020-03-17
Article Type : Research
Abstract :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 optimal / optimale yakın çözen ve ölçeklenebilen bir yöntem geliştirilmiştir. Bu çerçevede öncelikle, Örneklem Ortalama Yaklaşıklaması ile orijinal probleme yakınsayan belirgin bir matematiksel model kurulmuştur. Daha sonra bu model üzerinde düğüm bazlı 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 optimal / optimale yakın çözümlere ulaşılırken literatürdeki mevcut yöntemlere göre en az bir ölçek mertebesinde hızlanma sağlanmıştır.Keywords : Etki Enbüyüklemesi, Sosyal Ağlar, Stokastik Eniyileme, Lagrange Gevşetmesi