Influence maximization based on partial network structure information: A comparative analysis on seed selection heuristics

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2016

Tezin Dili: İngilizce

Öğrenci: ŞİRAG ERKOL

Danışman: GÖNENÇ YÜCEL

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu çalışmada çekirdek küme seçimi problemi incelendi. Bu probleme temel olarak eniyileme yaklaşımı uygulanmıştır ve bu yaklaşımın NP-zor olduğu kanıtlanmıştır. Birçok kaynak bu probleme algoritmik sezgisellerle yaklaşmıştır. Bu yaklaşımlardaki temel amaç hesaplama karışıklığını azaltırken çözümlerin hata payının artışını en düşük seviyede tutmaktır. Algoritmik sezgisellerin hata payı düşük, hesaplama karmaşıklıkları yüksektir. Ayrıca kaynakların çoğunda ağların yapısı ve özellikleri hakkında tüm bilgiye sahip olunduğu varsayılmıştır ancak durum genelde bu şekilde değildir. Bu çalışma için bir benzetim modeli kuruldu. Kurulan model, ağları oluşturma, çekirdek küme seçimini yapabilme ve yayılım modellerinin benzetimini gerçekleştirebilmektedir. Ağ üzerine kısmi bilgi kullanan yeni ve ölçüt temelli sezgiseller oluşturuldu ve benzetim modeli kullanılarak test edildi. Bu sezgiseller, sentetik olarak üretilmiş ağlardaki elemanları ve onlarda var olan yerel bilgileri kullandı. Sezgisellerin performansları üç farklı ağ tipi ve iki farklı yayılım modeli, yani altı kombinasyon üzerinde karşılaştırmalı olarak analiz edildi. Sonuçlar, sezgisellerin performanslarının ağ yapılarına bağlı olduğunu göstermektedir. Bir ağ üzerinde kullanılacak sezgisel, ağın özellikleri incelendikten sonra seçilmelidir. Ayrıca, kısmi bilgi yaklaşımıyla umut verici sonuçlar elde edildi. Kısmi bilgi kullanan sezgiseller, birçok yerde tam bilgi kullanan sezgisellerin performanslarına yakınsadılar.