Analisis Modularitas
- Diperkenalkan oleh
- Newman, M. E. J. & Girvan, M.
- Tahun
- 2004
- Jenis
- Community detection / graph partitioning
- Keluarga
- Network science
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Analisis modularitas adalah metode sains jaringan, yang diformalkan oleh Newman dan Girvan pada tahun 2004, yang mendeteksi struktur komunitas dalam graf dengan mengukur apakah tepi lebih terkonsentrasi di dalam kelompok daripada yang diharapkan secara kebetulan.
Indeks kualitas skalar Q-nya memandu algoritma yang mempartisi node ke dalam kluster yang kohesif, menjadikannya kerangka kerja yang paling diadopsi secara luas untuk deteksi komunitas dalam jaringan sosial, biologis, dan teknologi.
Intuisi di balik metode
Jika Anda secara acak mengacak semua tepi jaringan sambil mempertahankan derajat setiap node, Anda akan mendapatkan model nol tanpa komunitas nyata. Modularitas membandingkan distribusi tepi aktual dengan model nol ini: jika sebuah partisi menghasilkan lebih banyak tepi di dalam kelompok daripada yang diprediksi oleh model nol, Q tinggi, menandakan struktur komunitas yang asli. Sebuah pengoptimal mencari ruang partisi yang mungkin untuk pemisahan yang memaksimalkan Q, mengungkapkan pengelompokan alami yang tersirat oleh struktur jaringan, tanpa memerlukan analis untuk menentukan jumlah komunitas di muka.
Sejarah
Fungsi modularitas Q diperkenalkan oleh Newman dan Girvan pada tahun 2004 sebagai bagian dari serangkaian teknik deteksi komunitas. Makalah PNAS Newman tahun 2006 memformalkan pendekatan spektral untuk optimasi modularitas, dan metode Louvain (Blondel dkk., 2008) membuat optimasi skala besar menjadi praktis, mempopulerkan analisis modularitas di seluruh sosiologi, biologi, dan ilmu komputer. Masalah batas resolusi diidentifikasi oleh Fortunato dan Barthélemy pada tahun 2007, memotivasi algoritma yang ditingkatkan seperti Leiden (Traag dkk., 2019) yang juga mengoreksi komunitas yang terhubung buruk.
Kapan digunakan
Gunakan analisis modularitas ketika Anda memiliki kumpulan data relasional yang dapat direpresentasikan sebagai graf dan ingin mengidentifikasi subkelompok kohesif tanpa menentukan jumlahnya terlebih dahulu — misalnya, mendeteksi faksi dalam jaringan sosial, modul fungsional dalam jaringan interaksi protein, atau kluster topik dalam jaringan kutipan. Ini sesuai untuk graf tak berarah dan berarah dengan setidaknya beberapa lusin node dan struktur tepi yang jelas tidak sepele. Jangan gunakan ketika jaringan terlalu kecil (kurang dari sekitar 30 node) atau hampir lengkap, ketika bobot tepi membawa informasi penting yang diabaikan oleh model nol biner sederhana, ketika komunitas diketahui tumpang tindih secara signifikan (gunakan metode komunitas tumpang tindih sebagai gantinya), atau ketika Anda memerlukan batas yang diuji secara statistik daripada heuristik optimasi.
Batasan dan pertimbangan
- Batas resolusi: optimasi modularitas secara sistematis gagal mendeteksi komunitas yang lebih kecil dari skala yang ditetapkan oleh ukuran jaringan, menggabungkan modul kecil yang berbeda secara asli.
- Optimasi eksak NP-sulit berarti hanya perkiraan yang digunakan dalam praktik, dan eksekusi algoritma stokastik yang berbeda dapat menghasilkan partisi yang berbeda.
- Model nol mengasumsikan model konfigurasi (urutan derajat mirip Erdos-Renyi), yang mungkin tidak sesuai untuk jaringan dengan distribusi derajat ekor berat atau struktur hierarkis.
- Batas komunitas yang keras tidak dapat mewakili keanggotaan tumpang tindih di dunia nyata.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Tidak perlu menentukan jumlah komunitas di muka; partisi muncul dari data.
- Menyediakan skalar tunggal Q yang memfasilitasi perbandingan partisi atau jaringan yang berbeda secara langsung.
- Algoritma perkiraan cepat (Louvain, Leiden) dapat diskalakan hingga jutaan node.
- Dapat diterapkan pada jaringan tak berarah, berarah, dan berbobot dengan ekstensi yang sesuai.
- Diimplementasikan secara luas dalam pustaka standar (NetworkX, igraph, Gephi), menurunkan hambatan penggunaan.
Penerapan
- Mendeteksi faksi sosial, ruang gema, atau kluster kolaborasi dalam jaringan sosial online dan offline.
- Mengidentifikasi modul fungsional dalam jaringan biologis seperti graf interaksi protein-protein dan graf regulasi gen.
- Mengungkap kluster tematik atau disipliner dalam jaringan kutipan dan kolaborasi penulisan.
- Segmentasi jaringan pelanggan atau produk dalam sistem pemasaran dan rekomendasi.
- Partisi jaringan infrastruktur (jaringan listrik, transportasi) untuk analisis ketahanan.
- Menemukan komunitas topik dalam graf hyperlink atau ko-kemunculan dalam linguistik komputasi.
Cara kerjanya
Cara kerjanya
Jaringan direpresentasikan sebagai matriks ketetanggaan A (atau daftar tepi yang setara), di mana entri A_ij sama dengan 1 jika node i dan j terhubung dan 0 jika tidak. Derajat node (k_i, k_j) dan jumlah total tepi m dihitung sebagai masukan untuk formula modularitas.
Skor modularitas Q didefinisikan sebagai fraksi tepi yang jatuh di dalam komunitas dikurangi fraksi yang diharapkan di bawah model nol konfigurasi (pengacakan acak mempertahankan derajat). Q berkisar dari sekitar -0,5 hingga 1; nilai di atas sekitar 0,3 menunjukkan struktur komunitas yang bermakna.
Rumus
Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)Karena pencarian menyeluruh atas semua partisi yang mungkin adalah NP-sulit, algoritma praktis memperkirakan optimumnya. Pendekatan umum meliputi metode Louvain (agregasi serakah), algoritma Leiden (varian yang dikoreksi dan lebih cepat), optimasi spektral menggunakan vektor eigen dari matriks modularitas, dan simulated annealing.
Setiap node ditugaskan ke komunitas yang memaksimalkan Q untuk partisi keseluruhan. Algoritma biasanya menghasilkan dendrogram hierarkis, memungkinkan inspeksi struktur komunitas pada berbagai resolusi, dari super-komunitas kasar hingga kluster yang terperinci.
Partisi yang dihasilkan dievaluasi oleh nilai Q akhir, pemeriksaan stabilitas di berbagai eksekusi algoritma, dan, jika kebenaran dasar tersedia, metrik eksternal seperti informasi bersama yang dinormalisasi. Q rendah atau hasil yang tidak stabil di berbagai eksekusi menunjukkan struktur komunitas yang lemah atau tidak ada.
Kesalahan umum
- Menerima satu eksekusi pengoptimal stokastik tanpa memeriksa stabilitas di berbagai eksekusi atau benih acak.
- Mengabaikan batas resolusi dan menyimpulkan bahwa komunitas besar yang digabungkan benar-benar homogen.
- Menggunakan modularitas biner pada jaringan berbobot tanpa mengadaptasi model nol untuk memasukkan bobot tepi.
- Memperlakukan Q di atas 0,3 sebagai ambang batas universal untuk struktur 'baik' tanpa mempertimbangkan jenis dan ukuran jaringan.
- Menggabungkan kualitas optimasi (Q tinggi) dengan validitas interpretatif — komunitas masih harus diperiksa secara substantif.
Pertanyaan yang sering diajukan
Berapa nilai Q yang baik?
Q di atas sekitar 0,3 umumnya dikutip sebagai indikator struktur komunitas yang bermakna, tetapi ambang batas ini bergantung pada jenis dan ukuran jaringan. Jaringan yang sangat besar dengan struktur lemah dapat memiliki Q mendekati 0,1 namun tetap mengungkapkan kluster yang dapat diinterpretasikan, sementara jaringan kecil yang padat dapat mencapai Q di atas 0,5. Selalu periksa komunitas secara substantif daripada hanya mengandalkan Q.
Algoritma mana yang harus saya gunakan untuk memaksimalkan Q?
Algoritma Leiden (Traag dkk., 2019) saat ini direkomendasikan secara default: lebih cepat daripada metode Louvain asli dan mengoreksi kecenderungannya untuk menghasilkan komunitas yang terhubung buruk. Untuk graf yang sangat besar, Louvain tetap menjadi pilihan praktis. Metode spektral lebih disukai ketika Anda memerlukan hasil yang dapat direproduksi dan deterministik pada jaringan yang lebih kecil.
Bisakah analisis modularitas mendeteksi komunitas yang tumpang tindih?
Optimasi modularitas standar menugaskan setiap node ke tepat satu komunitas dan tidak dapat mendeteksi tumpang tindih. Jika Anda mengharapkan node untuk menjadi milik beberapa kelompok secara bersamaan, gunakan metode komunitas tumpang tindih seperti metode clique-percolation atau pendekatan faktorisasi matriks non-negatif sebagai gantinya.
Bagaimana batas resolusi memengaruhi analisis saya?
Optimasi modularitas cenderung menggabungkan komunitas yang lebih kecil dari sekitar sqrt(m) tepi menjadi komunitas yang lebih besar. Ini berarti kluster kecil yang asli dapat tidak terlihat ketika jaringan besar. Untuk mengurangi hal ini, variasikan parameter resolusi (tersedia di Leiden dan beberapa implementasi Louvain) dan bandingkan partisi di beberapa nilai resolusi.
Haruskah saya menerapkan analisis modularitas ke jaringan berarah?
Ya, dengan model nol yang diadaptasi yang mempertahankan urutan derajat masuk dan keluar, seperti yang diimplementasikan dalam alat seperti igraph. Modularitas tak berarah yang diterapkan secara naif pada graf berarah membuang ketidaksimetrisan hubungan dan dapat menghasilkan partisi yang menyesatkan.
Metode terkait
Sumber
Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.
Buka referensi DOIDisalin.Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582.
Buka referensi DOIDisalin.