Parallel network motif discovery in complex networks
Karmaşık ağlarda paralel olarak ağ motiflerini bulma
- Tez No: 527414
- Danışmanlar: PROF. DR. MEHMET EMİN DALKILIÇ
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı (disiplinlerarası)
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- “Vatan için ölmek”: Türkiye'de şehit asker kültünün sosyo-politik inşası ve şehit aileleri dernekleri
“Dying for the motherland”: The socio-political construction of martyr soldier cult and martyr family associations in Turkey
ŞAFAK AYKAÇ
- İzmir'de Mustafa Kemal Bulvarı'nın peyzaj mimarlığı açısından etüdü ve peyzaj projesi
Başlık çevirisi yok
ENGİN ALPARSLAN
Yüksek Lisans
Türkçe
1985
Peyzaj MimarlığıEge ÜniversitesiPeyzaj Mimarlığı Ana Bilim Dalı
YRD. DOÇ. DR. ÜMİT ERDEM
- Çocuklarda akut stres hiperglisemisinde hormonal değişikliklerin ve kısa süreli prognozun incelenmesi
Başlık çevirisi yok
AYGÜN DİNDAR
Tıpta Uzmanlık
Türkçe
1987
Çocuk Sağlığı ve Hastalıklarıİstanbul ÜniversitesiÇocuk Sağlığı ve Hastalıkları Hemşireliği Ana Bilim Dalı
DOÇ. DR. HÜLYA GÜNÖZ
- Değişik derim zamanı ve önsoğutmanın Bursa siyahı incir çeşidinin meyve kalitesi ve pazarlama süresi üzerine etkileri
Effects of haruest time and precooling on fruit quality and shelf-life of the fig variety“Bursa siyahı”
FÜSUN GÜRSEL ÇELİKEL
- Dislokasyon-dislokasyon etkileşimi
Başlık çevirisi yok
YILDIRIM AYDOĞDU
Yüksek Lisans
Türkçe
1987
Fizik ve Fizik Mühendisliğiİnönü ÜniversitesiFizik Ana Bilim Dalı
Y.DOÇ.DR. MUSTAFA DİKİCİ