Sentralitas

PageRank dan betweenness untuk menjawab node mana yang penting dalam graf.

Daftar isi

Sentralitas (centrality) mengukur kepentingan sebuah node dalam graf dari struktur koneksinya. Topik ini membahas dua algoritma sentralitas pada GDS, yaitu PageRank yang menilai kepentingan dari arus tautan dan betweenness yang menilai posisi node sebagai penghubung antar bagian graf. Keduanya dijalankan atas dua dataset milik modul ini mengikuti siklus kerja yang sama, yaitu memproyeksikan graf, menjalankan algoritma mode stream, lalu menyingkirkan proyeksinya. Setelah topik ini dibaca, kedua algoritma dapat dipilih dan dijalankan sesuai pertanyaannya.

Dua dataset untuk sentralitas#

Modul ini menyediakan dua dataset dan topik ini menggunakan keduanya. Dataset pertama adalah jaringan transportasi dengan node :Pemberhentian dan relasi :KE berarah yang membawa properti jarak, digunakan untuk betweenness karena arah rute dan panjang jarak menentukan jalur terpendeknya. Dataset kedua adalah graf keterhubungan dengan node :Anggota dan relasi :TERHUBUNG atas delapan anggota, yaitu Ayu, Bagas, Cinta, Dimas, Esa, Fira, Yuni, dan Zaki, melalui dua belas relasi. Relasi pertemanan bersifat timbal balik, sehingga graf ini diproyeksikan tanpa arah untuk PageRank.

Kedua dataset dimuat dari berkas setup.cypher berikut yang idempoten (idempotent), sehingga aman dijalankan berulang kali. Bagian jaringan transportasinya identik dengan berkas setup.cypher pada topik lain dalam modul ini. Sintaksnya telah dibahas pada modul Fundamental Cypher, sehingga skrip ini cukup dijalankan apa adanya. Berkas ini memuat seluruh dataset modul, sehingga isi basis data dapat dibangun ulang dari nol.

cypher setup.cypher

// Dataset contoh modul Algoritma graf dengan GDS: dua graf kecil untuk
// analitik sentralitas.
// Dataset pertama: jaringan transportasi mini dengan delapan pemberhentian
// dan relasi KE berbobot jarak, identik dengan berkas setup.cypher pada
// topik Pustaka GDS.
// Dataset kedua: graf keterhubungan anggota dengan relasi TERHUBUNG.
// Skrip ini idempoten (idempotent), artinya aman dijalankan berulang kali.

// Node pemberhentian: label :Pemberhentian dengan properti name.
MERGE (:Pemberhentian {name: "Mangga"});
MERGE (:Pemberhentian {name: "Melati"});
MERGE (:Pemberhentian {name: "Cemara"});
MERGE (:Pemberhentian {name: "Kenanga"});
MERGE (:Pemberhentian {name: "Cempaka"});
MERGE (:Pemberhentian {name: "Anggrek"});
MERGE (:Pemberhentian {name: "Flamboyan"});
MERGE (:Pemberhentian {name: "Bougenvil"});

// Relasi KE berarah antar pemberhentian, dengan properti jarak dalam kilometer.
MATCH (a:Pemberhentian {name: "Mangga"}), (b:Pemberhentian {name: "Melati"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 3;
MATCH (a:Pemberhentian {name: "Melati"}), (b:Pemberhentian {name: "Cemara"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 2;
MATCH (a:Pemberhentian {name: "Cemara"}), (b:Pemberhentian {name: "Kenanga"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 4;
MATCH (a:Pemberhentian {name: "Kenanga"}), (b:Pemberhentian {name: "Cempaka"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 2;
MATCH (a:Pemberhentian {name: "Cempaka"}), (b:Pemberhentian {name: "Anggrek"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 5;
MATCH (a:Pemberhentian {name: "Anggrek"}), (b:Pemberhentian {name: "Flamboyan"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 3;
MATCH (a:Pemberhentian {name: "Flamboyan"}), (b:Pemberhentian {name: "Bougenvil"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 2;
MATCH (a:Pemberhentian {name: "Bougenvil"}), (b:Pemberhentian {name: "Mangga"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 4;
MATCH (a:Pemberhentian {name: "Melati"}), (b:Pemberhentian {name: "Anggrek"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 6;
MATCH (a:Pemberhentian {name: "Cemara"}), (b:Pemberhentian {name: "Anggrek"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 9;
MATCH (a:Pemberhentian {name: "Kenanga"}), (b:Pemberhentian {name: "Bougenvil"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 7;
MATCH (a:Pemberhentian {name: "Cempaka"}), (b:Pemberhentian {name: "Melati"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 8;

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

// Relasi TERHUBUNG antar anggota, satu relasi per pasangan. Sifat tak berarah
// grafnya ditentukan pada konfigurasi proyeksi, bukan pada data.
MATCH (a:Anggota {name: "Ayu"}), (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: "Dimas"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Cinta"}), (b:Anggota {name: "Yuni"})
  MERGE (a)-[:TERHUBUNG]->(b);
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);
MATCH (a:Anggota {name: "Yuni"}), (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: "Yuni"}), (b:Anggota {name: "Zaki"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Zaki"}), (b:Anggota {name: "Ayu"})
  MERGE (a)-[:TERHUBUNG]->(b);
MATCH (a:Anggota {name: "Zaki"}), (b:Anggota {name: "Bagas"})
  MERGE (a)-[:TERHUBUNG]->(b);

bash

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

Ketersediaan kedua dataset diverifikasi dengan menghitung node pada label yang digunakan topik ini, dan hasilnya menegaskan delapan node per label.

cypher

MATCH (n)
WHERE n:Pemberhentian OR n:Anggota
RETURN labels(n)[0] AS label, count(*) AS jumlah
ORDER BY label;

text Keluaran

label, jumlah
"Anggota", 8
"Pemberhentian", 8

PageRank: kepentingan dari arus tautan#

PageRank menilai kepentingan sebuah node dari arus yang mengalir masuk melalui tautan. Setiap node menyebarkan skornya secara merata ke seluruh tautan keluarnya, sehingga tautan dari node dengan sedikit koneksi membawa arus lebih besar per tautan dibandingkan tautan dari node dengan banyak koneksi. Pembaruan dijalankan secara iteratif, artinya skor tiap node dihitung ulang dari skor sebelumnya sampai perubahan seluruh skor sangat kecil atau jumlah iterasi maksimum tercapai. Bentuk pembaruannya sebagai berikut.

PR(A) = (1-d) + d \sum_{i=1}^{n} \frac{PR(T_i)}{C(T_i)}

Pada rumus tersebut, $T_1$ hingga $T_n$ adalah node yang menaut ke $A$ , sedangkan $C(T_i)$ menyatakan jumlah tautan keluar dari $T_i$ . Parameter dampingFactor menyatakan damping factor, yakni porsi arus yang tetap mengikuti tautan, sedangkan sisanya disebar merata sebagai lompatan acak ke node sembarang. Nilainya berkisar dari nol sampai mendekati satu, dan default GDS adalah 0.85. Semakin kecil nilainya, semakin besar porsi lompatan acak, sehingga skor antar node saling mendekat.

Proyeksi PageRank dibuat atas graf keterhubungan dengan orientasi UNDIRECTED agar setiap relasi TERHUBUNG dapat dilalui dua arah.

cypher

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

text Keluaran

graphName, nodeCount, relationshipCount
"sentralitas-pr-m7", 8, 24

Algoritma dijalankan dalam mode stream dengan dampingFactor eksplisit. Skor dibulatkan ke tiga angka desimal melalui round(skor * 1000) / 1000 agar keluarannya pendek, sedangkan urutan ditentukan menurun menurut skor lalu menaik menurut nama.

cypher

CALL gds.pageRank.stream('sentralitas-pr-m7', {dampingFactor: 0.85})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS nama, round(score * 1000) / 1000 AS skor
ORDER BY skor DESC, nama ASC;

text Keluaran

nama, skor
"Bagas", 1.16
"Yuni", 1.16
"Dimas", 1.079
"Cinta", 0.943
"Ayu", 0.889
"Zaki", 0.889
"Esa", 0.786
"Fira", 0.786

Bagas dan Yuni menempati urutan teratas karena memiliki empat koneksi, sedangkan Esa dan Fira menutup daftar dengan dua koneksi. Pembeda yang lebih penting terlihat pada Dimas yang mencapai 1.079 dan mengungguli Cinta, Ayu, serta Zaki yang juga memiliki tiga koneksi, karena tetangganya, Esa dan Fira, hanya memiliki sedikit koneksi sehingga arus per tautannya lebih besar. Perilaku ini membedakan PageRank dari penghitungan tautan semata.

Pengaruh dampingFactor diperlihatkan dengan menjalankan algoritma yang sama pada proyeksi yang masih terpasang, kali ini dengan nilai 0.7, lalu menampilkan Bagas sebagai skor teratas dan Esa sebagai skor terendah.

cypher

CALL gds.pageRank.stream('sentralitas-pr-m7', {dampingFactor: 0.7})
YIELD nodeId, score
WITH gds.util.asNode(nodeId).name AS nama, round(score * 1000) / 1000 AS skor
WHERE nama IN ['Bagas', 'Esa']
RETURN nama, skor
ORDER BY nama;

text Keluaran

nama, skor
"Bagas", 1.158
"Esa", 0.868

Skor Bagas turun dari 1.16 ke 1.158, sedangkan skor Esa naik dari 0.786 ke 0.868. Porsi lompatan acak yang lebih besar menekan seluruh skor ke arah rata-rata, sehingga pembedaan antar node menyempit, tetapi urutan keduanya tidak berubah.

Betweenness: node penghubung antar bagian graf#

Betweenness menilai node dari posisinya sebagai penghubung. Skor sebuah node adalah jumlah jalur terpendek antar semua pasangan node yang melewatinya, sehingga skor tinggi menandai titik yang menyambung bagian-bagian graf. Apabila node berskor tinggi dihapus, banyak pasangan kehilangan jalur pendeknya, bahkan sebagian kehilangan koneksinya sama sekali. Ukuran ini cocok untuk mencari titik rawan pada jaringan transportasi maupun kemacetan pada jaringan komputer.

Pada jaringan transportasi modul ini, jalur terpendek dihitung menurut properti jarak, sehingga proyeksinya membawa jarak melalui relationshipProperties dan algoritmanya menerima relationshipWeightProperty. Arah rute turut diperhatikan, sehingga orientasinya DIRECTED. Mesin penghitung jalur terpendek di dalam betweenness adalah Dijkstra, yang teori lengkapnya dibahas pada materi struktur data dan algoritma, sehingga algoritma ini digunakan tanpa dibuktikan ulang.

cypher

CALL gds.graph.project(
  'sentralitas-bc-m7',
  'Pemberhentian',
  'KE',
  {relationshipProperties: 'jarak'}
)
YIELD graphName, nodeCount, relationshipCount
RETURN graphName, nodeCount, relationshipCount;

text Keluaran

graphName, nodeCount, relationshipCount
"sentralitas-bc-m7", 8, 12

Algoritma betweenness kemudian dijalankan dalam mode stream dengan pembulatan dan pengurutan yang sama.

cypher

CALL gds.betweenness.stream('sentralitas-bc-m7', {relationshipWeightProperty: 'jarak'})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS nama, round(score * 1000) / 1000 AS skor
ORDER BY skor DESC, nama ASC;

text Keluaran

nama, skor
"Melati", 21.0
"Bougenvil", 15.0
"Mangga", 15.0
"Anggrek", 11.0
"Cemara", 11.0
"Flamboyan", 11.0
"Kenanga", 9.0
"Cempaka", 5.0

Melati memperoleh skor tertinggi, yaitu 21.0, karena jalur terpendek dari Mangga menuju hampir semua pemberhentian lain melewatinya, demikian pula jalur dari sisi Anggrek, Flamboyan, dan Bougenvil menuju sisi barat lingkar rute. Sebaliknya, Cempaka mencatat skor terendah, yaitu 5.0, karena pintasan Melati menuju Anggrek memungkinkan banyak jalur menghindarinya. Bougenvil dan Mangga sama-sama memperoleh 15.0 karena jalur yang menyambung kedua sisi lingkar wajib melintasi keduanya.

Analisis kedua algoritma sudah selesai, sehingga kedua proyeksi disingkirkan dan katalog diperiksa kembali.

cypher

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

text Keluaran

graphName, nodeCount, relationshipCount
"sentralitas-pr-m7", 8, 24

cypher

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

text Keluaran

graphName, nodeCount, relationshipCount
"sentralitas-bc-m7", 8, 12

cypher

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

text Keluaran

jumlahProyeksi
0

Daftar proyeksi kembali kosong, sesuai kebiasaan kerja GDS untuk melepaskan memori analitik segera setelah digunakan.

Memilih antara PageRank dan betweenness#

Kedua algoritma menjawab pertanyaan yang berbeda, sehingga pilihannya mengikuti pertanyaannya. PageRank mengukur pengaruh kumulatif yang mengalir melalui tautan dan cocok untuk mencari node yang paling banyak menerima tautan. Betweenness mengukur posisi penghubung dan cocok untuk mencari titik yang menyatukan bagian graf atau rawan memutus konektivitas apabila hilang.

Aspek	PageRank	Betweenness
Pertanyaan yang dijawab	node mana yang paling berpengaruh dari arus tautan	node mana yang menjadi penghubung antar bagian graf
Dasar skor	arus dari tautan masuk, dihitung iteratif	jumlah jalur terpendek yang melewati node
Graf yang cocok	jaringan tautan yang dapat diperlakukan tanpa arah	jaringan perjalanan atau aliran berarah dan berbobot
Contoh pada modul	keterhubungan anggota, orientasi `UNDIRECTED`	jaringan transportasi, bobot `jarak`

Contoh pada modul ini memperlihatkan perbedaan praktis antara keduanya. PageRank berjalan atas proyeksi tanpa arah dan tanpa bobot, sedangkan betweenness menuntut arah rute dan bobot jarak. Karena satuannya berbeda, angka kedua algoritma tidak dandingkan secara langsung.

Kesalahan umum#

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

Betweenness dijalankan atas proyeksi UNDIRECTED pada jaringan yang sebenarnya berarah. Arah rute hilang dari perhitungan, sehingga jalur terpendek dihitung pada graf yang berbeda dari kenyataan. Skornya sah secara komputasi, tetapi tidak lagi menggambarkan arah perjalanan. Perbaikannya adalah memproyeksikan dengan orientasi DIRECTED sebagaimana contoh.
Proyeksi membawa properti jarak, tetapi pemanggilan algoritma tidak menyebut relationshipWeightProperty. Semua relasi diperlakukan sama berat, sehingga jalur terpendek ditentukan oleh jumlah relasi dan bukan oleh kilometer. Perbaikannya adalah menyebut konfigurasi tersebut pada setiap pemanggilan.
Skor PageRank dan betweenness dandingkan sebagai ukuran setara. Keduanya berbeda satuan, sehingga nilai 1.16 pada PageRank tidak berarti lebih kecil dari 21.0 pada betweenness. Perbaikannya adalah memilih algoritma menurut pertanyaannya, bukan membandingkan angkanya.
Proyeksi dibiarkan terpasang setelah analisis selesai. Memori analitik tetap terpakai meskipun proyeksinya tidak digunakan lagi. Perbaikannya adalah menjadikan gds.graph.drop penutup tetap setiap sesi, lalu memastikan lewat gds.graph.list().

Ringkasan#

PageRank menilai kepentingan node dari arus tautan yang dihitung secara iteratif, dengan dampingFactor mengatur porsi lompatan acak dan bernilai default 0.85.
Skor PageRank memperhitungkan bentuk koneksi tetangga, sehingga node dengan jumlah koneksi yang sama dapat memperoleh skor berbeda.
Betweenness menghitung jumlah jalur terpendek yang melewati sebuah node, dan arah serta bobotnya dijaga melalui orientasi proyeksi beserta relationshipWeightProperty.
Kedua algoritma dipilih menurut pertanyaannya, yaitu pengaruh kumulatif untuk PageRank dan posisi penghubung untuk betweenness, lalu proyeksinya disingkirkan setelah selesai.

Referensi#

PageRank — Neo4j Docs — Konfigurasi dampingFactor beserta rentang nilainya dan sifat pembaruan iteratif PageRank pada GDS.
Betweenness Centrality — Neo4j Docs — Definisi betweenness dan konfigurasi relationshipWeightProperty untuk jalur terpendek berbobot.