Skip to content
Kembali ke hasil pencarian

Model Difusi Jaringan — SIR, SIS, dan Independent Cascade

Diperkenalkan oleh
Kermack & McKendrick (SIR/SIS, 1927); Kempe, Kleinberg & Tardos (Independent Cascade, 2003)
Tahun
1927 (epidemiological compartmental); 2003 (social influence cascade)
Jenis
Stochastic / deterministic simulation on graphs

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Model difusi jaringan adalah keluarga kerangka kerja kompartemen dan probabilistik yang mensimulasikan bagaimana informasi, penyakit, atau inovasi menyebar melintasi sistem yang terhubung.

Berakar pada epidemiologi matematika Kermack dan McKendrick (1927), model SIR dan SIS mempartisi node ke dalam keadaan dan melacak transisi yang didorong oleh tingkat kontak dan probabilitas pemulihan. Model Independent Cascade dan Linear Threshold, yang diformalkan oleh Kempe, Kleinberg, dan Tardos (2003), memperluas logika ini ke pengaruh sosial, memodelkan bagaimana aktivasi merambat melalui jaringan satu tetangga pada satu waktu.

Intuisi di balik metode

Bayangkan sebuah gosip menyebar melalui sekolah. Ketika seorang siswa mendengarnya, mereka mungkin menyampaikannya kepada setiap teman dengan probabilitas tertentu, teman yang sudah mendengarnya tidak perlu mendengarnya lagi, dan akhirnya gosip tersebut mencapai semua orang atau menghilang. Model difusi jaringan memformalkan proses ini: setiap node berada dalam keadaan (rentan, terinfeksi, pulih, atau sekadar aktif/tidak aktif), dan pada setiap langkah waktu, node tersebut menyebarkan sinyal ke tetangganya sesuai dengan probabilitas transmisi atau pulih kembali ke keadaan dasar. Wawasan kuncinya adalah bahwa struktur jaringan — siapa yang terhubung dengan siapa — membentuk hasil sama banyaknya dengan tingkat transmisi itu sendiri.

Sejarah

Dasar-dasar matematis difusi jaringan diletakkan oleh Kermack dan McKendrick dalam makalah penting mereka tahun 1927, yang memperkenalkan kerangka kerja SIR sebagai sistem persamaan diferensial biasa yang menggambarkan transisi epidemi. Varian SIS menggeneralisasi ini untuk penyakit endemik di mana kekebalan bersifat sementara. Pendekatan medan rata-rata ini memperlakukan populasi sebagai tercampur secara homogen. Pergeseran ke struktur jaringan eksplisit — memungkinkan node yang berbeda memiliki jumlah kontak yang berbeda — menjadi pusat epidemiologi komputasi pada akhir 1990-an dan awal 2000-an, ketika model jaringan skala-bebas (Barabási dan Albert, 1999) mengungkapkan bahwa hub memainkan peran yang tidak proporsional dalam penularan. Kempe, Kleinberg, dan Tardos (2003) memformalkan masalah maksimisasi pengaruh di bawah model Independent Cascade dan Linear Threshold, menghubungkan teori difusi ke masalah algoritmik dalam komputasi sosial dan pemasaran. Sejak itu, bidang ini telah berkembang ke jaringan berlapis, urutan kontak temporal, dan estimasi parameter berbasis data menggunakan dataset epidemi atau media sosial yang sebenarnya.

Kapan digunakan

Model difusi jaringan sesuai ketika Anda memiliki dataset relasional (atau dapat membangun jaringan yang masuk akal) dan ingin memprediksi atau menjelaskan bagaimana suatu keadaan — penyakit, informasi, perilaku, inovasi — menyebar melaluinya. Model ini cocok untuk tugas prediksi, penjelasan, dan peramalan pada variabel keadaan node biner atau kontinu dalam struktur cross-sectional atau time-series. Jaringan harus memiliki setidaknya 20 node; dengan node yang lebih sedikit, dinamika stokastik tidak menghasilkan pola yang bermakna. Tingkat transmisi dan pemulihan harus dapat diestimasi dari data atau dikalibrasi dari literatur. Jika tidak ada struktur jaringan yang tersedia, atau jika hanya ada data agregat (non-relasional), model persamaan diferensial biasa kompartemen tanpa lapisan graf adalah alternatif yang lebih sederhana.

Batasan dan pertimbangan

  • Memerlukan struktur jaringan yang diketahui atau diestimasi; membangun graf yang valid dari data survei atau log menimbulkan ketidakpastian pengukuran tersendiri.
  • Asumsi pencampuran homogen dari model medan rata-rata mungkin tidak berlaku pada jaringan dunia nyata yang heterogen; simulasi jaringan penuh lebih akurat tetapi lebih berat secara komputasi.
  • Estimasi parameter (τ, γ) dari data observasional tidak sepele dan seringkali memerlukan kalibrasi tambahan atau langkah inferensi Bayesian.
  • Hasil stokastik bervariasi antar pengulangan; jumlah pengulangan Monte Carlo yang cukup diperlukan, yang meningkatkan waktu komputasi untuk jaringan besar.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Secara eksplisit memperhitungkan topologi jaringan, menangkap fakta bahwa hub yang sangat terhubung mempercepat penyebaran jauh melampaui apa yang diprediksi model agregat.
  • Keluarga model yang fleksibel — SIR, SIS, Independent Cascade, Linear Threshold — mencakup proses penularan biologis dan pengaruh sosial.
  • Simulasi Monte Carlo menghasilkan distribusi hasil penuh, bukan hanya perkiraan titik, memungkinkan kuantifikasi ketidakpastian yang berprinsip.
  • Kerangka kerja maksimisasi pengaruh (Kempe et al., 2003) terhubung langsung ke strategi penanaman praktis — mengidentifikasi node yang aktivasinya menyebarkan sinyal paling luas.

Penerapan

  • Memodelkan penyebaran penyakit menular (influenza, COVID-19) melalui jaringan kontak untuk mengevaluasi strategi intervensi seperti vaksinasi atau karantina.
  • Pemasaran viral dan adopsi produk — mengidentifikasi pengguna benih yang aktivasinya memaksimalkan penyebaran informasi atau penyerapan produk melalui jaringan sosial.
  • Misinformasi dan penyebaran gosip — memahami bagaimana informasi palsu menyebar di platform sosial dan di mana koreksi yang ditargetkan memiliki dampak tertinggi.
  • Difusi inovasi dalam jaringan organisasi dan kebijakan — memprediksi bagaimana teknologi atau praktik baru menyebar melalui komunitas profesional.
  • Epidemiologi komputasi untuk perencanaan kesehatan masyarakat — mensimulasikan lintasan wabah di bawah skenario tingkat kontak atau vaksinasi yang berbeda.

Cara kerjanya

Cara kerjanya

1

Langkah pertama adalah merepresentasikan sistem sebagai graf di mana node adalah agen (orang, halaman web, perangkat) dan tepi mengkodekan kontak atau ikatan sosial. Graf dapat bersifat empiris (berasal dari data) atau sintetis (dihasilkan oleh model pertumbuhan seperti Barabási-Albert). Bobot tepi dapat mengkodekan probabilitas transmisi. Minimal 20 node diperlukan agar model menunjukkan dinamika yang bermakna; di bawah ambang batas tersebut statistik jaringan deskriptif lebih sesuai.

2

Analis memilih keluarga difusi yang sesuai dengan pertanyaan penelitian. SIR (Susceptible–Infected–Recovered) cocok untuk proses yang tidak dapat diubah seperti epidemi atau adopsi teknologi baru, karena begitu node pulih, ia tidak dapat terinfeksi kembali. SIS (Susceptible–Infected–Susceptible) cocok untuk fenomena endemik atau berulang — seperti paparan kembali gosip — di mana node dapat kembali menjadi rentan. Model Independent Cascade dan Linear Threshold cocok untuk masalah pengaruh sosial di mana setiap node aktif paling banyak sekali dan fokusnya adalah jangkauan akhir dari sekumpulan benih.

3

Setiap model memerlukan sejumlah kecil parameter yang didasarkan pada data atau literatur: tingkat transmisi τ (probabilitas penyebaran per kontak per langkah waktu), tingkat pemulihan γ (untuk SIR/SIS), dan sekumpulan benih node yang awalnya terinfeksi atau aktif. Rasio τ/γ mendefinisikan angka reproduksi dasar R₀; ketika R₀ > 1 wabah skala besar dapat terjadi. Untuk model Independent Cascade, setiap tepi berarah membawa probabilitas aktivasinya sendiri. Asumsi pencampuran homogen menyederhanakan analisis medan rata-rata tetapi dapat dilonggarkan dengan menjalankan simulasi jaringan penuh.

4

Karena hasilnya stokastik, model dijalankan berkali-kali (pengulangan Monte Carlo) dengan parameter yang sama dan hasilnya dirata-ratakan. Setiap pengulangan melangkah melalui waktu: pada setiap detik, setiap node yang terinfeksi mencoba menular ke setiap tetangga yang rentan, dan node yang terinfeksi pulih dengan probabilitas γ. Keluaran utama adalah deret waktu ukuran kompartemen (S(t), I(t), R(t)), jumlah infeksi puncak, waktu hingga puncak, dan — untuk model pengaruh — fraksi akhir node yang teraktivasi. Untuk SIR medan rata-rata, dinamika juga dapat diselesaikan sebagai sistem persamaan diferensial biasa.

5

Hasil dibaca terhadap pertanyaan penelitian: Apakah R₀ di atas ambang batas epidemi? Node mana, jika dipilih sebagai benih, yang memaksimalkan penyebaran total? Seberapa sensitif hasilnya terhadap perubahan τ atau γ? Analisis sensitivitas dan perbandingan di berbagai topologi jaringan (acak, skala-bebas, dunia kecil) mengungkapkan bagaimana asumsi struktural mendorong kesimpulan. Analis harus melaporkan apakah hasil berasal dari solusi medan rata-rata deterministik atau dari rata-rata Monte Carlo atas simulasi stokastik, dan harus menyatakan jumlah pengulangan yang digunakan.

Kesalahan umum

  • Menggunakan terlalu sedikit node (kurang dari 20) — dengan graf kecil, fluktuasi stokastik mendominasi dan model tidak menghasilkan sinyal yang andal; gunakan statistik jaringan deskriptif sebagai gantinya.
  • Menerapkan aproksimasi medan rata-rata (pencampuran homogen) ke jaringan yang sangat heterogen — terutama graf skala-bebas melanggar asumsi ini dan memerlukan simulasi jaringan penuh.
  • Mengabaikan sensitivitas hasil terhadap set benih — pilihan node yang awalnya terinfeksi dapat secara dramatis mengubah ukuran infeksi puncak; selalu laporkan strategi penanaman.
  • Memperlakukan satu pengulangan stokastik sebagai hasil — selalu rata-ratakan atas beberapa pengulangan Monte Carlo dan laporkan varians atau interval kepercayaan.
  • Menggabungkan SIR dan SIS: gunakan SIR ketika pemulihan memberikan kekebalan (penyakit, adopsi teknologi), gunakan SIS ketika node dapat terinfeksi kembali atau terpapar kembali (gosip, penyakit musiman).

Pertanyaan yang sering diajukan

Kapan saya harus menggunakan SIR versus SIS versus Independent Cascade?

Gunakan SIR ketika pemulihan memberikan kekebalan permanen — seperti pada banyak penyakit menular atau adopsi teknologi sekali pakai — sehingga node tidak dapat kembali ke rentan setelah pulih. Gunakan SIS ketika kondisi bersifat berulang atau kekebalan bersifat sementara, seperti penyakit musiman atau paparan kembali gosip, di mana node berputar antara rentan dan terinfeksi tanpa batas. Pilih Independent Cascade atau Linear Threshold ketika fokusnya adalah pada pengaruh sosial dan node dapat menjadi aktif paling banyak sekali; model-model ini lebih cocok untuk masalah pemasaran, penyebaran informasi, atau adopsi perilaku di mana tujuannya adalah untuk memaksimalkan jumlah akhir node yang teraktivasi dari set benih yang dipilih.

Berapa banyak pengulangan Monte Carlo yang cukup?

Tidak ada aturan universal, tetapi dalam praktiknya 100–1000 pengulangan umum digunakan dalam literatur, dengan lebih banyak pengulangan diperlukan seiring bertambahnya ukuran jaringan atau ketika varians hasil tinggi. Laporkan jumlah pengulangan dan varians metrik utama (infeksi puncak, fraksi aktivasi akhir) sehingga pembaca dapat menilai stabilitas.

Bagaimana cara mengestimasi tingkat transmisi τ dari data?

Jika Anda memiliki data kasus berwaktu dan jaringan yang diketahui, τ dapat diestimasi dengan mencocokkan sistem ODE kompartemen ke kurva yang diamati menggunakan metode kuadrat terkecil atau kemungkinan maksimum, atau melalui inferensi Bayesian. Untuk pengaturan pengaruh sosial, probabilitas aktivasi tingkat tepi terkadang ditetapkan sebanding dengan frekuensi interaksi yang diamati. Ketika tidak ada data yang tersedia, τ biasanya divariasikan dalam analisis sensitivitas di seluruh rentang yang masuk akal yang diinformasikan oleh literatur.

Bisakah model ini berjalan pada jaringan berbobot atau terarah?

Ya. Bobot tepi dapat mengkodekan probabilitas transmisi heterogen — pasangan yang terikat kuat memiliki τ yang lebih tinggi daripada pasangan yang terikat lemah. Tepi terarah memodelkan pengaruh asimetris, di mana node A dapat menginfeksi B tetapi B tidak dapat secara langsung menginfeksi A. Kedua ekstensi ini mudah diimplementasikan dalam simulasi jaringan penuh, meskipun aproksimasi medan rata-rata menjadi kurang akurat dan seringkali perlu diganti dengan metode medan rata-rata heterogen berbasis derajat atau aproksimasi pasangan.

Metode terkait

Sumber

  1. 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.

    Buka referensi DOI
    Disalin.
  2. 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.

    Buka referensi DOI
    Disalin.