Büyük Veride Alt Çizge Madenciliği

Abstract

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.

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.