Stokastik Blok Modeli — Ağlarda Olasılıksal Topluluk Tespiti
- Yıl
- 1983
- Tür
- Probabilistic generative graph model
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Holland, Laskey ve Leinhardt (1983) tarafından tanıtılan Stokastik Blok Modeli (SBM), düğümleri gizli bloklara atayan ve bloklar arasındaki bağlantı olasılıklarını parametrik olarak tahmin eden, grafikler için olasılıksal bir üretken modeldir.
Ağ analizinde topluluk tespiti, çekirdek-çevre (core-periphery) tanımlaması ve hiyerarşik yapı keşfi için temel yaklaşımdır.
Yöntemin mantığı
İnsanların gruplar halinde (iş arkadaşları, aile, spor takımları) kümelendiği ve bir grup içindeki bağlantıların gruplar arası bağlantılardan daha olası olduğu bir sosyal ağ hayal edin. Stokastik Blok Modeli bu sezgiyi formüle eder: her düğüm için gizli bir grup etiketi olduğunu ve herhangi iki düğüm arasındaki bir kenarın olasılığının yalnızca bu iki düğümün ait olduğu gruplara bağlı olduğunu varsayar. Modeli uydurmak, gözlemlenen kenar örüntüsünü en iyi açıklayan gizli etiketleri bulmak anlamına gelir. Sonuç, grupların yoğun klikler olmasını gerektirmeyen, ağın bloklara ayrılmış, prensipli, istatistiksel olarak temellendirilmiş bir bölümlemesidir — model, çekirdek-çevre yapılarını ve hatta grup içi bağlantıların grup dışı bağlantılardan daha az olduğu disassortatif örüntüleri bile barındırır.
Tarih
Stokastik Blok Modeli, Holland, Laskey ve Leinhardt tarafından 1983 tarihli Social Networks makalelerinde, sosyal ağ analizindeki önceki blok modelleme çalışmalarının olasılıksal bir genellemesi olarak tanıtıldı. Yirmi yıl boyunca öncelikle teorik bir araç olarak kaldı; 2010'larda ölçeklenebilir çıkarım algoritmalarının — varyasyonel EM ve MCMC — geliştirilmesiyle pratik ilgi gördü. Derece Düzeltmeli SBM, derece heterojenliği sorununu ele almak için Karrer ve Newman (2011) tarafından tanıtıldı. Lee ve Wilkinson'ın 2019'daki Applied Network Science dergisindeki incelemesi, ekili bölüm modelleri, karma üyelikli SBM ve hiyerarşik varyantları kapsayan uzantı ailesini pekiştirdi. Bugün SBM ve türevleri, topluluk tespiti ve grafik kümelemesi için referans olasılıksal çerçevedir.
Ne zaman kullanılır?
En az 50 düğümlü bir ağınız varsa ve grupların yoğun klikler olması gerektiğini varsaymadan gizli grup yapısını keşfetmek istiyorsanız Stokastik Blok Modelini kullanın. Yönlü veya yönsüz grafikler, ağırlıklı veya ağırlıksız grafikler için uygundur ve keşifsel olduğu kadar sınıflandırma görevleri için de elverişlidir. Düğüm dereceleri önemli ölçüde değiştiğinde DCSBM varyantı tercih edilir. Grafik 20'den az düğüme sahipse, topluluk yapısı güvenilir bir şekilde tahmin edilemez ve bunun yerine daha basit tanımlayıcı metrikler kullanılmalıdır. Varsayımlar: blok üyelikleri gizlidir ve gözlemlenmez; blok bağlantı matrisinin her blok çifti içinde homojen olduğu varsayılır; ve K keyfi olarak sabitlenmek yerine BIC veya Bayes faktörü ile seçilmelidir.
Sınırlar ve dikkat edilmesi gerekenler
- Güvenilir blok tahmini için en az yaklaşık 50 düğüm gerektirir; çok küçük grafikler kararsız çözümler üretir.
- Büyük grafikler için çıkarım hesaplama açısından pahalıdır: varyasyonel EM veya MCMC gereklidir ve yakınsama garanti edilmez.
- Temel SBM'nin blok çiftleri içindeki homojenlik varsayımı, blok içi bağlantı oranları değiştiğinde bozulur — DCSBM bunu hafifletir ancak tamamen ortadan kaldırmaz.
- BIC veya Bayes faktörü aracılığıyla blok seçimi, grafik zayıf ayrılmış topluluklara sahipse yine de eksik veya fazla bölümlendirmeye neden olabilir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Keyfi parametre seçimlerinden kaçınarak BIC veya Bayes faktörü aracılığıyla model seçimine izin veren prensipli olasılıksal çerçeve.
- Algoritmik yöntemlerin yoğun-klik varsayımının ötesinde, topluluklar, çekirdek-çevre, iki parçalı ve hiyerarşik gibi geniş bir yapısal örüntü yelpazesini barındırır.
- Derece Düzeltmeli varyant, blok atamalarını bozmadan heterojen derece dağılımlarına ve merkezlere sahip grafikleri ele alır.
- Sonsal üyelik olasılıkları sağlayarak, kesin bölümlendirmeler yerine yumuşak veya belirsiz düğüm atamalarına olanak tanır.
Uygulama alanları
- Sosyal ve doğa bilimlerindeki atıf ve işbirliği ağlarında araştırma topluluklarını tespit etmek.
- Protein-protein etkileşimi ve gen eş-ifade grafikleri gibi biyolojik ağlarda fonksiyonel modülleri tanımlamak.
- İşlemsel ve finansal ağlarda müşteri segmentlerini veya dolandırıcılık halkalarını keşfetmek.
- Kurumlararası veya ülkelerarası ticaret ağlarında çekirdek-çevre yapısını karakterize etmek.
- SBM tarafından üretilen sentetik grafikleri gerçek veri olarak kullanarak diğer topluluk tespit algoritmalarını karşılaştırmak ve değerlendirmek.
Nasıl çalışır?
Nasıl çalışır?
Analist, blok sayısı K için aday bir aralık belirler ve bir varyant seçer: temel SBM, blok içi homojen derece dağılımı varsayarken, Derece Düzeltmeli SBM (DCSBM), merkezleri ve heterojen derece dizilerini ele almak için düğüm düzeyinde derece parametreleri ekler. Varyant seçimi, gözlemlenen grafiğin derece dağılımına göre yapılır.
Komşuluk matrisi verildiğinde, model, bir çıkarım algoritması kullanarak blok üyeliklerini ve K×K boyutunda bir bağlantı olasılıkları matrisini tahmin eder. Küçük ve orta ölçekli grafikler için kesin maksimizasyon uygulanabilir; büyük grafikler için çıkarımı yönetilebilir kılmak amacıyla varyasyonel Beklenti-Maksimizasyon (variational EM) veya Markov Zinciri Monte Carlo (MCMC) örneklemesi kullanılır.
Blok sayısı K önceden bilinmez ve verilerden seçilmelidir. Tercih edilen seçim kriterleri, her ikisi de model karmaşıklığını cezalandıran ve uyumu tutumlulukla en iyi dengeleyen K'yi seçen Bayes Bilgi Kriteri (BIC) ve Bayes faktörüdür. Minimum Tanımlama Uzunluğu (MDL) prensibi, graph-tool uygulamasının temelini oluşturur.
Optimal K ve blok atamaları belirlendikten sonra, yapıyı karakterize etmek için blok bağlantı matrisi incelenir: assortatif bloklar topluluklara, disassortatif bloklar iki parçalı (bipartite) benzeri örüntülere ve karışık profiller çekirdek-çevre düzenlemelerine karşılık gelir. Düğüm üyelikleri, çıkarım algoritmasının sağladığı durumlarda sonsal olasılıklarla birlikte rapor edilir.
Sık yapılan hatalar
- K'yi BIC veya Bayes faktörü ile seçmek yerine keyfi olarak sabitlemek güvenilmez bölümlendirmeler üretir — her zaman prensipli bir model seçim kriteri kullanın.
- Temel SBM'yi heterojen bir derece dizisine (merkezler, üstel kanun derece dağılımı) sahip bir grafiğe uygulamak blok sayısı tahminlerini şişirir; bunun yerine DCSBM kullanın.
- Sonsal dağılım yaygın olduğunda blok üyeliğini kesin olarak kabul etmek güveni abartır — mevcut olduğunda belirsizliği rapor edin.
- SBM çıktısını gerçek topluluklarla karıştırmak: model, sosyolojik olarak anlamlı gruplar değil, istatistiksel olarak makul gizli yapıyı bulur. Alan bilgisiyle doğrulayın.
- 20'den az düğümde SBM çalıştırmak dejenere çözümler üretir — küçük grafikler için tanımlayıcı ağ metriklerine veya basit topluluk tespitine geri dönün.
Sık sorulan sorular
Stokastik Blok Modeli, modülerlik tabanlı topluluk tespitinden nasıl farklıdır?
Modülerlik maksimizasyonu (örneğin, Louvain, Leiden), örtük olarak assortatif, yaklaşık olarak eşit büyüklükteki toplulukları varsayan ve küçük toplulukların tespitini engelleyen bilinen bir çözünürlük sınırına sahip sezgisel bir amacı optimize eder. SBM, açık varsayımlara sahip üretken bir olasılıksal modeldir; blok sayısı sezgisel optimizasyon yerine model seçimi (BIC veya Bayes faktörü) ile seçilir ve modülerlik tabanlı yöntemlerin kaçırdığı disassortatif ve çekirdek-çevre yapılarını tespit edebilir.
Temel SBM yerine DCSBM'yi ne zaman kullanmalıyım?
Düğüm derece dağılımı heterojen olduğunda DCSBM kullanın — örneğin, az sayıda merkezin kenarların büyük bir kısmını oluşturduğu durumlarda veya derece dizisi yaklaşık bir üstel kanunu takip ettiğinde. Temel SBM, bir blok içindeki tüm düğümleri değiştirilebilir olarak ele alır, bu da merkezlerin kendi sahte bloklarına çekilmesine neden olur. DCSBM, yapısal konumu dereceden ayıran bir derece düzeltme terimi ekleyerek bu tür grafiklerde daha yorumlanabilir blok atamaları üretir.
Blok sayısı K'yi nasıl seçerim?
Bir dizi K değeri için modelleri uydurun ve BIC'yi minimize eden veya Bayes faktörünü maksimize eden (veya eşdeğer olarak tanımlama uzunluğunu minimize eden) değeri seçin. K'yi grafiğin görsel incelemesine veya ön beklentilere dayanarak seçmeyin. Çoğu uygulama (graph-tool, R'deki blockmodels) bu aramayı otomatikleştirir. Hassasiyet analizi — K bir birim değiştirildiğinde niteliksel blok yapısının değişip değişmediğini kontrol etmek — de önerilir.
SBM'nin güvenilir olması için minimum ağ boyutu nedir?
Kayıt, güvenilir çıkarım için minimum 50 düğüm belirtir. 20'den az düğümle model anlamlı topluluk yapısını tanımlayamaz ve gürültüyü uydurur — bunun yerine tanımlayıcı ağ istatistiklerini veya basit topluluk tespitini kullanın. 20 ila 50 düğüm arasındaki sonuçlar keşifsel olarak ele alınmalı ve dikkatle yorumlanmalıdır.
İlgili yöntemler
Kaynaklar
Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.
DOI kaynağını açKopyalandı.Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.
DOI kaynağını açKopyalandı.