Model Blok Stokastik — Deteksi Komunitas Probabilistik dalam Jaringan
- Tahun
- 1983
- Jenis
- Probabilistic generative graph model
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Model Blok Stokastik (SBM), yang diperkenalkan oleh Holland, Laskey dan Leinhardt (1983), adalah model generatif probabilistik untuk graf yang menugaskan simpul ke blok laten dan secara parametrik memperkirakan probabilitas koneksi antar blok.
Ini adalah pendekatan fundamental untuk deteksi komunitas, identifikasi inti-periferi, dan penemuan struktur hierarkis dalam analisis jaringan.
Intuisi di balik metode
Bayangkan sebuah jaringan sosial di mana orang-orang mengelompok ke dalam grup — kolega, keluarga, tim olahraga — dan koneksi di dalam grup lebih mungkin terjadi daripada koneksi antar grup. Model Blok Stokastik memformalkan intuisi ini: ia mengasumsikan ada label grup tersembunyi untuk setiap simpul, dan probabilitas tepi antara dua simpul hanya bergantung pada grup mana kedua simpul tersebut berada. Pencocokan model berarti menemukan label tersembunyi yang paling baik menjelaskan pola tepi yang diamati. Hasilnya adalah partisi jaringan menjadi blok yang berprinsip dan berdasar secara statistik, tanpa memerlukan grup menjadi klik padat — model mengakomodasi struktur inti-periferi dan bahkan pola disasortatif di mana koneksi antar-grup melebihi koneksi intra-grup.
Sejarah
Model Blok Stokastik diperkenalkan oleh Holland, Laskey dan Leinhardt dalam makalah Social Networks mereka tahun 1983 sebagai generalisasi probabilistik dari pekerjaan blockmodelling sebelumnya dalam analisis jaringan sosial. Selama dua dekade, model ini terutama tetap menjadi alat teoretis; model ini mendapatkan daya tarik praktis dengan pengembangan algoritma inferensi yang dapat diskalakan — variational EM dan MCMC — pada tahun 2010-an. SBM yang Dikoreksi Derajat diperkenalkan oleh Karrer dan Newman (2011) untuk mengatasi masalah heterogenitas derajat. Tinjauan Lee dan Wilkinson tahun 2019 di Applied Network Science mengkonsolidasikan keluarga perluasan, mencakup model partisi yang ditanam, SBM keanggotaan campuran, dan varian hierarkis. Saat ini SBM dan turunannya adalah kerangka kerja probabilistik referensi untuk deteksi komunitas dan pengelompokan graf.
Kapan digunakan
Gunakan Model Blok Stokastik ketika Anda memiliki jaringan dengan setidaknya 50 simpul dan Anda ingin menemukan struktur grup laten tanpa mengasumsikan bahwa grup harus berupa klik padat. Ini sesuai untuk graf berarah atau tak berarah, berbobot atau tak berbobot, dan cocok untuk tugas eksploratif maupun klasifikasi. Varian DCSBM lebih disukai ketika derajat simpul bervariasi secara substansial. Jika graf memiliki kurang dari 20 simpul, struktur komunitas tidak dapat diperkirakan secara andal dan metrik deskriptif yang lebih sederhana harus digunakan sebagai gantinya. Asumsi: keanggotaan blok bersifat laten dan tidak diamati; matriks koneksi blok diasumsikan homogen dalam setiap pasangan blok; dan K harus dipilih oleh BIC atau faktor Bayes daripada ditetapkan secara sewenang-wenang.
Batasan dan pertimbangan
- Membutuhkan setidaknya sekitar 50 simpul untuk estimasi blok yang andal; graf yang sangat kecil menghasilkan solusi yang tidak stabil.
- Inferensi secara komputasi mahal untuk graf besar: variational EM atau MCMC diperlukan, dan konvergensi tidak dijamin.
- Asumsi homogenitas SBM dasar dalam pasangan blok rusak ketika tingkat koneksi dalam blok bervariasi — DCSBM mengurangi tetapi tidak menghilangkan ini.
- Pemilihan blok melalui BIC atau faktor Bayes masih dapat melakukan segmentasi kurang atau berlebihan jika graf memiliki komunitas yang terpisah lemah.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Kerangka kerja probabilistik berprinsip yang memungkinkan pemilihan model melalui BIC atau faktor Bayes, menghindari pilihan parameter sewenang-wenang.
- Mengakomodasi berbagai pola struktural — komunitas, inti-periferi, bipartit, dan hierarkis — di luar asumsi klik padat dari metode algoritmik.
- Varian yang Dikoreksi Derajat menangani graf dengan distribusi derajat heterogen dan hub tanpa mendistorsi penugasan blok.
- Menyediakan probabilitas keanggotaan posterior, memungkinkan penugasan simpul lunak atau tidak pasti daripada partisi keras.
Penerapan
- Mendeteksi komunitas penelitian dalam jaringan kutipan dan kolaborasi di ilmu sosial dan alam.
- Mengidentifikasi modul fungsional dalam jaringan biologis seperti interaksi protein-protein dan graf ko-ekspresi gen.
- Menemukan segmen pelanggan atau cincin penipuan dalam jaringan transaksional dan keuangan.
- Mengkarakterisasi struktur inti-periferi dalam jaringan perdagangan antar-organisasi atau antar-negara.
- Melakukan benchmark dan mengevaluasi algoritma deteksi komunitas lainnya menggunakan graf sintetis yang dihasilkan SBM sebagai kebenaran dasar.
Cara kerjanya
Cara kerjanya
Analis menentukan rentang kandidat untuk jumlah blok K dan memilih varian: SBM dasar mengasumsikan distribusi derajat dalam blok yang homogen, sedangkan SBM yang Dikoreksi Derajat (DCSBM) menambahkan parameter derajat tingkat simpul untuk menangani hub dan urutan derajat heterogen. Pilihan varian diinformasikan oleh distribusi derajat graf yang diamati.
Diberikan matriks ketetanggaan, model memperkirakan keanggotaan blok dan matriks probabilitas koneksi K×K menggunakan algoritma inferensi. Untuk graf kecil hingga menengah, maksimisasi eksak layak dilakukan; untuk graf besar, Expectation-Maximisation variasional (variational EM) atau sampling Markov Chain Monte Carlo (MCMC) digunakan untuk membuat inferensi dapat ditangani.
Jumlah blok K tidak diketahui sebelumnya dan harus dipilih dari data. Kriteria seleksi yang disukai adalah Kriteria Informasi Bayesian (BIC) dan faktor Bayesian, keduanya menghukum kompleksitas model dan memilih K yang paling baik menyeimbangkan kecocokan terhadap parsimoni. Prinsip panjang deskripsi minimum (MDL) mendasari implementasi graph-tool.
Setelah K optimal dan penugasan blok ditentukan, matriks koneksi blok diperiksa untuk mengkarakterisasi struktur: blok asortatif sesuai dengan komunitas, blok disasortatif dengan pola mirip bipartit, dan profil campuran dengan pengaturan inti-periferi. Keanggotaan simpul dilaporkan dengan probabilitas posterior di mana algoritma inferensi menyediakannya.
Kesalahan umum
- Menetapkan K secara sewenang-wenang daripada memilihnya dengan BIC atau faktor Bayes menghasilkan partisi yang tidak dapat diandalkan — selalu gunakan kriteria pemilihan model yang berprinsip.
- Menerapkan SBM dasar pada graf dengan urutan derajat heterogen (hub, distribusi derajat hukum pangkat) meningkatkan perkiraan jumlah blok; gunakan DCSBM sebagai gantinya.
- Memperlakukan keanggotaan blok sebagai pasti ketika posterior menyebar di atas perkiraan kepercayaan — laporkan ketidakpastian jika tersedia.
- Mencampuradukkan keluaran SBM dengan komunitas sebenarnya: model menemukan struktur laten yang masuk akal secara statistik, belum tentu grup yang bermakna secara sosiologis. Validasi terhadap pengetahuan domain.
- Menjalankan SBM pada kurang dari 20 simpul menghasilkan solusi yang degeneratif — kembali ke metrik jaringan deskriptif atau deteksi komunitas sederhana untuk graf kecil.
Pertanyaan yang sering diajukan
Bagaimana Model Blok Stokastik berbeda dari deteksi komunitas berbasis modularitas?
Maksimisasi modularitas (misalnya, Louvain, Leiden) mengoptimalkan tujuan heuristik yang secara implisit mengasumsikan komunitas asortatif, berukuran kurang lebih sama dan memiliki batas resolusi yang diketahui yang mencegah deteksi komunitas kecil. SBM adalah model generatif probabilistik dengan asumsi eksplisit; jumlah blok dipilih melalui pemilihan model (BIC atau faktor Bayes) daripada optimasi heuristik, dan dapat mendeteksi struktur disasortatif dan inti-periferi yang terlewatkan oleh metode berbasis modularitas.
Kapan saya harus menggunakan DCSBM daripada SBM dasar?
Gunakan DCSBM ketika distribusi derajat simpul heterogen — misalnya ketika sejumlah kecil hub menyumbang sebagian besar tepi, atau ketika urutan derajat mengikuti hukum pangkat perkiraan. SBM dasar memperlakukan semua simpul dalam blok sebagai dapat dipertukarkan, yang menyebabkan hub ditarik ke dalam blok palsu mereka sendiri. DCSBM menambahkan istilah koreksi derajat yang memisahkan posisi struktural dari derajat, menghasilkan penugasan blok yang lebih dapat diinterpretasikan dalam graf semacam itu.
Bagaimana cara memilih jumlah blok K?
Cocokkan model untuk berbagai nilai K dan pilih yang meminimalkan BIC atau memaksimalkan faktor Bayes (atau secara ekuivalen meminimalkan panjang deskripsi). Jangan memilih K berdasarkan inspeksi visual graf atau ekspektasi sebelumnya. Sebagian besar implementasi (graph-tool, blockmodels di R) mengotomatiskan pencarian ini. Analisis sensitivitas — memeriksa apakah struktur blok kualitatif berubah ketika K divariasikan satu — juga direkomendasikan.
Berapa ukuran jaringan minimum agar SBM andal?
Registri menetapkan minimum 50 simpul untuk inferensi yang andal. Dengan kurang dari 20 simpul, model tidak dapat mengidentifikasi struktur komunitas yang bermakna dan akan mencocokkan kebisingan — gunakan statistik jaringan deskriptif atau deteksi komunitas sederhana sebagai gantinya. Antara 20 dan 50 simpul, hasil harus diperlakukan sebagai eksploratif dan diinterpretasikan dengan hati-hati.
Metode terkait
Sumber
Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.
Buka referensi DOIDisalin.Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.
Buka referensi DOIDisalin.