Community Detection (Topluluk Tespiti)

#CommunityDetection #GraphAnalysis #Louvain #GraphRAG #NetworkAnalysis

Topluluk tespiti (Community Detection), bir grafın (ağın) yoğun bağlantılı alt gruplarını — toplulukları — tespit etmeye yarayan graf analizi yöntemidir.

Topluluk tespiti (Community Detection), bir grafın (ağın) yoğun bağlantılı alt gruplarını — toplulukları — tespit etmeye yarayan graf analizi yöntemidir. Topluluklar, kendi içlerinde birbirleriyle yoğun bağlantılara sahip, diğer topluluklarla ise daha seyrek bağlantılı düğüm kümeleridir. Sosyal ağlarda, bilgi graflarında ve biyolojik ağlarda bu yapıları bulmak, sistemin modüler örgütlenmesini anlamamızı sağlar. Temel topluluk tespit algoritmaları şunlardır: Louvain algoritması (modülarite optimizasyonu), Girvan-Newman algoritması (arasındalık merkeziyeti tabanlı kenar silme), Leiden algoritması (Louvain'in geliştirilmiş hali), Spectral Clustering (grafın özvektörlerine dayalı kümeleme) ve Label Propagation (etiket yayılımı). Bu algoritmalar; her biri farklı zaman karmaşıklığı ve ölçeklenebilirlik özellikleri sunar. GraphRAG bağlamında topluluk tespiti kritik bir role sahiptir: Metin belgelerinden çıkarılan varlık grafiındaki topluluklar belirlenir ve her topluluk için özet rapor üretilir. Bu raporlar, genel sorulara (global queries) yanıt üretilirken bağlam olarak kullanılır; böylece standart RAG'ın zorluk çektiği geniş kapsamlı sorularda başarılı sonuçlar elde edilir.

Popüler Topluluk Tespit Algoritmaları

scatter_plot Louvain

Modülarite optimizasyonu tabanlı. Büyük ağlarda hızlı çalışır; O(n log n) karmaşıklığıyla milyonlarca düğüm işler.

auto_graph Leiden

Louvain'in iyileştirilmiş versiyonu; bağlantısız topluluk oluşma sorununu giderir, daha kararlı sonuçlar üretir.

remove_road Girvan-Newman

Arasındalık merkeziyeti yüksek kenarları kaldırarak toplulukları ortaya çıkarır. Küçük ağlarda kaliteli sonuç, büyüklerde yavaş.

label Label Propagation

Her düğüm komşuların çoğunluk etiketini benimser. Çok hızlı ve ölçeklenebilir; bazı çalışmalarda kararsızlık görülebilir.

account_tree GraphRAG ile İlişkisi

Microsoft GraphRAG sisteminde topluluk tespiti şöyle çalışır: Önce belgelerden varlık-ilişki grafiği çıkarılır. Ardından Leiden algoritması ile bu grafta topluluklar belirlenir. Her topluluk için LLM bir özet rapor üretir. Sorgulama sırasında, global sorgular bu topluluk raporlarını bağlam olarak kullanır; lokal sorgular ise belirli varlık alt graflarını kullanır. Bu yaklaşım, "tüm veri setini kapsayan sorular" için standart vektör RAG'a göre belirgin şekilde üstün sonuçlar vermektedir.

Topluluk Tespiti Algoritmaları

  • check_circle Louvain Algoritması: Modülerliği hiyerarşik biçimde optimize eden hızlı ve ölçeklenebilir yöntem. Büyük sosyal ağlarda yaygın kullanım; Python'da networkx ve python-louvain ile kullanılabilir.
  • check_circle Leiden Algoritması: Louvain'ın iyileştirilmiş versiyonu; daha iyi bölünmüş topluluklar bulur. Biyoinformatik ve büyük ağ analizinde tercih ediliyor.
  • check_circle Girvan-Newman: Köprü kenarları (edge betweenness) iteratif kaldırarak toplulukları ayıran klasik yöntem. Küçük ağlarda iyi ama büyük graflarda yavaş.
  • check_circle Spektral Kümeleme: Graf Laplacian'ının özvektörlerini kullanarak topluluk bölümleme. Matematiksel açıdan sağlam; büyük graflarda hesaplama maliyetli.
  • check_circle Label Propagation: Her düğümün komşularının çoğunluk etiketini benimsemesiyle çalışan basit ve hızlı algoritma. Küçük networklerde bile iyi sonuç verebilir.
  • check_circle GNN Tabanlı Yöntemler: Graph Neural Network'lerin derin öğrenme ile topluluk tespiti. Özellikle öznitelik zengin ağlarda daha iyi performans.

Topluluk Tespitinin Uygulama Alanları ve GraphRAG Bağlantısı

Topluluk tespiti, büyük ağların yapısını anlamanın temel tekniğidir. Sosyal ağ analizinde fikir toplulukları, yankı odaları (echo chambers) ve etki ağlarını keşfetmek için kullanılır. Biyoinformatik alanında protein etkileşim ağlarında fonksiyonel modüllerin tespiti ve hastalık mekanizmaları araştırması. Öneri sistemlerinde benzer tercih grubunu bularak kişiselleştirilmiş içerik önerisi. GraphRAG bağlantısı: Microsoft'un GraphRAG sistemi belge külliyatından bilgi grafiği oluşturur, ardından Leiden gibi algoritmalarla bu grafin topluluklarını tespit eder. Bu topluluklar LLM ile özetlenerek 'tema bazlı özetler' oluşturulur; global sorgularda bu özetler kullanılır. Bu yaklaşım standart RAG'ın belge bütünü hakkındaki sorulara yetersiz kalma sorununu çözer. Değerlendirme: modülerlik (modularity) ve NMI (Normalized Mutual Information) tespit kalitesini ölçen yaygın metriklerdir.

quiz Sık Sorulan Sorular

  • check_circle Hangi algoritmayi seçmeliyim?: Büyük ölçekli ve hız öncelikliyse Leiden/Louvain. Kalite ve yavaş ağlar için Girvan-Newman. Keşif amaçlıysa Label Propagation ile başlayın.
  • check_circle Topluluk sayısını nasıl belirliyoruz?: Louvain ve Leiden algoritmaları topluluk sayısını otomatik belirler. Spectral clustering ve K-means gibi yöntemler ise önceden K belirlemeyi gerektirir.
  • check_circle Topluluk tespiti nedir?: Bir ağdaki (grafın) yoğun iç bağlantılara sahip alt grupları (toplulukları) otomatik olarak bulan grafik analiz yöntemidir. Sosyal ağ, biyoinformatik ve öneri sistemlerinde kullanılır.
  • check_circle Hangi topluluk tespiti algoritması kullanılmalı?: Büyük ağlar için Louvain veya Leiden (hızlı, ölçeklenebilir). Küçük ağlarda Girvan-Newman veya spektral kümeleme. Öznitelik zengin ağlar için GNN tabanlı yöntemler. Leiden genel olarak Louvain'den kaliteli sonuç üretir.
  • check_circle Python'da topluluk tespiti nasıl yapılır?: `pip install python-louvain networkx` ile kurulum, `community.best_partition(G)` ile Louvain topluluklarını bulabilirsiniz. Leiden için `leidenalg` paketi kullanılır.
  • check_circle GraphRAG'da topluluk tespiti nasıl kullanılır?: Belgelerden oluşturulan bilgi grafiği Leiden algoritmasıyla bölümlere ayrılır, her topluluk LLM ile özetlenir. Bu özetler global sorgu bağlamı olarak kullanılır; belge bütünü hakkındaki sorularda standart RAG'dan üstündür.