Ağ Yayılım Modelleri — SIR, SIS ve Bağımsız Kaskat
- Ortaya koyan
- Kermack & McKendrick (SIR/SIS, 1927); Kempe, Kleinberg & Tardos (Independent Cascade, 2003)
- Yıl
- 1927 (epidemiological compartmental); 2003 (social influence cascade)
- Tür
- Stochastic / deterministic simulation on graphs
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Ağ yayılım modelleri, bilgi, hastalık veya yeniliğin bağlı bir sistemde nasıl yayıldığını simüle eden bir grup kompartıman ve olasılıksal çerçevedir.
Kermack ve McKendrick'in (1927) matematiksel epidemiyolojisine dayanan SIR ve SIS modelleri, düğümleri durumlara ayırır ve temas oranları ile iyileşme olasılıklarının yönlendirdiği geçişleri izler. Kempe, Kleinberg ve Tardos (2003) tarafından biçimlendirilen Bağımsız Kaskat ve Doğrusal Eşik modelleri, bu mantığı sosyal etkiye genişleterek, aktivasyonun bir ağda komşudan komşuya nasıl yayıldığını modeller.
Yöntemin mantığı
Bir okulda yayılan bir söylentiyi düşünün. Bir öğrenci bunu duyduğunda, bunu her arkadaşına belirli bir olasılıkla yayabilir, zaten duymuş olan arkadaşların bunu tekrar duymasına gerek yoktur ve sonunda söylenti herkese ulaşır veya ortadan kaybolur. Ağ yayılım modelleri tam olarak bu süreci biçimlendirir: her düğüm bir durumda (duyarlı, enfekte, iyileşmiş veya basitçe aktif/pasif) bulunur ve her zaman adımında, iletim olasılığına göre komşularına sinyali yayar veya bir temel duruma geri iyileşir. Temel içgörü, ağın yapısının — kimin kime bağlı olduğu — sonucunu iletim oranının kendisi kadar şekillendirmesidir.
Tarih
Ağ yayılımının matematiksel temelleri, adi diferansiyel denklemler sistemi olarak SIR çerçevesini tanıtan ve epidemik geçişleri tanımlayan dönüm noktası niteliğindeki 1927 tarihli makalelerinde Kermack ve McKendrick tarafından atılmıştır. SIS varyantı, bağışıklığın geçici olduğu endemik hastalıklar için bunu genelleştirmiştir. Bu ortalama alan yaklaşımları, nüfusu homojen karışımlı olarak ele almıştır. Farklı düğümlerin farklı sayıda temasa sahip olmasına izin veren açık ağ yapısına geçiş, ölçek-serbest ağ modellerinin (Barabási ve Albert, 1999) merkezlerin bulaşmada orantısız bir rol oynadığını ortaya çıkardığı 1990'ların sonları ve 2000'lerin başlarında hesaplamalı epidemiyolojinin merkezine yerleşti. Kempe, Kleinberg ve Tardos (2003), Bağımsız Kaskat ve Doğrusal Eşik modelleri altında etki maksimizasyonu problemini biçimlendirerek, yayılım teorisini sosyal bilişim ve pazarlamadaki algoritmik problemlerle ilişkilendirdi. O zamandan beri alan, çok katmanlı ağlara, zamansal temas dizilerine ve gerçek epidemi veya sosyal medya veri kümeleri kullanılarak veri odaklı parametre tahminine genişlemiştir.
Ne zaman kullanılır?
Ağ yayılım modelleri, ilişkisel bir veri kümeniz olduğunda (veya makul bir ağ oluşturabiliyorsanız) ve bir durumun — hastalık, bilgi, davranış, yenilik — üzerinde nasıl yayıldığını tahmin etmek veya açıklamak istediğinizde uygundur. İkili veya sürekli düğüm-durum değişkenlerinde kesitsel veya zaman serisi yapılarında tahmin, açıklama ve öngörme görevlerine uygundurlar. Ağın en az 20 düğümü olmalıdır; daha az düğümle stokastik dinamikler anlamlı desenler üretmez. İletim ve iyileşme oranları verilerden tahmin edilebilir veya literatürden kalibre edilebilir olmalıdır. Ağ yapısı mevcut değilse veya yalnızca toplu (ilişkisel olmayan) veriler varsa, grafik katmanı olmayan kompartıman adi diferansiyel denklem modelleri daha basit bir alternatiftir.
Sınırlar ve dikkat edilmesi gerekenler
- Bilinen veya tahmin edilen bir ağ yapısı gerektirir; anket veya günlük verilerinden geçerli bir grafik oluşturmak kendi ölçüm belirsizliğini getirir.
- Ortalama alan modellerinin homojen karışım varsayımı, heterojen gerçek dünya ağlarında geçerli olmayabilir; tam ağ simülasyonu daha doğrudur ancak hesaplama açısından daha ağırdır.
- Gözlemsel verilerden parametre tahmini (τ, γ) önemsizdir ve genellikle ek kalibrasyon veya Bayesci çıkarım adımları gerektirir.
- Stokastik sonuçlar çalıştırmalar arasında değişir; yeterli sayıda Monte Carlo tekrarı gereklidir, bu da büyük ağlar için hesaplama süresini artırır.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Yüksek bağlantılı merkezlerin yayılımı toplu modellerin öngördüğünden çok daha fazla hızlandırdığı gerçeğini yakalayarak ağ topolojisini açıkça hesaba katar.
- Esnek model ailesi — SIR, SIS, Bağımsız Kaskat, Doğrusal Eşik — hem biyolojik bulaşmayı hem de sosyal etki süreçlerini kapsar.
- Monte Carlo simülasyonu, yalnızca nokta tahminleri değil, sonuçların tam dağılımlarını üretir, bu da ilkeli belirsizlik ölçümünü sağlar.
- Etki maksimizasyonu çerçevesi (Kempe vd., 2003), pratik tohumlama stratejileriyle — sinyali en geniş şekilde yayan aktivasyonlarının düğümlerini belirleme — doğrudan bağlantı kurar.
Uygulama alanları
- Aşılamaveya karantina gibi müdahale stratejilerini değerlendirmek için temas ağları aracılığıyla bulaşıcı hastalıkların (grip, COVID-19) yayılımını modellemek.
- Viral pazarlama ve ürün benimsenmesi — sosyal bir ağ aracılığıyla bilgi veya ürün alımının yayılmasını en üst düzeye çıkaran tohum kullanıcıları belirleme.
- Yanlış bilgilendirme ve söylenti yayma — sosyal platformlarda yanlış bilginin nasıl yayıldığını ve hedeflenen düzeltmelerin en yüksek etkiyi nerede gösterdiğini anlama.
- Kurumsal ve politika ağlarında yenilik yayılımı — yeni bir teknolojinin veya uygulamanın bir profesyonel toplulukta nasıl yayıldığını tahmin etme.
- Halk sağlığı planlaması için hesaplamalı epidemiyoloji — farklı temas oranı veya aşılama senaryoları altında salgın yörüngelerini simüle etme.
Nasıl çalışır?
Nasıl çalışır?
İlk adım, sistemi düğümlerin ajanlar (insanlar, web sayfaları, cihazlar) olduğu ve kenarların temasları veya sosyal bağları kodladığı bir grafik olarak temsil etmektir. Grafik ampirik (verilerden türetilmiş) veya sentetik (Barabási-Albert gibi bir büyüme modeli tarafından üretilmiş) olabilir. Kenar ağırlıkları iletim olasılıklarını kodlayabilir. Modelin anlamlı dinamikler sergilemesi için en az 20 düğüm gereklidir; bu eşiğin altındaki tanımlayıcı ağ istatistikleri daha uygundur.
Analist, araştırma sorusuna uyan yayılım ailesini seçer. SIR (Duyarlı-Enfekte-İyileşmiş), bir düğüm iyileştikten sonra tekrar enfekte olamayacağı için salgınlar veya yeni bir teknolojinin benimsenmesi gibi geri döndürülemez süreçlere uygundur. SIS (Duyarlı-Enfekte-Duyarlı), düğümlerin duyarlı duruma geri dönebileceği endemik veya tekrarlayan olgulara — söylenti yeniden maruz kalma gibi — uygundur. Bağımsız Kaskat ve Doğrusal Eşik modelleri, her düğümün en fazla bir kez aktifleştiği ve odağın bir tohum kümesinin nihai erişimi olduğu sosyal etki sorunlarına uygundur.
Her model, verilerden veya literatürden elde edilen az sayıda parametre gerektirir: iletim oranı τ (temas başına zaman adımı başına yayılma olasılığı), iyileşme oranı γ (SIR/SIS için) ve başlangıçta enfekte olmuş veya aktif düğümlerin bir tohum kümesi. τ/γ oranı temel üreme sayısını R₀ tanımlar; R₀ > 1 olduğunda büyük ölçekli bir salgın meydana gelebilir. Bağımsız Kaskat modeli için her yönlendirilmiş kenar kendi aktivasyon olasılığını taşır. Homojen karışım varsayımı, ortalama alan analizini basitleştirir ancak tam ağ simülasyonları çalıştırılarak gevşetilebilir.
Sonuçlar stokastik olduğundan, model aynı parametrelerle birçok kez (Monte Carlo tekrarı) çalıştırılır ve sonuçlar ortalaması alınır. Her çalıştırma zaman içinde ilerler: her tikte her enfekte düğüm her duyarlı komşuya iletmeye çalışır ve enfekte düğümler γ olasılığıyla iyileşir. Birincil çıktılar, kompartıman boyutlarının zaman serileri (S(t), I(t), R(t)), tepe enfeksiyon sayısı, tepeye ulaşma süresi ve — etki modelleri için — aktifleşen düğümlerin nihai oranıdır. Ortalama alan SIR için dinamikler, bir adi diferansiyel denklem sistemi olarak da çözülebilir.
Sonuçlar araştırma sorusuna göre okunur: R₀ salgın eşiğinin üzerinde mi? Hangi düğümler tohum olarak seçilirse toplam yayılımı en üst düzeye çıkarır? Sonuç, τ veya γ'daki değişikliklere ne kadar duyarlıdır? Hassasiyet analizi ve ağ topolojileri (rastgele, ölçek-serbest, küçük-dünya) arasındaki karşılaştırma, yapısal varsayımların sonuçları nasıl yönlendirdiğini ortaya koyar. Analist, sonuçların deterministik bir ortalama alan çözümünden mi yoksa stokastik simülasyonlar üzerinden Monte Carlo ortalamalarından mı geldiğini bildirmeli ve kullanılan tekrar sayısını belirtmelidir.
Sık yapılan hatalar
- Çok az düğüm kullanmak (20'den az) — küçük grafiklerde stokastik dalgalanmalar baskın gelir ve model güvenilir bir sinyal üretmez; bunun yerine tanımlayıcı ağ istatistiklerini kullanın.
- Özellikle ölçek-serbest grafikler bu varsayımı ihlal ettiği ve tam ağ simülasyonu gerektirdiği için, güçlü heterojen bir ağa ortalama alan (homojen karışım) yaklaşımı uygulamak.
- Sonuçların tohum kümesine duyarlılığını göz ardı etmek — başlangıçta enfekte olmuş düğümlerin seçimi tepe enfeksiyon boyutunu önemli ölçüde değiştirebilir; her zaman tohumlama stratejisini bildirin.
- Tek bir stokastik çalıştırmayı sonuç olarak ele almak — her zaman birden fazla Monte Carlo tekrarı üzerinden ortalama alın ve varyansı veya güven aralıklarını bildirin.
- SIR ve SIS'i karıştırmak: iyileşmenin bağışıklık sağladığı durumlarda SIR (hastalık, teknoloji benimseme), düğümlerin duyarlı duruma geri dönebileceği durumlarda SIS (söylentiler, mevsimsel hastalık) kullanın.
Sık sorulan sorular
Ne zaman SIR, SIS veya Bağımsız Kaskat kullanmalıyım?
İyileşmenin kalıcı bağışıklık sağladığı — birçok bulaşıcı hastalıkta veya tek seferlik teknoloji benimsemelerinde olduğu gibi — bir düğümün iyileştikten sonra duyarlı duruma geri dönemediği durumlarda SIR kullanın. Durumun tekrarlayan olduğu veya bağışıklığın geçici olduğu, düğümlerin süresiz olarak duyarlı ve enfekte arasında döngüye girdiği mevsimsel hastalık veya söylenti yeniden maruz kalma gibi durumlarda SIS kullanın. Odak noktasının sosyal etki olduğu ve bir düğümün en fazla bir kez aktif olabileceği durumlarda Bağımsız Kaskat veya Doğrusal Eşik seçin; bu modeller, seçilen bir tohum kümesinden aktifleşen düğümlerin nihai sayısını en üst düzeye çıkarma hedefinin olduğu pazarlama, bilgi yayılımı veya davranış benimseme sorunlarına daha uygundur.
Kaç Monte Carlo tekrarı yeterlidir?
Evrensel bir kural yoktur, ancak pratikte literatürde yaygın olarak 100-1000 tekrar kullanılır, ağ boyutu arttıkça veya sonuç varyansı yüksek olduğunda daha fazla tekrar gereklidir. Okuyucuların kararlılığı değerlendirebilmesi için tekrar sayısını ve ana metriklerin (tepe enfeksiyonu, nihai aktivasyon oranı) varyansını bildirin.
Verilerden iletim oranı τ'yu nasıl tahmin ederim?
Zaman damgalı vaka verileriniz ve bilinen bir ağınız varsa, τ, kompartıman adi diferansiyel denklem sistemini en küçük kareler veya en büyük olabilirlik yöntemlerini kullanarak gözlemlenen eğrilere uydurarak veya Bayesci çıkarım yoluyla tahmin edilebilir. Sosyal etki ortamları için, kenar düzeyindeki aktivasyon olasılıkları bazen gözlemlenen etkileşim sıklıklarının orantılı olarak ayarlanır. Veri mevcut olmadığında, τ tipik olarak literatürden alınan makul bir aralık üzerinde duyarlılık analizinde değiştirilir.
Bu modeller ağırlıklı veya yönlendirilmiş ağlarda çalışabilir mi?
Evet. Kenar ağırlıkları heterojen iletim olasılıklarını kodlayabilir — güçlü bir şekilde bağlı bir çift, zayıf bir şekilde bağlı bir çiftten daha yüksek bir τ'ya sahiptir. Yönlendirilmiş kenarlar, A düğümünün B'yi enfekte edebildiği ancak B'nin doğrudan A'yı enfekte edemediği asimetrik etkiyi modeller. Her iki uzantı da tam ağ simülasyonunda uygulamak için basittir, ancak ortalama alan yaklaşımları daha az doğru hale gelir ve genellikle derece tabanlı heterojen ortalama alan veya çift yaklaşım yöntemleriyle değiştirilmesi gerekir.
İlgili yöntemler
Kaynaklar
Kermack, W.O. & McKendrick, A.G. (1927). A Contribution to the Mathematical Theory of Epidemics. Proceedings of the Royal Society of London. Series A, 115(772), 700-721.
DOI kaynağını açKopyalandı.Kempe, D., Kleinberg, J., & Tardos, E. (2003). Maximizing the Spread of Influence through a Social Network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 137-146.
DOI kaynağını açKopyalandı.