Karmaşık ağlarda paralel olarak ağ motiflerini bulma

Bu tezde, ağ motifleri, mevcut seri ve paralel motif keşif algoritmaları hakkında bir yazın taraması yapıldıktan sonra ağ ve ağaç paralelleştirme yaklaşımları kullanılarak yeni paralel motif keşif algoritmaları sunulmuştur. Ağ paralelleştirmesinde, hedef ağı işlemciler arasında bölmek için Genişlik Öncelikli Arama ve Yıldız Daralması'na dayanan iki farklı ağ paralelleştirme algoritması önerilmiştir. Yıldız Daralmasını karmaşık ağların bölümlendirilmesine daha uygun hale getirmek için iki yeni sezgisel yöntem geliştirilmiştir. Birden fazla bölümde bulunan motiflerin tam olarak bulunmasını sağlamak için Hayalet Düğüm Algılama algoritmaları sunulmuştur. Ayrıca, ağaç paralelleştirmesi yaklaşımını kullanan yeni bir algoritma önerilmiş ve düğüm numaraları için bir yeniden etiketleme şeması kullanılarak algoritmanın hızı ve bellek kullanımı iyileştirilmiştir. Ağ paralelleştirme algoritmalarının hızlarını arttırmak için iş yükünün işlemcilere daha dengeli ve adil bir şekilde dağıtılması gerekmektedir. Üç dinamik yük dengeleme algoritması kullanılarak bu hedefe ulaşılmıştır: merkezi efendi-köle, rastgele seçimli dağıtık ve halka dağıtık. Tüm paralelleştirme yöntemlerinde, alt çizgeleri saymak için ESU algoritması, motif adaylarını eşyapılı sınıflara ayırmak için Nauty kullanılmıştır. Rastgele ağların oluşturulması için Markov-zincir yöntemine dayanan bir algoritma uygulanmış ve ağ motiflerini elde etmek için eşyapılı sınıfların z-değerleri hesaplanmıştır. Paralel algoritmaların hızlanma, paralelleştirme maliyeti, çalışma süresi, bellek kullanımı ve ölçeklenebilirlik açısından karşılaştırılması verilmiştir. Farklı tiplerdeki karmaşık ağlar üzerinde yapılan testler, önerilen algoritmaların seri ESU algoritmasına kıyasla önemli hızlanma sağladığını ve daha büyük motiflerin keşfine izin verdiğini göstermektedir.