Bu proje, sosyal ağ analizinin klasik veri setlerinden biri olan Zachary Karate Club ağı üzerinde, farklı topluluk tespiti (community detection) algoritmalarını C programlama dili ile uygular ve performanslarını Modularity (Q) metriği üzerinden karşılaştırır. Proje, Veri Yapıları ve Algoritmalar dersi kapsamında geliştirilmiştir.
🎯 Proje Amacı
Projenin temel amacı, yönsüz (undirected) bir graf üzerindeki düğümleri, aralarındaki bağlantı yoğunluğuna göre analiz etmek ve Modularity (Q) değerini maksimize edecek en uygun topluluk yapısını ortaya çıkarmaktır.
⚙️ Uygulanan Algoritmalar
Proje kapsamında 4 farklı algoritma implemente edilmiştir:
1. FastGreedy (Clauset–Newman–Moore)
- Hiyerarşik kümeleme mantığıyla çalışır.
- Her düğüm başlangıçta kendi topluluğundadır.
- Her adımda, birleştiğinde ΔQ (modularity artışı) en yüksek olacak iki topluluk birleştirilir.
- Global maksimuma ulaşılana kadar işlem devam eder.
2. Louvain Yöntemi
- Büyük ağlar için optimize edilmiş, iki fazlı bir yaklaşımdır:
- Faz 1 (Local Moving): Düğümler, komşu topluluklara taşınarak yerel modularity artışı denenir.
- Faz 2 (Coarsening): Bulunan topluluklar tek bir süper düğüm haline getirilir ve graf sıkıştırılır. Bu işlem Q değeri sabitlenene kadar iteratif olarak sürer.
3. Label Propagation Algoritması (LPA)
- Asenkron çalışan, "çoğunluğa uyma" prensibine dayalı çok hızlı bir algoritmadır.
- Her düğüm, komşuları arasında en sık görülen etiketi (topluluk ID'sini) benimser.
- Özellikler:
- Stability Fix: Eşitlik durumunda mevcut etiketi koruyarak tek bir dev komün oluşmasını engeller.
- Multi-Run: Algoritma rastgeleliği minimize etmek için 10 kez çalıştırılır ve en yüksek Q değerine sahip sonuç raporlanır.
4. Özgün Algoritma – MyAlgo (Common Neighbor)
- Louvain veya FastGreedy’den farklı olarak, "Ortak Komşu" (Common Neighbor) benzerliğini temel alan hibrit bir yaklaşımdır.
- Sadece Q artışına değil, düğümlerin sosyal bağ kuvvetine (ortak arkadaş sayısı) göre birleştirme kararı verir.
- Sosyal ağlardaki "arkadaşımın arkadaşı benim de arkadaşımdır" mantığını simüle eder.
📂 Proje Dosya Yapısı
.
├── data/
│ └── karate_edges.txt # Zachary Karate Club veri seti (Edge List)
├── include/ # Başlık (.h) dosyaları
│ ├── fastgreedy.h
│ ├── graph.h
│ ├── label.h
│ ├── louvain.h
│ ├── modularity.h
│ └── myalgo.h
├── src/ # Kaynak kod (.c) dosyaları
│ ├── fastgreedy.c
│ ├── graph.c
│ ├── label.c
│ ├── louvain.c
│ ├── main.c
│ ├── modularity.c
│ └── myalgo.c
├── Makefile # Derleme kuralları
├── README.md # Proje dokümantasyonu
└── karate # Derleme sonrası oluşan çalıştırılabilir dosya
Derleme ve Çalıştırma
Tüm projeyi derlemek için:
make
Derlenmiş projeyi çalıştırmak için:
./karate
Tüm projeyi derlemek ve çalıştırmak için:
make run
Program Çıktısı (Örnek)
Program çalıştırıldığında her algoritma için:
- Her düğümün ait olduğu topluluk numaraları
- Toplam modularity (Q) değeri
- Karşılaştırma tablosu Örnek çıktı (kısaltılmış):
=== FastGreedy Sonuc ===
Modularity Q = 0.380671
Komunler:
Komun 1: 1 5 6 7 11 12 17 20
Komun 2: 2 3 4 8 10 13 14 18 22
Komun 3: 9 15 16 19 21 23 24 25 26 27 28 29 30 31 32 33 34
=== Louvain Sonuc ===
Modularity Q = 0.418803
Komunler:
Komun 1: 1 2 3 4 8 10 12 13 14 18 20 22
Komun 2: 5 6 7 11 17
Komun 3: 9 15 16 19 21 23 27 30 31 33 34
Komun 4: 24 25 26 28 29 32
=== Label Propagation Sonuc (10 Tekrarin En Iyisi) ===
Modularity Q = 0.371466
Komunler:
Komun 1: 1 2 3 4 8 12 13 14 18 20 22
Komun 2: 5 6 7 11 17
Komun 3: 9 10 15 16 19 21 23 24 25 26 27 28 29 30 31 32 33 34
=== Özel Algoritma (Common Neighbor) ===
Modularity Q = 0.394395
Komunler:
Komun 1: 1 2 3 4 8 9 10 12 13 14 18 20 22 31
Komun 2: 5 6 7 11 17
Komun 3: 15 16 19 21 23 24 25 26 27 28 29 30 32 33 34
Değerlendirme Ölçütü – Modularity (Q)
Topluluk tespitinin başarısı modularity değeri ile ölçülür. Q değeri arttıkça topluluk yapısı daha belirgin hale gelir. Bu projede Louvain yöntemi genellikle en yüksek Q değerini vermektedir, ancak özgün algoritma (MyAlgo) anlamlı sosyal kümeler oluşturmasıyla dikkat çeker.
Geliştirici
Bu proje, Yusuf Bahçeci tarafından Veri Yapıları ve Algoritmalar dersi kapsamında geliştirilmiştir.