Yumuşak konfigürasyon modeli - Soft configuration model

Ağ bilimi
Teori
Grafik Karmaşık ağ Bulaşma Küçük dünya Ölçeksiz Topluluk yapısı Süzülme Evrim Kontrol edilebilirlik Grafik çizimi Sosyal sermaye Bağlantı analizi Optimizasyon Mütekabiliyet Kapanış Homofilik Geçişlilik Tercihli ek Denge teorisi Ağ etkisi Sosyal etki
Ağ türleri
Bilgilendirici (bilgi işlem) Telekomünikasyon Ulaşım Sosyal Bilimsel işbirliği Biyolojik Yapay sinir Birbirine bağımlı Anlamsal Mekansal Bağımlılık Akış Çip üzerinde
Grafikler
Özellikleri Clique Bileşen Kesmek Döngü Veri yapısı Kenar Döngü Komşuluk Yol Köşe Bitişiklik listesi  / matris Sıklık listesi  / matris Türler Bipartit Tamamlayınız Yönetmen Aşırı Çok Rastgele Ağırlıklı
Metrikler Algoritmalar
Merkeziyet Derece Arasılık Yakınlık PageRank Motif Kümeleme Derece dağılımı Çeşitlilik Mesafe Modülerlik Verimlilik
Modeller
Topoloji Rastgele grafik Erdős – Rényi Barabási-Albert Spor modeli Watt-Strogatz Üstel rastgele (ERGM) Rastgele geometrik (RGG) Hiperbolik (HGN) Hiyerarşik Stokastik blok Maksimum entropi Yumuşak konfigürasyon LFR Benchmark Dinamikler Boole ağı ajan tabanlı Salgın / SIR
Listeler Kategoriler
Konular Yazılım Ağ bilimcileri Kategori: Ağ teorisi Kategori: Grafik teorisi
v t e

Uygulanan matematik olarak, yumuşak yapılandırma modeli (SCM) a, rastgele grafiktir model konusu maksimum entropi ilkesi üzerine kısıtlamalar altında beklentisi içinde derecesi dizisinin örnek bir grafik . Oysa yapılandırma modeli (CM) homojen numuneleri, belirli bir derecede dizisinin rastgele grafikler, SCM sadece tüm ağ gerçekleşmeleri içinde ortalama belirtilen derecesi dizisini korur; bu anlamda SCM, CM'ninkilere göre çok gevşek kısıtlamalara sahiptir ("keskin" kısıtlamalar yerine "yumuşak" kısıtlamalar). Boyut grafikleri için SCM, herhangi bir büyüklükteki grafiği örneklemek için sıfır olmayan bir olasılığa sahiptir , oysa CM yalnızca tam olarak öngörülen bağlantı yapısına sahip grafiklerle sınırlıdır. ${\ displaystyle n}$${\ displaystyle n}$

Model formülasyonu

SCM, (büyüklükteki grafikler kümesi) üzerinde bir olasılık dağılımı üreten köşeleri ( ) etiketli olan rastgele grafiklerin istatistiksel bir topluluğudur . Topluluğu dayatılan , yani bu, kısıtlamaları topluluğu ortalama bir derece tepe noktası belirlenen bir değere eşit olan herkes için . Model, boyutu ve beklenen derece sırası ile tamamen parametreleştirilmiştir . Bu kısıtlamalar hem yereldir (her köşe ile ilişkili bir kısıt) hem de yumuşaktır (belirli gözlemlenebilir miktarların toplu ortalamasına ilişkin kısıtlamalar) ve bu nedenle çok sayıda kısıtlamaya sahip kanonik bir topluluk oluşturur . Koşullar tarafından grup dayatılan Lagrange çarpanları (bakınız maksimum entropi rastgele grafik modeli ). ${\ displaystyle G}$${\ displaystyle n}$${\ displaystyle n = | V (G) |}$${\ displaystyle \ {v_ {j} \} _ {j = 1} ^ {n} = V (G)}$${\ displaystyle {\ mathcal {G}} _ {n}}$${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle k_ {j}}$${\ displaystyle v_ {j}}$${\ displaystyle {\ widehat {k}} _ {j}}$${\ displaystyle v_ {j} \ V (G)}$${\ displaystyle n}$${\ displaystyle \ {{\ widehat {k}} _ {j} \} _ {j = 1} ^ {n}}$${\ displaystyle \ langle k_ {j} \ rangle = {\ widehat {k}} _ {j}}$

Olasılık dağılımının türetilmesi

Bir grafik üreten SCM'nin olasılığı , Gibbs entropisinin kısıtlamalara ve normalizasyona tabi olarak maksimize edilmesiyle belirlenir . Bu , aşağıdaki çoklu kısıtlamalı Lagrange işlevini optimize etmek anlamına gelir : ${\ displaystyle \ mathbb {P} _ {\ text {SCM}} (G)}$${\ displaystyle G}$ ${\ displaystyle S [G]}$${\ displaystyle \ langle k_ {j} \ rangle = {\ widehat {k}} _ {j}, \ j = 1, \ ldots, n}$${\ displaystyle \ sum _ {G \ {\ mathcal {G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} (G) = 1}$

${\ displaystyle {\ begin {align}} & {\ mathcal {L}} \ left (\ alpha, \ {\ psi _ {j} \} _ {j = 1} ^ {n} \ sağ) \\ [6pt ] = {} & - \ sum _ {G \ içinde {\ mathcal {G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} (G) \ log \ mathbb {P} _ { \ text {SCM}} (G) + \ alpha \ left (1- \ sum _ {G \ in {\ mathcal {G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} ( G) \ right) + \ sum _ {j = 1} ^ {n} \ psi _ {j} \ left ({\ widehat {k}} _ {j} - \ sum _ {G \ in {\ mathcal { G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} (G) k_ {j} (G) \ sağ), \ end {hizalı}}}$

burada ve vardır ile tespit edilecek çarpanları kısıtlamaları (normalleştirme ve beklenen derecesi sekansı). Keyfi bir verime göre yukarıdakinin türevini sıfırlamak${\ displaystyle \ alpha}$${\ displaystyle \ {\ psi _ {j} \} _ {j = 1} ^ {n}}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ displaystyle \ mathbb {P} _ {\ text {SCM}} (G)}$${\ mathcal {G}} _ {n}} içinde {\ displaystyle G \$

${\ displaystyle 0 = {\ frac {\ kısmi {\ mathcal {L}} \ sol (\ alpha, \ {\ psi _ {j} \} _ {j = 1} ^ {n} \ sağ)} {\ kısmi \ mathbb {P} _ {\ text {SCM}} (G)}} = - \ log \ mathbb {P} _ {\ text {SCM}} (G) -1- \ alpha - \ sum _ {j = 1} ^ {n} \ psi _ {j} k_ {j} (G) \ \ Rightarrow \ \ mathbb {P} _ {\ text {SCM}} (G) = {\ frac {1} {Z} } \ exp \ left [- \ sum _ {j = 1} ^ {n} \ psi _ {j} k_ {j} (G) \ sağ],}$

sabit olmak bölümleme işlevi dağılımı normale; yukarıdaki üstel ifade herkes için geçerlidir ve dolayısıyla olasılık dağılımıdır. Dolayısıyla , aşağıdaki eşdeğer ifadelerle beklenen derece dizisiyle ilişkili olan, tarafından parametreleştirilmiş üstel bir ailemiz var : ${\ displaystyle Z: = e ^ {\ alpha +1} = \ sum _ {G \ in {\ mathcal {G}} _ {n}} \ exp \ left [- \ sum _ {j = 1} ^ { n} \ psi _ {j} k_ {j} (G) \ sağ] = \ prod _ {1 \ leq i <j \ leq n} \ left (1 + e ^ {- (\ psi _ {i} + \ psi _ {j})} \ sağ)}$${\ mathcal {G}} _ {n}} içinde {\ displaystyle G \$${\ displaystyle \ {\ psi _ {j} \} _ {j = 1} ^ {n}}$${\ displaystyle \ {{\ widehat {k}} _ {j} \} _ {j = 1} ^ {n}}$

${\ displaystyle \ langle k_ {q} \ rangle = \ sum _ {G \ in {\ mathcal {G}} _ {n}} k_ {q} (G) \ mathbb {P} _ {\ text {SCM} } (G) = - {\ frac {\ kısmi \ log Z} {\ kısmi \ psi _ {q}}} = \ toplam _ {j \ neq q} {\ frac {1} {e ^ {\ psi _ {q} + \ psi _ {j}} + 1}} = {\ widehat {k}} _ {q}, \ q = 1, \ ldots, n.}$

Referanslar