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
Yazar: Güney, Evren
Dergi: Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, Vol. 20 No. 1, 2019
Anahtar kelimeler: Engineering ; Mühendislik ; Etki Enbüyüklemesi,Sosyal Ağlar,Stokastik Eniyileme,Lagrange Gevşetmesi

Etki EnbüyüklemeProblemi (EEP) büyük bir sosyal ağ içindeki en etkin K tane kişiyi seçen zorbir stokastik kombinatoryal eniyileme problemidir. Son yıllarda pek çokaraştırmacının ilgisini çeken bu problem için çok sayıda etkin yöntemgeliştirilmiştir. Sosyal ağdaki bilginin / etkinin yayılımı çeşitli ağ akışmodelleri ile tasarlandığında, elde edilen problemin amaç fonksiyonununalt-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 gerektirmesialternatif yöntem arayışlarına neden olmuştur. Son yıllarda geliştirilen yeniyö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ışmaproblemin sadece en-iyi çözümüne odaklanmıştır. Bu çalışmada Lagrangegevşetmesi tabanlı ve EEP’yi optimal / optimale yakın çözen ve ölçeklenebilen biryöntem geliştirilmiştir. Bu çerçevede öncelikle, Örneklem OrtalamaYaklaşıklaması ile orijinal probleme yakınsayan belirgin bir matematiksel modelkurulmuştur. Daha sonra bu model üzerinde düğüm bazlı Lagrange gevşetmesitekniği uygulanmıştır. İlgili yöntem bağımsız çağlayan ve doğrusal eşik bilgiyayı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 senaryolardaoptimal / optimale yakın çözümlere ulaşılırken literatürdeki mevcut yöntemleregöre en az bir ölçek mertebesinde hızlanma sağlanmıştır.

Etki EnbüyüklemeProblemi (EEP) büyük bir sosyal ağ içindeki en etkin K tane kişiyi seçen zorbir stokastik kombinatoryal eniyileme problemidir. Son yıllarda pek çokaraştırmacının ilgisini çeken bu problem için çok sayıda etkin yöntemgeliştirilmiştir. Sosyal ağdaki bilginin / etkinin yayılımı çeşitli ağ akışmodelleri ile tasarlandığında, elde edilen problemin amaç fonksiyonununalt-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 gerektirmesialternatif yöntem arayışlarına neden olmuştur. Son yıllarda geliştirilen yeniyö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ışmaproblemin sadece en-iyi çözümüne odaklanmıştır. Bu çalışmada Lagrangegevşetmesi tabanlı ve EEP’yi optimal / optimale yakın çözen ve ölçeklenebilen biryöntem geliştirilmiştir. Bu çerçevede öncelikle, Örneklem OrtalamaYaklaşıklaması ile orijinal probleme yakınsayan belirgin bir matematiksel modelkurulmuştur. Daha sonra bu model üzerinde düğüm bazlı Lagrange gevşetmesitekniği uygulanmıştır. İlgili yöntem bağımsız çağlayan ve doğrusal eşik bilgiyayı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 senaryolardaoptimal / optimale yakın çözümlere ulaşılırken literatürdeki mevcut yöntemleregöre en az bir ölçek mertebesinde hızlanma sağlanmıştır.