A New Greedy Algorithm For Influence Maximization On Signed Social Networks

Authors : Aybike ŞİMŞEK

Pages : 250-257

Doi:10.30855/gmbd.2019.03.06

View : 15 | Download : 10

Publication Date : 2019-12-30

Article Type : Research Paper

Abstract :Sosyal etki insanların görüşlerini şekillendiren büyük olgulardan biridir. Bu bakımdan, Etki Maksimizasyonu (EM) problemi viral pazarlama, kamuoyu şekillendirme gibi pratik faydaları olduğu için sosyal ağ analizinde en fazla ilgili çeken araştırma alanlarından biridir. EM probleminin amacı bir sosyal ağ üzerindeki etkili kişi olarak adlandırılan az sayıdaki kişiyi kullanarak bir etkinin (bir fikir veya reklam) ağ üzerindeki yayılımını maksimize etmektir. Etkili kişilerin tespiti birçok durumda NP-Hard bir kombinasyonal optimizasyon problemidir. Bundan dolayı, EM problemi için birçok algoritma geliştirilmiştir ve geliştirilmeye devam etmektedir. Ne var ki, geliştirilen algoritmalar henüz çözüm kalitesi ve hız açısından istenen seviyede değildirler. Bu çalışmada, bireyler arasındaki olumlu ve olumsuz ilişkileri göz önünde bulunduran işaretli EM problemine odaklanılmıştır. Bu amaçla, en iyi  adet etkili kişiyi tespit etmek için Elitist Aç Gözlü Algoritma (EGA) olarak adlandırılan bir aç gözlü algoritma geliştirmiştir. EGA’nın performansı 2 adet açık veriseti üzerinde rasgele seçim, çıkış derecesi merkeziliği, ve bir güncel algoritma ile kıyaslanmıştır. EGA çözüm kalitesi açısından rakiplerine göre daha iyi sonuçlar vermiştir.
Keywords : Etki maksimizasyonu, online sosyal ağlar, bilgi yayılımı, aç gözlü algoritma