Topluluk Tespiti — Ağlarda Grafik Kümeleme
- Ortaya koyan
- Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
- Yıl
- 2002–2019 (algorithm family)
- Tür
- Graph-partitioning / clustering algorithm family
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Topluluk tespiti, bir ağ içinde yoğun bir şekilde bağlantılı alt grupları — toplulukları — keşfeden bir grafik bölümleme algoritmaları ailesidir.
İlk olarak Girvan ve Newman (2002) tarafından modülerlik ölçüsü aracılığıyla formüle edilen bu alan, Louvain yöntemi (Blondel vd., 2008), Leiden iyileştirmesi (Traag vd., 2019) ve bilgi-teorik Infomap yaklaşımı ile hızla ilerlemiştir. Tüm varyantlar aynı soruyu yanıtlar: hangi düğümler kendi aralarında ağın geri kalanından daha sıkı bir şekilde kümelenir?
Yöntemin mantığı
Bazı insanların çoğunlukla kendi yakın çevreleriyle konuştuğu, ancak ara sıra dışarıyla iletişim kurduğu büyük bir sosyal ağ hayal edin. Topluluk tespiti, bu çevreleri önceden etiketlemenize gerek kalmadan otomatik olarak bulur. Algoritma, düğümleri, iç bağlantıların yoğun ve gruplar arası bağlantıların seyrek olduğu gruplara yeniden düzenler — modülerlik adı verilen bir kalite puanını maksimize ederek (veya Infomap'te, ağdaki rastgele bir yürüyüşün açıklama uzunluğunu minimize ederek). Sonuç bir bölümlendirmedir: her düğüm tam olarak bir topluluğa aittir ve ağı bir dizi uyumlu küme olarak görselleştirebilirsiniz.
Tarih
Ağlardaki topluluk yapısının incelenmesi, hiyerarşik ağ bölümlemesi için bir araç olarak kenar betweenness kavramını tanıtan Girvan ve Newman (2002) tarafından nicel bir temele oturtulmuştur. Newman ve Girvan (2004) daha sonra standart kalite kriteri haline gelen modülerlik ölçüsü Q'yu formüle etmişlerdir. Blondel vd. (2008), milyonlarca düğüme sahip ağlarda yüksek kaliteli topluluk tespitini pratik hale getiren iki aşamalı açgözlü bir optimizasyon olan Louvain yöntemini yayınlamışlardır. Traag, Waltman ve van Eck (2019), Louvain'de dahili olarak bağlantısız topluluklar üretebilen yapısal bir kusur tespit etmiş ve bunu düzeltmek için Leiden algoritmasını geliştirerek iyi bağlantılı bölümlendirmeleri garanti etmişlerdir. Paralel olarak, Rosvall ve Bergstrom (2008), topluluk tespitini bir sıkıştırma problemi olarak yeniden çerçeveleyen Infomap'i geliştirmişlerdir: ağdaki rastgele bir yürüyüşün açıklama uzunluğunu minimize eden bölümlendirmeyi bulun.
Ne zaman kullanılır?
Topluluk tespiti, bir ağınız olduğunda (minimum ~20 düğüm) ve grupları önceden belirtmeden gizli grup yapısını keşfetmek istediğinizde uygundur. Kesitsel ve boylamsal ağ verileri dahil olmak üzere ikili veya sürekli kenar ağırlıklı veriler üzerinde keşifsel, tanımlayıcı ve sınıflandırma hedefleri için uygundur. Düğüm nitelikleri veya normal dağılımlar gerektirmez. Yöntem, topluluk sayısı bilinmediğinde özellikle iyi sonuç verir. Ağ çok küçükse (20'den az düğüm), tanımlayıcı ağ istatistikleri tercih edilir. Sonuçlar kenar ağırlığı tanımlarına ve ağ yoğunluğuna duyarlıdır, bu nedenle bu seçimler dikkatlice düşünülmelidir.
Sınırlar ve dikkat edilmesi gerekenler
- Modülerlik maksimizasyonu yerel optimumlara duyarlıdır; sonuçlar çalıştırmalar arasında değişebilir ve birden çok çalıştırmanın en iyisi olarak rapor edilmelidir.
- Çözünürlük sınırı, büyük ağlardaki çok küçük toplulukların bir araya getirilerek ince taneli yapıyı maskeleyebileceği anlamına gelir.
- Sonuçlar, kenar ağırlıklarının nasıl tanımlandığına duyarlıdır; farklı ağırlıklandırma şemaları anlamlı derecede farklı bölümlendirmeler verebilir.
- Girvan-Newman O(m²n) karmaşıklığına sahiptir ve büyük ağlarda pratik değildir; ölçek için Louvain veya Leiden tercih edilmelidir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Topluluk sayısının önceden belirtilmesini gerektirmez — bölümlendirme boyutu veriler tarafından belirlenir.
- Büyük ağlara ölçeklenir: Louvain ve Leiden neredeyse doğrusal zamanda çalışır, bu da onları milyonlarca düğüme sahip ağlar için pratik hale getirir.
- Leiden, Louvain'in bağlantısız topluluk kusurunu düzelterek, iyi bağlantılı, dahili olarak uyumlu toplulukları garanti eder.
- Veriler üzerinde dağılımsal varsayımlar olmaksızın hem ağırlıksız hem de ağırlıklı ağlara uygulanabilir.
Uygulama alanları
- Bilimsel alanları haritalamak için atıf ve ortak yazarlık ağlarındaki araştırma kümelerini belirleme.
- Biyolojide protein-protein etkileşim ağlarındaki fonksiyonel modülleri tespit etme.
- Davranışsal analiz için sosyal medya ve iletişim ağlarındaki kullanıcı topluluklarını bulma.
- Uyumlu müşteri gruplarını ortaya çıkarmak için iş ve pazarlamada müşteri ağlarını segmentlere ayırma.
- Altyapı, ulaşım veya tedarik zinciri ağlarındaki yapısal blokları keşfetme.
Nasıl çalışır?
Nasıl çalışır?
Girdi, düğümleri varlıkları (insanlar, web sayfaları, proteinler, atıflar) ve kenarları aralarındaki ilişkileri temsil eden bir grafiktir. Kenarlar yönlü veya yönsüz olabilir ve ağırlık taşıyabilir. Komşuluk yapısı — hangi düğümlerin bağlı olduğu ve ne kadar güçlü olduğu — algoritmaların ihtiyaç duyduğu tek girdidir. Düğüm etiketleri, sınıfları veya harici nitelikler gerekli değildir, ancak sonuçları daha sonra doğrulamak için kullanılabilirler.
Her algoritma, düğümlerin topluluklara başlangıçtaki bir atamasıyla başlar. Louvain ve Leiden'da her düğüm kendi tekil topluluğu olarak başlar. Girvan-Newman, tam ağ ile başlar ve en yüksek betweenness centrality'ye sahip kenarı yinelemeli olarak kaldırarak topluluk yapısını aşamalı olarak ortaya çıkarır. Infomap, ağın rastgele yürüyüş açıklamasından başlar ve kod uzunluğunu minimize etmek için iki seviyeli bir harita kullanarak onu kodlar.
Çekirdek aşama, modülerlik Q'yu maksimize eden (Louvain, Leiden) veya harita denklemi kod uzunluğunu minimize eden (Infomap) bir bölümlendirme arar. Louvain, Q'yu iyileştirmek için tek düğümleri topluluklar arasında açgözlü bir şekilde hareket ettirir, ardından toplulukları süper düğümlere toplar ve tekrarlar — iyi ölçeklenen ancak bağlantısız topluluklar üretebilen iki aşamalı bir süreçtir. Leiden, toplama öncesinde yerel bir hareket ve iyileştirme adımı kullanarak her topluluğun dahili olarak bağlı olduğunu garanti ederek Louvain'i iyileştirir. Girvan-Newman, kenarları yinelemeli olarak kaldırır ve bölmelerin dendrogramını kaydeder; dendrogramın herhangi bir kesiminde Q'yu maksimize eden bölümlendirme seçilir. Topluluk sayısı algoritmanın kendisinden ortaya çıkar; önceden belirtilmesi gerekmez.
Nihai bölümlendirmenin kalitesi, -0.5 ile 1 arasında değişen modülerlik puanı Q ile özetlenir. Yaklaşık 0.3-0.5'in üzerindeki değerler genellikle anlamlı topluluk yapısının göstergesi olarak kabul edilir. Modülerlik optimizasyonu yerel optimumlarda takılı kalabileceğinden, algoritmayı birden çok kez çalıştırmak ve en iyi sonucu almak standart bir uygulamadır. Bölümlendirme ayrıca görsel olarak incelenir ve anlamlı olduğunu doğrulamak için mevcut düğüm nitelikleri veya gerçek etiketlerle çapraz doğrulanır.
Sık yapılan hatalar
- Algoritmayı bir kez çalıştırmak ve tek sonucu gerçek olarak kabul etmek — her zaman birden çok kez çalıştırın ve en iyi modülerliği rapor edin veya topluluk yöntemlerini kullanın.
- Çözünürlük sınırını göz ardı etmek: büyük seyrek ağlarda, küçük ama gerçek topluluklar uyarı vermeden daha büyük olanlara dahil edilebilir.
- Modülerlik tabanlı algoritmaları 20'den az düğüme sahip ağlara uygulamak — bu ölçekte topluluk yapısı güvenilir bir şekilde tanımlanamaz.
- Yüksek bir modülerlik puanını doğrulanmış gerçek dünya topluluk yapısıyla karıştırmak; modülerlik, bölümlendirmenin bir kalite ölçüsüdür, toplulukların istatistiksel olarak anlamlı olup olmadığına dair çıkarımsal bir test değildir.
Sık sorulan sorular
Hangi algoritmayı seçmeliyim — Louvain, Leiden, Girvan-Newman veya Infomap?
Louvain, büyük ağlar için hızlı, yaygın olarak kullanılan bir temeldir. Leiden, doğruluk önemli olduğunda tercih edilen seçenektir, çünkü dahili olarak bağlı toplulukları garanti eder ve genellikle daha yüksek modülerlik elde eder. Girvan-Newman, hiyerarşik keşif için yararlı bir dendrogram üretir ancak büyük ağlar için çok yavaştır. Infomap, rastgele bir yürüyüşçünün izlediği yolun anlamlı olduğu yönlü veya akış tabanlı ağlar için çok uygundur.
Topluluk sayısını önceden belirtmem gerekiyor mu?
Hayır. Louvain, Leiden ve Infomap, topluluk sayısını ağ yapısından otomatik olarak belirler. Girvan-Newman, herhangi bir sayıda topluluğun okunabileceği tam bir dendrogram üretir; genellikle Q'yu maksimize eden bölümlendirme seçilir.
Bulunan toplulukların anlamlı olup olmadığını nasıl anlarım?
Modülerlik puanı Q, veriye içsel bir kalite ölçüsü sağlar; yaklaşık 0.3-0.5'in üzerindeki değerler önemsiz olmayan topluluk yapısını gösterir. Bunun ötesinde, topluluklar alan bilgisi, düğüm nitelikleri veya harici etiketlerle doğrulanmalıdır. Yüksek Q tek başına sosyolojik veya biyolojik önemi kanıtlamaz.
Çalıştırmalar arasında sonuçlar farklılık gösterirse ne olur?
Modülerlik optimizasyonu bir sezgiseldir ve farklı çalıştırmalar, özellikle Louvain'de, biraz farklı bölümlendirmeler verebilir. Algoritmayı birden çok kez çalıştırın (büyük ağlarda en az 10-100 çalıştırma) ve en yüksek Q'ya sahip bölümlendirmeyi rapor edin. Leiden, iyileştirme adımı daha kapsamlı olduğu için Louvain'den daha kararlıdır, ancak tekrarlanan çalıştırmalar iyi bir uygulama olmaya devam eder.
İlgili yöntemler
Kaynaklar
Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.
DOI kaynağını açKopyalandı.Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.
Yayın kaynağını açKopyalandı.