Modülerlik Analizi
- Ortaya koyan
- Newman, M. E. J. & Girvan, M.
- Yıl
- 2004
- Tür
- Community detection / graph partitioning
- Aile
- Network science
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Modülerlik analizi, Newman ve Girvan tarafından 2004 yılında formüle edilen bir ağ bilimi yöntemidir.
Kenarların gruplar içinde rastlantısal olarak beklenenden daha yoğun olup olmadığını ölçerek grafiklerdeki topluluk yapısını tespit eder. Skaler kalite indeksi Q, düğümleri tutarlı kümelere ayıran algoritmalara rehberlik eder ve bu da onu sosyal, biyolojik ve teknolojik ağlarda topluluk tespiti için en yaygın kabul gören çerçeve haline getirir.
Yöntemin mantığı
Bir ağın tüm kenarlarını, her düğümün derecesini koruyarak rastgele yeniden bağlarsanız, gerçek toplulukları olmayan bir boş model elde edersiniz. Modülerlik, gerçek kenar dağılımını bu boş modelle karşılaştırır: eğer bir bölümleme, boş modelin öngördüğünden çok daha fazla grup içi kenar üretiyorsa, Q yüksek çıkar ve bu da gerçek bir topluluk yapısına işaret eder. Bir iyileştirici, olası bölümlemeler uzayında Q'yu maksimize eden ayrımı arar ve analistin topluluk sayısını önceden belirtmesini gerektirmeden ağ yapısının ima ettiği doğal gruplamaları ortaya çıkarır.
Tarih
Modülerlik fonksiyonu Q, Newman ve Girvan tarafından 2004 yılında bir dizi topluluk tespit tekniğinin bir parçası olarak tanıtıldı. Newman'ın 2006 tarihli PNAS makalesi, modülerlik optimizasyonuna spektral yaklaşımı formüle etti ve Louvain yöntemi (Blondel vd., 2008), büyük ölçekli optimizasyonu pratik hale getirerek modülerlik analizini sosyoloji, biyoloji ve bilgisayar bilimleri genelinde popülerleştirdi. Çözünürlük sınırı problemi Fortunato ve Barthélemy tarafından 2007'de tanımlandı ve Leiden (Traag vd., 2019) gibi, zayıf bağlantılı toplulukları da düzelten geliştirilmiş algoritmaları motive etti.
Ne zaman kullanılır?
Bir grafik olarak temsil edilebilen ilişkisel bir veri kümeniz olduğunda ve sayılarını önceden belirtmeden tutarlı alt grupları tanımlamak istediğinizde modülerlik analizini kullanın — örneğin, sosyal ağlarda grupları, protein-etkileşim ağlarında fonksiyonel modülleri veya atıf ağlarında konu kümelerini tespit etmek için. En az birkaç düzine düğümü ve açıkça önemsiz olmayan bir kenar yapısı olan yönsüz ve yönlü grafikler için uygundur. Ağ çok küçük olduğunda (yaklaşık 30'dan az düğüm) veya neredeyse tamamlandığında, kenar ağırlıkları basit bir ikili boş modelin göz ardı ettiği kritik bilgileri taşıdığında, toplulukların önemli ölçüde çakıştığı bilindiğinde (bunun yerine çakışan-topluluk yöntemlerini kullanın) veya bir optimizasyon sezgisinden ziyade istatistiksel olarak test edilmiş sınırlar gerektiğinde kullanmayın.
Sınırlar ve dikkat edilmesi gerekenler
- Çözünürlük sınırı: modülerlik optimizasyonu, ağ boyutu tarafından belirlenen bir ölçekten daha küçük toplulukları sistematik olarak tespit edemez, gerçekten farklı küçük modülleri birleştirir.
- NP-zor kesin optimizasyon, pratikte yalnızca yaklaşımların kullanıldığı ve stokastik algoritmaların farklı çalışmalarının farklı bölümlemeler üretebileceği anlamına gelir.
- Boş model, ağır kuyruklu derece dağılımlarına veya hiyerarşik yapıya sahip ağlar için uygun olmayabilecek bir konfigürasyon modeli (Erdos-Renyi benzeri derece dizisi) varsayar.
- Sert topluluk sınırları, gerçek dünyadaki çakışan üyelikleri temsil edemez.
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ı önceden belirtmeye gerek yoktur; bölümleme verilerden ortaya çıkar.
- Farklı bölümlemelerin veya ağların doğrudan karşılaştırılmasını kolaylaştıran tek bir skaler Q sağlar.
- Hızlı yaklaşık algoritmalar (Louvain, Leiden) milyonlarca düğüme ölçeklenebilir.
- Uygun uzantılarla yönsüz, yönlü ve ağırlıklı ağlara uygulanabilir.
- Standart kütüphanelerde (NetworkX, igraph, Gephi) yaygın olarak uygulanmıştır, kullanım engelini azaltır.
Uygulama alanları
- Çevrimiçi ve çevrimdışı sosyal ağlarda sosyal grupları, yankı odalarını veya işbirliği kümelerini tespit etmek.
- Protein-protein etkileşimi ve gen-düzenleyici grafikler gibi biyolojik ağlarda fonksiyonel modülleri tanımlamak.
- Atıf ve ortak yazarlık ağlarında tematik veya disipliner kümeleri ortaya çıkarmak.
- Pazarlama ve öneri sistemlerinde müşteri veya ürün ağlarını segmentlere ayırmak.
- Dayanıklılık analizi için altyapı ağlarını (elektrik şebekeleri, ulaşım) bölümlemek.
- Hesaplamalı dilbilimde köprü veya birlikte oluşum grafiklerinde konu topluluklarını keşfetmek.
Nasıl çalışır?
Nasıl çalışır?
Ağ, bir komşuluk matrisi A (veya eşdeğer kenar listesi) olarak temsil edilir; burada A_ij girişi, i ve j düğümleri bağlıysa 1'e, aksi takdirde 0'a eşittir. Düğüm dereceleri (k_i, k_j) ve toplam kenar sayısı m, modülerlik formülüne girdi olarak hesaplanır.
Modülerlik skoru Q, topluluklar içine düşen kenarların oranı eksi bir konfigürasyon-model boş modeli (dereceleri koruyan rastgele yeniden bağlama) altında beklenen oran olarak tanımlanır. Q yaklaşık -0.5 ile 1 arasında değişir; yaklaşık 0.3'ün üzerindeki değerler anlamlı bir topluluk yapısını gösterir.
Formül
Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)Tüm olası bölümlemeler üzerinde kapsamlı arama NP-zor olduğundan, pratik algoritmalar optimumu yaklaşık olarak bulur. Yaygın yaklaşımlar arasında Louvain yöntemi (açgözlü kümelenme), Leiden algoritması (düzeltilmiş ve daha hızlı bir varyant), modülerlik matrisinin özvektörlerini kullanan spektral optimizasyon ve benzetimli tavlama bulunur.
Her düğüm, genel bölümleme için Q'yu maksimize eden topluluğa atanır. Algoritma tipik olarak hiyerarşik bir dendrogram üretir ve bu da topluluk yapısının kaba süper-topluluklardan ince taneli kümelere kadar birden çok çözünürlükte incelenmesine olanak tanır.
Ortaya çıkan bölümleme, nihai Q değeri, birden çok algoritma çalışması boyunca kararlılık kontrolleri ve eğer zemin gerçekliği mevcutsa, normalize edilmiş karşılıklı bilgi gibi harici metriklerle değerlendirilir. Düşük Q veya çalışmalar arasında kararsız sonuçlar, zayıf veya mevcut olmayan bir topluluk yapısını gösterir.
Sık yapılan hatalar
- Birden çok çalışma veya rastgele tohum arasında kararlılığı kontrol etmeden stokastik bir iyileştiricinin tek bir çalışmasını kabul etmek.
- Çözünürlük sınırını göz ardı etmek ve birleştirilmiş büyük bir topluluğun gerçekten homojen olduğu sonucuna varmak.
- Boş modeli kenar ağırlıklarını içerecek şekilde uyarlamadan ağırlıklı bir ağ üzerinde ikili modülerlik kullanmak.
- Ağ türü ve boyutu dikkate alınmadan Q'yu 0.3'ün üzerinde 'iyi' bir yapı için evrensel bir eşik olarak ele almak.
- Optimizasyon kalitesini (yüksek Q) yorumlayıcı geçerlilikle karıştırmak — topluluklar yine de esaslı bir şekilde incelenmelidir.
Sık sorulan sorular
Q'nun iyi bir değeri nedir?
Yaklaşık 0.3'ün üzerindeki Q, anlamlı topluluk yapısını gösterdiği yaygın olarak belirtilir, ancak bu eşik ağ türüne ve boyutuna bağlıdır. Zayıf yapıya sahip çok büyük ağlar 0.1'e yakın Q'ya sahip olabilir ve yine de yorumlanabilir kümeler ortaya çıkarabilirken, küçük yoğun ağlar 0.5'in üzerinde Q'ya ulaşabilir. Yalnızca Q'ya güvenmek yerine toplulukları her zaman esaslı bir şekilde inceleyin.
Q'yu maksimize etmek için hangi algoritmayı kullanmalıyım?
Leiden algoritması (Traag vd., 2019) şu anda önerilen varsayılandır: orijinal Louvain yönteminden daha hızlıdır ve zayıf bağlantılı topluluklar üretme eğilimini düzeltir. Çok büyük grafikler için Louvain pratik bir seçenek olmaya devam etmektedir. Daha küçük ağlarda tekrarlanabilir, deterministik sonuçlara ihtiyacınız olduğunda spektral yöntemler tercih edilebilir.
Modülerlik analizi çakışan toplulukları tespit edebilir mi?
Standart modülerlik optimizasyonu, her düğümü tam olarak bir topluluğa atar ve çakışmayı tespit edemez. Düğümlerin aynı anda birden fazla gruba ait olmasını bekliyorsanız, bunun yerine klik-sızma yöntemi veya negatif olmayan matris çarpanlara ayırma yaklaşımları gibi çakışan-topluluk yöntemlerini kullanın.
Çözünürlük sınırı analizimi nasıl etkiler?
Modülerlik optimizasyonu, yaklaşık sqrt(m) kenardan daha küçük toplulukları daha büyük olanlarla birleştirme eğilimindedir. Bu, ağ büyük olduğunda gerçek küçük kümelerin görünmez olabileceği anlamına gelir. Bunu hafifletmek için çözünürlük parametresini (Leiden ve bazı Louvain uygulamalarında mevcuttur) değiştirin ve birkaç çözünürlük değeri boyunca bölümlemeleri karşılaştırın.
Yönlü bir ağa modülerlik analizi uygulamalı mıyım?
Evet, igraph gibi araçlarda uygulandığı gibi hem iç hem de dış derece dizilerini koruyan uyarlanmış bir boş modelle. Yönlü bir grafiğe safça uygulanan yönsüz modülerlik, ilişkilerin asimetrisini göz ardı eder ve yanıltıcı bölümlemeler üretebilir.
İlgili yöntemler
Kaynaklar
Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.
DOI kaynağını açKopyalandı.Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582.
DOI kaynağını açKopyalandı.