Lancichinetti-Fortunato-RADICCHI kriter - Lancichinetti–Fortunato–Radicchi benchmark

Ağ bilimi
teori
grafik Karmaşık ağ bulaşma Küçük dünya Ölçek içermeyen Topluluk yapısı Süzülme Evrim Kontrol edilebilirlik Grafik Çizimi Sosyal sermaye Bağlantı analizi Optimizasyon Karşılıklılık kapatma türlük geçişlilik Tercihli eki Denge teorisi Ağ etkisi Sosyal etki
Ağ türleri
Bilgi (bilgisayar) Telekomünikasyon taşıma Sosyal Bilimsel işbirliği Biyolojik Yapay sinir birbirine bağlı anlamsal uzaysal Bağımlılık Akış on-Chip
Grafikler
Özellikler klik Bileşen Kesmek Çevrim Veri yapısı kenar döngü Komşuluk yol tepe Komşuluk listesi  / matris Sıklık listesi  / matris Türleri ikili Tamamlayınız Yönetmen Aşırı Çok rasgele Ağırlıklı
Metrik Algoritmalar
mERKEZİLİĞİ derece Betweenness Yakınlık PageRank motif kümelenme Derece dağılımı Assortativity Mesafe Modülarite verim
Modeller
Topoloji Rastgele grafik Erdos-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 yapılandırma LFR Benchmark dinamik Boole ağ ajan tabanlı Salgın / SIR
Listeler Kategoriler
Başlıklar Yazılım Ağ bilim adamları Kategori: Ağ teorisi Kategori: Grafik teorisi
v t e

Lancichinetti-Fortunato-RADICCHI (LFR) kriter oluşturan bir algoritmadır kriter ağları (gerçek dünya ağları benzeyen yapay ağlar). Onlar sahip önsel bilinen topluluklar ve farklı topluluk algılama yöntemleri karşılaştırmak için kullanılır. Diğer yöntemlere göre LFR avantajı oluşturuyor olmasıdır heterojenlik dağılımları düğüm derece ve toplum boyutlarda.

algoritma

Düğüm derece ve toplum boyutları göre dağıtılır güç hukuku farklı üstellerle. LFR derecesi ve toplum boyutu ikisine de sahip olduğunu varsayar güç yasası dağılımları farklı üstellerle, ve sırasıyla. düğüm sayısı, ortalama açısıdır . Bir karıştırma parametresi vardır karşılaştırmalı düğüm ait bir eden ait olmayan bir düğüm komşu düğümlerin ortalama fraksiyonudur. Bu parametre, toplumlar arasında olan kenarların bölümünü kontrol etmektedir. Böylece, ağda gürültü miktarını yansıtır. Aşırı anda, ne zaman eğer tüm bağlantıları, topluluk bağlantıları içindedir tüm bağlantıları farklı topluluklara mensup düğümler arasında bulunmaktadır.${\ Displaystyle \ y}$${\ Displaystyle \ p}$${\ Displaystyle K}$${\ Displaystyle \ langle k \ rangle}$${\ Displaystyle \ u}$${\ Displaystyle \ u = 0}$${\ Displaystyle \ u = 1}$

Bir aşağıdaki adımlarda bir LFR kriter ağı oluşturabilir.

1 Adım: üs ile bir güç yasası dağılımı aşağıdaki düğümlerle bir ağ oluşturmakve dağıtım aşırı seçmekveortalama derecesi istenen almak. ${\ Displaystyle \ y}$${\ Displaystyle k _ {\ dak}}$${\ Displaystyle k _ {\ max}}$${\ Displaystyle \ langle k \ rangle}$

Aşama 2: fraksiyon ise, her düğümün bağlantıların fraksiyonu, aynı toplumun düğümleri ilediğer düğümler ile. ${\ Displaystyle (mu \ 1-)}$${\ Displaystyle \ u}$

3. Adım: üs ile bir güç yasası dağılımından topluluk boyutlarını oluşturun. Her boyutta toplamı eşit olmalıdır. Minimum ve maksimum topluluğu boyutlarıveher yalıtımsız düğüm, en az bir topluluk içinde olduğu şekilde eden tanımını karşılaması gerekmektedir: ${\ Displaystyle \ p}$${\ Displaystyle K}$${\ Displaystyle s _ {\ dak}}$${\ Displaystyle s _ {\ maks}}$

${\ Displaystyle s _ {\ dak}> k _ {\ dak}}$

${\ Displaystyle s _ {\ max}> k _ {\ max}}$

Adım 4: Başlangıçta, düğüm topluluklara atanır. Sonra, her düğüm rasgele bir topluluk atanır. Sürece yeni bir düğüm topluluk eklendiğinde topluluk boyutunu aşmaması toplum içinde komşu düğümlerin sayısı olarak, aksi dışarıda kalır. Aşağıdaki tekrarlamalar yılında “evsiz” düğüm rastgele bazı topluluk atanır. Bu topluluk tamsa boyutu tükendiğinde, yani, bu topluluğun rasgele seçilen bir düğüm bağlantısız olmalı. Tüm topluluklar eksiksiz ve tüm düğümler en az bir topluluğa ait zaman iterasyon durdurun.

Adım 5: aynı düğüm derece tutmak düğümleri sadece her bir düğüm için eden dış bağlantıların sayısı karıştırma parametresi yaklaşık olarak eşit olacak şekilde, iç ve dış bağlantılar kısmını etkileyen yeni kablo uygulamak.${\ Displaystyle \ u}$

Test yapmak

Bir düşünün bölümü örtüşmeyen topluluklara. Her tekrarında rasgele seçilen düğümlerin toplumların izleyin rasgele seçilmiş düğüm topluluktan olma olasılığını temsil dağılımı . Bazı topluluk bulgu algoritması tarafından tahmin ve sahip olduğu aynı ağın bir bölümü düşünün dağılımı. Kıyaslama bölümü vardır dağılımı. Eklem dağıtımıdır . Bu iki bölümlerin benzerlik normalize tarafından yakalanır karşılıklı bilgi . ${\ Displaystyle s (C)}$${\ Displaystyle Cı}$${\ Displaystyle (p C_ {2})}$${\ Displaystyle (p C_ {1})}$${\ Displaystyle (p C_ {1}, C_ {2})}$

${\ Displaystyle I_ {n} = {\ frac {\ toplamı _ {C_ {1}, C_ {2}} s (C_ {1}, C_ {2}) \ log _ {2} {\ frac {s ( C_ {1}, C_ {2})} + {s (C_ {1}) p (C_ {2})}}} {{\ frac {1} {2}} H (\ {s (C_ {1} ) \}) + {\ frac {1} {2}} H (\ {s (C_ {2}) \})}}}$

Eğer kriter ve algılanan bölümleri aynıdır ve eğer sonra birbirlerinden bağımsızdır.${\ Displaystyle I_ {n} = 1}$${\ Displaystyle I_ {n} = 0}$

Referanslar