Deteksi Komunitas

Topik ini membahas deteksi komunitas (community detection) pada graf dengan pustaka GDS, yaitu pembagian node menjadi kelompok yang relasi di dalamnya lebih rapat daripada relasi ke luar. Dua algoritma dibahas berurutan, yaitu Label Propagation yang cepat dan hanya membaca struktur relasi, serta Louvain yang mengoptimalkan modularitas secara bertingkat. Keduanya dijalankan dalam mode stream atas proyeksi tak berarah milik modul ini, kemudian perbedaan perilakunya menjadi dasar pemilihan. Setelah topik ini dibaca, kedua algoritma dapat dijalankan pada graf lain beserta penilaian mutu partisinya.

Komunitas dan dataset contoh#

Komunitas (community) pada graf adalah kumpulan node yang relasi di antara anggotanya jauh lebih banyak daripada relasi yang keluar menuju node lain. Deteksi komunitas membagi seluruh node menjadi partisi, yaitu pembagian yang menempatkan setiap node tepat pada satu komunitas. Kedua algoritma pada topik ini menemukan struktur tersebut dari pola relasi semata, tanpa label kelompok yang diberikan lebih dahulu.

Jaringan sosial contoh milik modul ini memuat delapan anggota pada label :Anggota yang dihubungkan dua belas relasi :TERHUBUNG. Relasi-relasi itu membentuk dua kelompok rapat, yaitu kelompok besar beranggota lima dan kelompok kecil beranggota tiga, yang tersambung oleh satu relasi penghubung antara Cinta dan Dimas. Dataset ini juga dimuat pada topik sentralitas, dan berkas setup.cypher berikut membangunnya kembali secara idempoten (idempotent), artinya aman dijalankan berulang karena MERGE hanya menambahkan data yang belum ada.

// Dataset contoh topik Deteksi komunitas: jaringan sosial dua klub
// dengan delapan anggota dan relasi TERHUBUNG tanpa properti bobot.
// Skrip ini idempoten (idempotent), artinya aman dijalankan berulang kali.

// Node anggota: label :Anggota dengan properti name.
MERGE (:Anggota {name: "Yuni"});
MERGE (:Anggota {name: "Zaki"});
MERGE (:Anggota {name: "Ayu"});
MERGE (:Anggota {name: "Bagas"});
MERGE (:Anggota {name: "Cinta"});
MERGE (:Anggota {name: "Dimas"});
MERGE (:Anggota {name: "Esa"});
MERGE (:Anggota {name: "Fira"});

// Relasi TERHUBUNG antar anggota klub sastra.
MATCH (a:Anggota {name: "Yuni"}), (b:Anggota {name: "Zaki"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Yuni"}), (b:Anggota {name: "Ayu"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Zaki"}), (b:Anggota {name: "Ayu"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Yuni"}), (b:Anggota {name: "Bagas"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Ayu"}), (b:Anggota {name: "Bagas"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Zaki"}), (b:Anggota {name: "Bagas"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Bagas"}), (b:Anggota {name: "Cinta"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Cinta"}), (b:Anggota {name: "Yuni"})
  MERGE (a)-[:TERHUBUNG]->(b);

// Relasi TERHUBUNG antar anggota klub fotografi.
MATCH (a:Anggota {name: "Dimas"}), (b:Anggota {name: "Esa"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Esa"}), (b:Anggota {name: "Fira"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Fira"}), (b:Anggota {name: "Dimas"})
  MERGE (a)-[:TERHUBUNG]->(b);

// Satu relasi penghubung antara kedua klub.
MATCH (a:Anggota {name: "Cinta"}), (b:Anggota {name: "Dimas"})
  MERGE (a)-[:TERHUBUNG]->(b);

# tidak-dijalankan
# memuat dataset jaringan sosial dari berkas setup.cypher ke dalam basis data
cat setup.cypher | cypher-shell -u neo4j

Jumlah node dan relasi diverifikasi dengan kueri berikut agar analitik dimulai dari isi basis data yang diketahui.

MATCH (a:Anggota)
WITH count(a) AS jumlahAnggota
MATCH ()-[r:TERHUBUNG]->()
RETURN jumlahAnggota, count(r) AS jumlahRelasi;

jumlahAnggota, jumlahRelasi
8, 12

Proyeksi graf tak berarah#

Label Propagation dan Louvain menimbang kedekatan antar tetangga tanpa memandang arah relasi tersimpan, sehingga proyeksinya dibuat tak berarah (undirected). Orientasi itu dinyatakan pada konfigurasi proyeksi, bukan pada data. Kueri berikut memproyeksikan label Anggota dan tipe relasi TERHUBUNG ke dalam proyeksi bernama komunitas-m7 dengan nilai orientation: 'UNDIRECTED'.

CALL gds.graph.project(
  'komunitas-m7',
  'Anggota',
  {TERHUBUNG: {orientation: 'UNDIRECTED'}}
)
YIELD graphName, nodeCount, relationshipCount
RETURN graphName, nodeCount, relationshipCount;

graphName, nodeCount, relationshipCount
"komunitas-m7", 8, 24

Keluaran melaporkan 24 relasi untuk data yang hanya memuat 12 karena setiap relasi dimuat dua arah sekaligus, yaitu arah aslinya dan arah baliknya, dan angka dua kali lipat itu wajar pada proyeksi tak berarah. Relasi contoh tidak membawa bobot, sehingga konfigurasi properti tidak diperlukan dan kedua algoritma membaca struktur relasinya semata. Proyeksi yang sama digunakan oleh kedua algoritma pada bagian berikutnya, lalu disingkirkan pada akhir topik.

Label Propagation#

Label Propagation menemukan komunitas melalui penyebarluasan label antar node bertetangga. Setiap node memulai dari labelnya sendiri, lalu pada setiap iterasi menggantinya dengan label yang paling banyak dimiliki tetangga. Keadaan seri dipecahkan secara sewenang-wenang, dan algoritma berhenti saat label sudah stabil atau jumlah iterasi maksimum tercapai, dengan default maxIterations bernilai 10.

Mode stream mengembalikan satu baris per node berisi communityId. Nilai tersebut tidak bermakna dan dapat berubah antar jalankan, sehingga kueri berikut langsung mengagregasinya menjadi daftar anggota per komunitas.

CALL gds.labelPropagation.stream('komunitas-m7')
YIELD nodeId, communityId
WITH communityId, gds.util.asNode(nodeId).name AS nama
ORDER BY communityId, nama
WITH communityId, collect(nama) AS anggota
RETURN size(anggota) AS ukuran, anggota
ORDER BY ukuran DESC, anggota;

ukuran, anggota
8, ["Ayu", "Bagas", "Cinta", "Dimas", "Esa", "Fira", "Yuni", "Zaki"]

Hasilnya adalah satu komunitas tunggal yang memuat seluruh anggota, bukan error melainkan sifat algoritmanya. Label salah satu kelompok menyebar hingga Cinta, melintasi relasi penghubung menuju Dimas, lalu menggantikan label kelompok yang lebih kecil. Label Propagation tidak memiliki ukuran mutu yang menilai kerugian peleburan itu, sehingga partisinya berhenti pada konsensus pertama yang tercapai.

CALL gds.labelPropagation.stats('komunitas-m7')
YIELD ranIterations, didConverge, communityCount
RETURN ranIterations, didConverge, communityCount;

ranIterations, didConverge, communityCount
2, TRUE, 1

Louvain#

Louvain menemukan komunitas dengan mengoptimalkan modularitas (modularity), yaitu ukuran mutu yang membandingkan kepadatan relasi di dalam komunitas dengan jaringan acak yang berstruktur sama. Algoritmanya bertingkat (hierarchical), yaitu node berpindah komunitas selama modularitas masih naik, komunitas yang terbentuk dilebur menjadi node perwakilan, lalu proses yang sama dijalankan pada graf yang memadat. Konfigurasi includeIntermediateCommunities menyimpan komunitas tiap tingkat, sedangkan defaultnya hanya menyimpan komunitas tingkat akhir.

Kueri berikut menjalankan Louvain dengan pola agregasi yang sama seperti pada Label Propagation.

CALL gds.louvain.stream('komunitas-m7')
YIELD nodeId, communityId
WITH communityId, gds.util.asNode(nodeId).name AS nama
ORDER BY communityId, nama
WITH communityId, collect(nama) AS anggota
RETURN size(anggota) AS ukuran, anggota
ORDER BY ukuran DESC, anggota;

ukuran, anggota
5, ["Ayu", "Bagas", "Cinta", "Yuni", "Zaki"]
3, ["Dimas", "Esa", "Fira"]

Partisinya terdiri atas dua komunitas, yaitu kelompok besar beranggota lima dan kelompok kecil beranggota tiga, persis seperti struktur kelompok pada dataset. Angka agregatnya diambil dari mode stats.

CALL gds.louvain.stats('komunitas-m7')
YIELD communityCount, modularity, ranLevels
RETURN communityCount, modularity, ranLevels;

communityCount, modularity, ranLevels
2, 0.32986111111111116, 1

Modularitas partisi dua komunitas ini mencapai 0.32986111111111116, sedangkan partisi satu komunitas seperti hasil Label Propagation memiliki modularitas nol karena seluruh relasi berada di dalam satu komunitas. Louvain menolak peleburan yang menurunkan modularitas, sehingga kedua kelompok tetap terpisah.

Analitik sudah selesai, sehingga proyeksinya disingkirkan dan daftar proyeksi diperiksa kembali.

CALL gds.graph.drop('komunitas-m7')
YIELD graphName, nodeCount, relationshipCount
RETURN graphName, nodeCount, relationshipCount;

graphName, nodeCount, relationshipCount
"komunitas-m7", 8, 24

CALL gds.graph.list()
YIELD graphName
RETURN count(graphName) AS jumlahProyeksi;

jumlahProyeksi
0

Daftar proyeksi yang kembali kosong menandakan memori analitik telah dilepaskan.

Memilih antara Label Propagation dan Louvain#

Kedua algoritma membaca proyeksi yang sama, tetapi kecepatan dan mutu hasilnya tidak setara. Tabel berikut merangkum perbedaannya.

Label Propagation dipilih untuk penjelajahan awal atas graf sangat besar ketika gambaran kasar dibutuhkan secepat mungkin. Louvain dipilih apabila partisi menjadi dasar keputusan, misalnya kelompok pada jaringan sosial untuk analisis lanjutan. Pada graf yang membawa bobot relasi, keduanya juga dapat membaca relationshipWeightProperty, sehingga pilihan algoritma tidak bergantung pada keberadaan bobot. Pada jaringan sekecil contoh ini, perbedaan waktu keduanya tidak signifikan, sedangkan pada graf berjuta relasi pilihan ini menentukan lama komputasi. Dataset modul ini memperlihatkan perbedaan mutunya, yaitu Label Propagation meleburkan kedua kelompok menjadi satu komunitas, sedangkan Louvain memisahkannya sesuai struktur yang sebenarnya.

Hubungan dengan teori klaster#

Pengelompokan (clustering) pada materi struktur data dan algoritma membagi sekumpulan objek menjadi klaster yang anggotanya saling serupa di dalam kelompok dan tidak serupa terhadap kelompok lain. Deteksi komunitas menerapkan kerangka yang sama pada graf, dengan keserupaan yang dinyatakan oleh konektivitas, yaitu keberadaan relasi, alih-alih jarak geometris antar objek. Konsep partisi beserta ukuran mutunya karenanya digunakan apa adanya dan tidak dibuktikan ulang pada topik ini, sedangkan peran ukuran mutu untuk graf diisi oleh modularitas.

Kasus paling sederhana terjadi apabila graf terputus menjadi beberapa bagian tanpa relasi penghubung sama sekali. Komunitasnya sama dengan komponen terhubung (connected component), sehingga algoritma komunitas tidak diperlukan. Jaringan contoh sengaja dibuat tetap terhubung melalui satu relasi penghubung, sehingga pemisahan kelompok hanya dapat ditemukan dengan menimbang kedekatan relasi, dan di situ perbedaan perilaku kedua algoritma terlihat. Istilah klaster dan komunitas karenanya sering dipertukarkan pada praktik, dengan komunitas sebagai istilah yang lazim untuk graf.

Kesalahan umum#

Empat kesalahan berikut paling sering muncul saat topik ini dipraktikkan, masing-masing disertai penyebab dan perbaikannya.

1. Proyeksi dibuat tanpa orientation: 'UNDIRECTED' untuk Label Propagation. Algoritma tetap berjalan, tetapi berhenti pada batas iterasi dengan didConverge bernilai FALSE dan partisinya terfragmentasi. Perbaikannya adalah memproyeksikan ulang graf dengan orientasi tersebut.
2. Nilai communityId disimpan atau dibandingkan sebagai data permanen, padahal nilainya sewenang-wenang dan dapat berubah antar jalankan. Perbaikannya adalah mengagregasi keluaran stream menjadi keanggotaan komunitas atau membaca angka agregat dari mode stats.
3. Proyeksi komunitas-m7 dibiarkan terpasang setelah analitik selesai, sehingga memori analitik tetap terpakai. Perbaikannya adalah menutup setiap sesi analitik dengan gds.graph.drop, lalu memastikan gds.graph.list() kembali kosong.
4. Label salah eja pada gds.graph.project, umumnya karena berkas setup.cypher belum dijalankan. Proyeksi atas label yang tidak memiliki node ditolak dengan pesan error Invalid node projection, one or more labels not found: 'AnggotaXX'. Perbaikannya adalah menjalankan berkas setup.cypher lebih dahulu atau menyamakan ejaan label dengan isi basis data.

Ringkasan#

• Komunitas adalah kumpulan node yang relasi internalnya lebih rapat daripada relasi keluar, dan deteksi komunitas membagi node menjadi partisi.
• Label Propagation menyalin label mayoritas tetangga sampai konsensus tercapai, cepat tetapi tanpa ukuran mutu, sehingga dapat meleburkan kelompok yang terhubung lemah.
• Louvain mengoptimalkan modularitas secara bertingkat dan pada dataset modul ini menemukan kedua kelompok dengan modularitas 0.32986111111111116.
• Nilai communityId sewenang-wenang, sehingga keluaran stream diagregasi menjadi keanggotaan komunitas, dan proyeksi ditutup dengan gds.graph.drop.

Referensi#

• Label Propagation — Neo4j Docs — Mekanisme penyebaran label mayoritas, default maxIterations, dan arti didConverge.
• Louvain — Neo4j Docs — Definisi modularitas, sifat bertingkat algoritma, dan konfigurasi includeIntermediateCommunities.
• Native projection — Neo4j Docs — Konfigurasi gds.graph.project, termasuk orientation untuk relasi tak berarah.