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Ç
- Deciphering sequence variations and splicing sensitivity: Predictive analysis of PSI in SRRM4 response groups
Sekans varyasyonlarının ve birleştirme duyarlılığının çözümlenmesi: SRRM4 yanıt gruplarında PSIin tahminsel analizi
ÜMİT SUDE BÖLER
Yüksek Lisans
İngilizce
2025
BiyolojiOrta Doğu Teknik ÜniversitesiSağlık Bilişimi Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURÇAK OTLU SARITAŞ
DR. MAFALDA DİAS
- Investigating molecular interaction networks of nuclear factor one transcription factors
Nükleer faktör I transkripsyon faktörlerinin moleküler etkileşim ağlarının araştırılması
DİCLE MALAYMAR PİNAR
Doktora
İngilizce
2024
Genetikİstanbul Teknik ÜniversitesiMoleküler Biyoloji-Genetik ve Biyoteknoloji Ana Bilim Dalı (disiplinlerarası)
DOÇ. DR. ASLI KUMBASAR
DOÇ. DR. MARKKU VARJOSALO
- 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
Sosyolojiİstanbul Teknik ÜniversitesiMüzikoloji ve Müzik Teorisi Ana Bilim Dalı (disiplinlerarası)
PROF. SONGÜL KARAHASANOĞLU
PROF. DR. RALF MARTİN JÄGER
- Muş ili İslam dönemi mimari eserlerin güncel durumlarının belgelendirilmesi ve değerlendirilmesi
Documentation and evaluation of the current conditions of Islamic period architectural monuments in Muş
ABDULKERİM BOZYEL
Yüksek Lisans
Türkçe
2025
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. ARAS NEFTÇİ