Tez No	İndirme	Tez Künye	Durumu
680384		Ultra-fast influence maximization with fused sampling and sketches / Örneklem birleştirme ve veri özetleri ile yüksek performanslı etki eniyilemesi Yazar:GÖKHAN GÖKTÜRK Danışman: DR. ÖĞR. ÜYESİ KAMER KAYA Yer Bilgisi: Sabancı Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2021 97 s.
Etki Eniyileme (EE), bir sosyal ağda etkisinin bir yayılma modeline göre maksimum erişilebilirliğe ulaştığı bir düğüm alt kümesi bulma problemidir. Çözümün NP-Zorolması nedeniyle, bu problem için genellikle açgözlü yaklaşım algoritmaları uygulanır. Düzensiz bellek erişim kalıpları ve sorunun olasılıksal doğası, onu zorlu ancaködüllendirici bir optimizasyon hedefi haline getirmektedir.Bu tez, üç yüksek performanslı EE yöntemi önermekte ve gerçekleme için perfor-mans değerlendirmelerini araştırmaktadır; ilk olarak, özüt tabanlı, yön bağımsız rasgele sayı üreteci ve örneklem birleştirme kullanarak, yönlemdirilmemiş bağları örnekleyen bir EE algoritması olan InFuseR-MG'yi öneriyoruz. İkinci olarak, yönlendirilmiş ağlar için, büyük erişilebilirlik kümelerinin boyutlarımı tahmin etmekiçin değiştirilmiş Flajolet-Martin eskizleri kullanan bir EE yönetemi olan Hyper-FuseR'ı anlatacağız. Son olarak, akıllı örneklem-uzay bölümlenmesi ile birden fazla Grafik İşleme Ünitesi kullanmak için özel olarak tasarlanmış, eskiz tabanlı bir EE algoritması olan SuperFuseR önerilmiştir. Bu tezde algoritmaların her adımının performans değerlendirmeleri de tartışılmakta ve önerilen algoritmaların yüksek performanslı gerçeklemeleri de verilmektedir. Her algoritma için, literatürdeki en iyi yöntemler ile performans, kalite ve ölçeklemekarşılaştırmaları da dahil olmak üzere ayrıntılı deney sonuçları bulunmaktadır.
Influence Maximization (IM) is the problem of finding a subset of vertices in a social network whose influence reaches the maximum reachability according to a diffusion model. Due to the NP-Hardness of the solution, often, greedy approximation algorithms are applied. However, irregular memory access patterns and the probabilistic nature of the problem make it a challenging yet rewarding optimization target. This thesis proposes three high-performance IM methods and explores their performance considerations for implementation; first, we propose InFuseR-MG, an IM algorithm that uses a hash-based, direction-oblivious pseudo-random number generator and fused sampling to sample edges in undirected networks. Second, we propose HyperFuseR for directed, generic networks; HyperFuseR uses modified Flajolet-Martin sketches to estimate the cardinality of large reachability sets efficiently. Finally, we propose SuperFuseR, a sketch-based IM algorithm that is specifically designed for the multi-GPU setting. SuperFuseR uses a sampling-aware sample-space split mechanism to distribute the graph to multiple devices. Also in this work, we discuss performance considerations at each step of the proposed algorithms and provide their high-performance implementations. For each algorithm, we provide detailed experimental results, including performance, quality, and scaling benchmarks