Tez No	İndirme	Tez Künye	Durumu
527414		Parallel network motif discovery in complex networks / Karmaşık ağlarda paralel olarak ağ motiflerini bulma Yazar:ESRA RÜZGAR ATEŞKAN Danışman: PROF. DR. MEHMET EMİN DALKILIÇ Yer Bilgisi: Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2018 152 s.
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.
In this thesis, we first provide a literature survey of network motifs, existing sequential and parallel network motif discovery algorithms. We present new parallel motif discovery algorithms using network and tree parallelization approaches. For network parallelization, we propose two network parallelization algorithms based on Breadth First Search and Star Contraction. We develop two new heuristics to make star contraction suitable for partitioning of complex networks. We present Ghost Vertex Detection algorithms to ensure that the motifs located in multiple partitions are exactly found. Moreover, for tree parallelization, we propose a new algorithm and improve its speedup and memory usage using a novel relabelling scheme for vertex identifiers. In order to increase speedups of our network parallelization algorithms, we need to distribute the workload fairly among the processors. We attain this goal by using three dynamic load balancing algorithms: centralized masterslave, random polling distributed and ring distributed. For all parallelization methods, we use the ESU algorithm to count subgraphs and Nauty to group motif candidates into isomorphic classes. We implement a random network generation algorithm based on Markov-chain method. We calculate z-scores of isomorphic classes to obtain network motifs. We provide comparison of parallel algorithms in terms of speedup, parallelization overhead, running time, memory usage and scalability. Experiments on complex networks of different types demonstrate that the proposed algorithms provide significant speedups when compared to sequential ESU algorithm allowing discovery of larger motifs.