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ı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 152
Ö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
- Community within an individual in a transcultural work: Ali Baba und 40 Räuber
Transkültürel bir eserde bireydeki topluluk: Ali Baba und 40 Räuber
ELİF DAMLA YAVUZ
Doktora
İngilizce
2014
Müzikİstanbul Teknik ÜniversitesiMüzikoloji ve Müzik Teorisi Ana Bilim Dalı
PROF. SONGÜL KARAHASANOĞLU
PROF. DR. RALF MARTİN JÄGER
- Modeling the combined effect of RNA-binding proteins and micrornas in post-transcriptional regulation
Transkripsiyon-sonrası kontrolde RNA'ya bağlanan proteinler ve mikrorna'ların etkisinin birlikte modellenmesi
SABER HAFEZQORANI
Yüksek Lisans
İngilizce
2015
BiyoistatistikOrta Doğu Teknik ÜniversitesiSağlık Bilişimi Ana Bilim Dalı
DOÇ. DR. YEŞİM AYDIN SON
YRD. DOÇ. DR. HİLAL KAZAN
- Parallel network flow algorithms
Paralel ağ akışı algoritmaları
GÖKÇEHAN KARA
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CAN ÖZTURAN
- Generation and parameter estimation of markov random field textures and a parallel network for texture generation
Markov rastgele alanı dokularının üretimi, parametrelerinin kestirimi ve doku üretimi için paralel, ağ yapılı bir devre
MEHMET İZZET GÜRELLİ
Yüksek Lisans
İngilizce
1990
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. LEVENT ONURAL
- Design and performance evaluation of a banyan network based interconnection structure for ATM switches
ATM Anahtarları için banyan ağı temelli bir ara bağlantı yapısının tasarlanması ve başarımının değerlendirilmesi
SEMA F. OKTUĞ
Doktora
İngilizce
1996
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiDOÇ.DR. M. UFUK ÇAĞLAYAN