Deteksi Komunitas — Pengelompokan Graf dalam Jaringan
- Diperkenalkan oleh
- Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
- Tahun
- 2002–2019 (algorithm family)
- Jenis
- Graph-partitioning / clustering algorithm family
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Deteksi komunitas adalah keluarga algoritma partisi graf yang menemukan sub-kelompok yang terhubung erat — komunitas — di dalam sebuah jaringan.
Pertama kali diformalkan melalui ukuran modularitas oleh Girvan dan Newman (2002), bidang ini berkembang pesat dengan metode Louvain (Blondel et al., 2008), penyempurnaan Leiden (Traag et al., 2019), dan pendekatan Infomap berbasis teori informasi. Semua varian menjawab pertanyaan yang sama: simpul mana yang mengelompok bersama lebih erat di antara mereka sendiri daripada dengan sisa jaringan?
Intuisi di balik metode
Bayangkan sebuah jaringan sosial besar di mana beberapa orang lebih banyak berbicara dengan lingkaran terdekat mereka sambil sesekali menjangkau ke luar. Deteksi komunitas menemukan lingkaran-lingkaran itu secara otomatis, tanpa Anda harus memberi label terlebih dahulu. Algoritma mengatur ulang simpul ke dalam kelompok sehingga koneksi internal padat dan koneksi antar-kelompok jarang — memaksimalkan skor kualitas yang disebut modularitas (atau, dalam Infomap, meminimalkan panjang deskripsi jalan acak melalui jaringan). Hasilnya adalah partisi: setiap simpul termasuk dalam tepat satu komunitas, dan Anda dapat memvisualisasikan jaringan sebagai serangkaian kluster yang kohesif.
Sejarah
Studi tentang struktur komunitas dalam jaringan ditempatkan pada pijakan kuantitatif oleh Girvan dan Newman (2002), yang memperkenalkan konsep sentralitas antara tepi sebagai alat untuk pembagian jaringan hierarkis. Newman dan Girvan (2004) kemudian memformalkan ukuran modularitas Q, yang menjadi kriteria kualitas standar. Blondel et al. (2008) menerbitkan metode Louvain — optimasi serakah dua fase yang membuat deteksi komunitas berkualitas tinggi praktis pada jaringan dengan jutaan simpul. Traag, Waltman, dan van Eck (2019) mengidentifikasi cacat struktural dalam Louvain — bahwa itu dapat menghasilkan komunitas yang terputus secara internal — dan mengembangkan algoritma Leiden untuk memperbaikinya, menjamin partisi yang terhubung dengan baik. Secara paralel, Rosvall dan Bergstrom (2008) mengembangkan Infomap, yang membingkai ulang deteksi komunitas sebagai masalah kompresi: temukan partisi yang meminimalkan panjang deskripsi jalan acak pada jaringan.
Kapan digunakan
Deteksi komunitas sesuai ketika Anda memiliki jaringan (minimal ~20 simpul) dan ingin menemukan struktur kelompok laten tanpa menentukan kelompok terlebih dahulu. Ini cocok untuk tujuan eksplorasi, deskriptif, dan klasifikasi pada data bobot tepi biner atau kontinu, termasuk data jaringan lintas sektoral dan longitudinal. Ini tidak memerlukan atribut simpul atau distribusi normal. Metode ini sangat cocok ketika jumlah komunitas tidak diketahui. Jika jaringan terlalu kecil (kurang dari 20 simpul), statistik jaringan deskriptif lebih disukai. Hasil sensitif terhadap definisi bobot tepi dan kepadatan jaringan, sehingga pilihan tersebut memerlukan pemikiran yang cermat.
Batasan dan pertimbangan
- Optimasi modularitas rentan terhadap optimum lokal; hasil dapat bervariasi antar eksekusi dan harus dilaporkan sebagai yang terbaik dari beberapa eksekusi.
- Batas resolusi berarti komunitas yang sangat kecil dalam jaringan besar dapat digabungkan, menutupi struktur yang terperinci.
- Hasil sensitif terhadap bagaimana bobot tepi didefinisikan; skema pembobotan yang berbeda dapat menghasilkan partisi yang berbeda secara bermakna.
- Girvan-Newman memiliki kompleksitas O(m²n) dan tidak praktis pada jaringan besar; Louvain atau Leiden harus lebih disukai untuk skala.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Tidak memerlukan jumlah komunitas untuk ditentukan sebelumnya — ukuran partisi ditentukan oleh data.
- Skala ke jaringan besar: Louvain dan Leiden berjalan dalam waktu mendekati linier, membuatnya praktis untuk jaringan dengan jutaan simpul.
- Leiden menjamin komunitas yang terhubung dengan baik dan kohesif secara internal, memperbaiki cacat komunitas yang terputus dari Louvain.
- Dapat diterapkan pada jaringan tak berbobot dan berbobot tanpa asumsi distribusi pada data.
Penerapan
- Mengidentifikasi kluster penelitian dalam jaringan kutipan dan kolaborasi penulisan untuk memetakan bidang ilmiah.
- Mendeteksi modul fungsional dalam jaringan interaksi protein-protein dalam biologi.
- Menemukan komunitas pengguna di media sosial dan jaringan komunikasi untuk analisis perilaku.
- Segmentasi jaringan pelanggan dalam bisnis dan pemasaran untuk mengungkapkan kelompok pelanggan yang kohesif.
- Menemukan blok struktural dalam jaringan infrastruktur, transportasi, atau rantai pasokan.
Cara kerjanya
Cara kerjanya
Inputnya adalah graf yang simpulnya mewakili entitas (orang, halaman web, protein, kutipan) dan tepinya mewakili hubungan di antara mereka. Tepi dapat diarahkan atau tidak diarahkan, dan dapat membawa bobot. Struktur ketetanggaan — simpul mana yang terhubung dan seberapa kuat — adalah satu-satunya masukan yang dibutuhkan algoritma. Tidak ada label simpul, kelas, atau atribut eksternal yang diperlukan, meskipun dapat digunakan untuk memvalidasi hasil nanti.
Setiap algoritma dimulai dengan penetapan awal simpul ke komunitas. Dalam Louvain dan Leiden, setiap simpul dimulai sebagai komunitas tunggalnya sendiri. Girvan-Newman dimulai dengan jaringan lengkap dan secara iteratif menghapus tepi dengan sentralitas antara tertinggi, secara progresif mengungkapkan struktur komunitas. Infomap dimulai dari deskripsi jalan acak dari jaringan dan mengkodekannya menggunakan peta dua tingkat untuk meminimalkan panjang kode.
Fase inti mencari partisi yang memaksimalkan modularitas Q (Louvain, Leiden) atau meminimalkan panjang kode persamaan peta (Infomap). Louvain secara serakah memindahkan simpul tunggal antar komunitas untuk meningkatkan Q, kemudian menggabungkan komunitas menjadi super-simpul dan mengulanginya — proses dua fase yang diskalakan dengan baik tetapi dapat menghasilkan komunitas yang terputus. Leiden menyempurnakan Louvain dengan menjamin setiap komunitas terhubung secara internal, menggunakan langkah pemindahan dan penyempurnaan lokal sebelum agregasi. Girvan-Newman menghapus tepi secara iteratif dan mencatat dendrogram pemisahan; partisi yang memaksimalkan Q pada setiap pemotongan dendrogram dipilih. Jumlah komunitas muncul dari algoritma itu sendiri; tidak perlu ditentukan sebelumnya.
Kualitas partisi akhir diringkas oleh skor modularitas Q, yang berkisar dari −0.5 hingga 1. Nilai di atas ~0.3–0.5 umumnya dianggap menunjukkan struktur komunitas yang bermakna. Karena optimasi modularitas dapat terjebak dalam optimum lokal, menjalankan algoritma berkali-kali dan mengambil hasil terbaik adalah praktik standar. Partisi juga diperiksa secara visual dan divalidasi silang terhadap atribut simpul yang tersedia atau label kebenaran dasar untuk mengkonfirmasi bahwa itu bermakna secara substantif.
Kesalahan umum
- Menjalankan algoritma sekali dan memperlakukan satu hasil sebagai kebenaran dasar — selalu jalankan berkali-kali dan laporkan modularitas terbaik atau gunakan metode ensemble.
- Mengabaikan batas resolusi: dalam jaringan jarang yang besar, komunitas kecil tetapi nyata dapat diserap ke dalam komunitas yang lebih besar tanpa peringatan.
- Menerapkan algoritma berbasis modularitas pada jaringan dengan kurang dari 20 simpul — struktur komunitas tidak dapat diidentifikasi secara andal pada skala itu.
- Mencampuradukkan skor modularitas tinggi dengan struktur komunitas dunia nyata yang terkonfirmasi; modularitas adalah ukuran kualitas partisi, bukan uji inferensial apakah komunitas signifikan secara statistik.
Pertanyaan yang sering diajukan
Algoritma mana yang harus saya pilih — Louvain, Leiden, Girvan-Newman, atau Infomap?
Louvain adalah dasar yang cepat dan banyak digunakan untuk jaringan besar. Leiden adalah pilihan yang disukai ketika kebenaran penting, karena menjamin komunitas yang terhubung secara internal dan biasanya mencapai modularitas yang lebih tinggi. Girvan-Newman menghasilkan dendrogram yang berguna untuk eksplorasi hierarkis tetapi terlalu lambat untuk jaringan besar. Infomap cocok untuk jaringan terarah atau berbasis aliran di mana jalur yang diambil oleh pejalan kaki acak bermakna.
Apakah saya perlu menentukan jumlah komunitas di muka?
Tidak. Louvain, Leiden, dan Infomap menentukan jumlah komunitas secara otomatis dari struktur jaringan. Girvan-Newman menghasilkan dendrogram lengkap dari mana sejumlah komunitas dapat dibaca; partisi yang memaksimalkan Q biasanya dipilih.
Bagaimana saya tahu apakah komunitas yang ditemukan bermakna?
Skor modularitas Q memberikan ukuran kualitas internal data; nilai di atas kira-kira 0.3–0.5 menunjukkan struktur komunitas yang tidak sepele. Selain itu, komunitas harus divalidasi terhadap pengetahuan domain, atribut simpul, atau label eksternal. Q tinggi saja tidak membuktikan signifikansi sosiologis atau biologis.
Apa yang terjadi jika hasil berbeda antar eksekusi?
Optimasi modularitas adalah heuristik dan eksekusi yang berbeda dapat menghasilkan partisi yang sedikit berbeda, terutama di Louvain. Jalankan algoritma berkali-kali (minimal 10–100 eksekusi pada jaringan besar) dan laporkan partisi dengan Q tertinggi. Leiden lebih stabil daripada Louvain karena langkah penyempurnaan lebih menyeluruh, tetapi eksekusi berulang tetap merupakan praktik yang baik.
Metode terkait
Sumber
Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.
Buka referensi DOIDisalin.Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.
Buka referensi publikasiDisalin.