GCRIS

Now showing 1 - 2 of 2

Graphlet mining in big data
(01. Izmir Institute of Technology, 2024) Ergenç Bostanoğlu, Belgin; Çalmaz, Büşra; Bostanoğlu, Belgin Ergenç
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.
Knowledge hiding on graph data
(01. Izmir Institute of Technology, 2024) Tekin, Leyla; Bostanoğlu, Belgin Ergenç
Çizgelerde anlamlı alt yapılar olan alt çizgeler ve topluluklar, ağ yapılarının daha derinlemesine anlaşılması için önemli bilgiler sağlar. Ancak çizge analiz araçları daha gelişmiş hale geldikçe, bu durum, çizge verilerinden gereğinden fazla bilgi çıkarılması riski gibi yeni bir zorluğu da beraberinde getirir. Böylelikle, bilgi gizleme tekniklerinin araştırılmasına yol açmıştır. Bu tez kapsamında, çizge verilerinin mahremiyetini koruyan teknikler olarak alt çizge gizleme ve topluluk gizleme incelenmektedir. Alt çizge gizleme, işlemsel çizge veritabanındaki hassas alt çizgeleri tanımlamayı ve verilerin yayınlanmasından sonra onların ifşa edilmesini önlemek için veritabanını dönüştürmeyi içerirken, orijinal verileri mümkün olduğunca korur. Topluluk gizleme ise çizgeyi stratejik olarak değiştirerek toplulukların gizlenmesini veya karartılmasını içerir. Kullanıcıların topluluk üyeliği gibi hassas bilgilerinin gizliliğini koruyan topluluk gizlemeye yönelik çalışmalarla birlikte, gizlemeye etkili bir şekilde karşı koyabilecek dayanıklı topluluk tespit algoritmalarına olan ihtiyaç daha da belirgin hale gelir. Bu tezde öncelikle alt çizge gizleme teknikleri incelenmiş ve çeşitli kenar silme tabanlı algoritmalar önerilmiştir. Daha sonra, topluluk gizleme teknikleri araştırılmış ve tekniklerin üç ölçekte kapsamlı bir şekilde ele alınması için bir araştırma yapılmıştır. Ayrıca, klikler kullanılarak küresel topluluk gizleme için bir algoritma önerilmiştir.

Phd Degree / Doktora

Browse

Filters

Settings

Sort By

Results per page

Search Results