Graphlet mining in big data
Büyük veride alt çizge madenciliği
- Tez No: 923153
- Danışmanlar: DOÇ. DR. BELGİN ERGENÇ BOSTANOĞLU
- 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: 2024
- Dil: İngilizce
- Üniversite: İzmir Yüksek Teknoloji Enstitüsü
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 119
Özet
This thesis explores graphlet counting algorithms, which are crucial for understanding the structural principles of complex networks such as bioinformatics, social networks, and network model evaluation. Counting graphlets in large networks is computationally challenging due to the combinatorial explosion of possibilities, particularly for larger graphlet sizes. To address this, we focus on clique graphlets, fully connected subgraphs, which reveal critical patterns in areas like protein structure analysis, social network modeling, community detection, and spam detection. Counting k-cliques (subgraphs with $k$ nodes) becomes infeasible for large datasets and high $k$ values. Existing exact and approximate algorithms struggle with large $k$, often failing when $k$ exceeds 10. To tackle these limitations, we propose BDAC (Boundary-Driven Approximations of K-Cliques), a novel algorithm that efficiently approximates k-clique counts using classical extremal graph theorems. BDAC uniquely provides lower and upper bounds for k-clique counts at both local (per vertex) and global levels, making it particularly suited for large, dense graphs with high $k$ values. Unlike existing methods, the algorithm's complexity remains unaffected by the value of $k$. We validate BDAC's efficiency and scalability through extensive comparisons with leading algorithms on diverse datasets, spanning k values from minor (e.g., 8) to large (e.g., 50). Parallelization techniques enhance its performance, making it highly scalable for analyzing large and dense networks. BDAC offers a significant advancement in k-clique counting, enabling the analysis of previously considered computationally intractable networks.
Özet (Çeviri)
Bu tez, biyoenformatik, sosyal ağlar ve ağ modeli değerlendirmesi gibi karmaşık ağların yapısal prensiplerini anlamak için kritik öneme sahip olan alt çizge sayma algoritmalarını incelemektedir. Büyük ağlarda alt çizgelerin sayılması, özellikle daha büyük alt çizge boyutları için olasılıkların kombinatoryel patlaması nedeniyle hesaplama açısından zorludur. Bu zorlukları ele almak için, protein yapısı analizi, sosyal ağ modelleme, topluluk tespiti ve spam tespiti gibi alanlarda kritik desenleri ortaya çıkaran tam bağlı alt çizgeler olan k-klik alt çizgelerine odaklanıyoruz. K-klik'lerin ($k$ düğümlü alt çizgeler) sayılması, büyük veri kümeleri ve yüksek $k$ değerleri için uygulanamaz hale gelmektedir. Mevcut kesin ve yaklaşık algoritmalar, $k$ 10'u aştığında genellikle başarısız olur. Bu sınırlamaların üstesinden gelmek için, klasik ekstremal çizge teoremlerini kullanarak k-klik sayılarını verimli bir şekilde yaklaşık olarak hesaplayan yenilikçi bir algoritma olan BDAC'ı (K-kliklerin Sınır Tabanlı Yaklaşımı) öneriyoruz. BDAC, k-klik sayımları için hem yerel (düğüm bazında) hem de küresel seviyelerde benzersiz bir şekilde alt ve üst sınırlar sağlayarak, özellikle yüksek $k$ değerlerine sahip büyük ve yoğun çizgeler için son derece uygundur. Mevcut yöntemlerin aksine, algoritmanın karmaşıklığı $k$ değerinden etkilenmez. BDAC'ın verimliliğini ve ölçeklenebilirliğini, küçük (ör. 8) ile büyük (ör. 50) arasında değişen $k$ değerlerini kapsayan çeşitli veri kümeleri üzerinde önde gelen algoritmalarla yapılan kapsamlı karşılaştırmalarla doğruluyoruz. Paralelleştirme teknikleri, performansını daha da artırarak, büyük ve yoğun çizgelerin analizinde oldukça ölçeklenebilir hale getirmektedir. BDAC, k-klik sayımı konusunda önemli bir ilerleme sunarak, daha önce hesaplama açısından ulaşılamaz kabul edilen çizgelerin analizine olanak tanımaktadır.
Benzer Tezler
- Balıkesir ili, Kille köyü kumrutüyü mermerinin değerlendirilmesi
Başlık çevirisi yok
ABDÜLKERİM PEKİN
Yüksek Lisans
Türkçe
1992
Maden Mühendisliği ve MadencilikAnadolu ÜniversitesiMaden Mühendisliği Ana Bilim Dalı
PROF. DR. RIFAT BOZKURT
- Construction and analysis of tissue/disease specific protein-protein interaction networks by integrating large scale transcriptome data with genome scale protein-protein interaction networks
Transkriptom ve genom ölçekli protein etkileşim ağlarının birleştirilmesi ile durum bazlı spesifik protein etkileşim ağlarının oluşturulması ve analizi
ARZU BURÇAK ŞENKAL
Doktora
İngilizce
2022
Bilim ve TeknolojiOrta Doğu Teknik ÜniversitesiTıp Bilişimi Ana Bilim Dalı
PROF. DR. TOLGA CAN
- Structural pattern detection and domain recognition for protein function prediction
Protein fonksiyon tayini için yapısal örüntü ve domen tanınması
SÜVEYDA YENİTERZİ
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. UGUR SEZERMAN
- Uncovering hidden connections and functional modules via pyparagon: A hybrid approach for network contextualization
Gizli etkileşimler ve fonksiyonel modüllerin hibrit bir ağ bağlamsallaştirma araci pyparagon ile açiğa çikarilmasi
MÜSLÜM KAAN ARICI
Doktora
İngilizce
2024
BiyoistatistikOrta Doğu Teknik ÜniversitesiTıp Bilişimi Ana Bilim Dalı
YRD. DOÇ. DR. AYBAR CAN ACAR
DOÇ. DR. NURCAN TUNÇBAĞ
- A novel metaheuristic for graph and graphset-T coloring problem
Çizge boyama ve çizgeyi kümeli boyama problemi üzerine metasezgisel algoritma
ÇAĞRI YEŞİL
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMİN ERKAN KORKMAZ