Apa Itu Leiden Algorithm? Pengertian, Cara Kerja, Kelebihan, dan Contohnya

Ketika kita melihat sebuah jaringan yang sangat besar, memahami hubungan di dalamnya bisa menjadi pekerjaan yang sulit.

Bayangkan sebuah media sosial dengan jutaan pengguna, jaringan sitasi yang berisi jutaan artikel ilmiah, jaringan transaksi yang menghubungkan pelanggan dan produk, atau jaringan halaman web yang saling terhubung melalui internal link.

Pada jaringan seperti itu, biasanya terdapat kelompok-kelompok node yang memiliki hubungan lebih kuat satu sama lain dibandingkan dengan hubungan mereka terhadap node di kelompok lain.

Masalahnya adalah: bagaimana menemukan kelompok tersebut secara otomatis?

Di sinilah Leiden Algorithm digunakan.

Leiden Algorithm adalah algoritma untuk community detection, yaitu proses menemukan struktur komunitas di dalam sebuah jaringan atau graph. Algoritma ini diperkenalkan oleh Vincent A. Traag, Ludo Waltman, dan Nees Jan van Eck melalui penelitian From Louvain to Leiden: guaranteeing well-connected communities yang diterbitkan di Scientific Reports pada 2019. Nama Leiden diambil dari lokasi institusi para penulis di Leiden, Belanda.

Secara sederhana, Leiden mencoba menjawab pertanyaan:

"Dari sekian banyak node dan hubungan dalam sebuah jaringan, kelompok mana yang secara struktural memiliki keterikatan lebih kuat?"

Leiden memiliki hubungan yang sangat erat dengan Louvain Algorithm, tetapi dirancang untuk mengatasi kelemahan penting pada Louvain, terutama kemungkinan terbentuknya komunitas yang terhubung dengan buruk atau bahkan terputus secara internal.

Memahami Leiden Algorithm dari Dasar

Sebelum membahas cara kerja Leiden, kita perlu memahami tiga konsep utama: graph, node, dan edge.

Dalam network science, sebuah graph biasanya terdiri dari:

• Node atau vertex → objek atau entitas yang ingin dianalisis.

• Edge → hubungan antara dua node.

• Edge weight → kekuatan hubungan, jika jaringan menggunakan bobot.

• Community → kelompok node yang memiliki struktur hubungan internal yang relatif kuat.

Misalnya kita membuat jaringan pertemanan.

Anggap terdapat 100 orang. Setiap orang menjadi satu node, sedangkan hubungan pertemanan menjadi edge.

Setelah dianalisis, mungkin terlihat bahwa:

• Kelompok A banyak berinteraksi satu sama lain.

• Kelompok B memiliki pola hubungan internal yang kuat.

• Kelompok C juga memiliki jaringan internal yang relatif padat.

Kita mungkin tidak mengetahui kelompok tersebut sebelumnya.

Leiden dapat mencoba menemukannya hanya berdasarkan struktur hubungan dalam graph. Inilah perbedaan penting dengan clustering pada dataset tabular.

Pada clustering biasa, kita sering bekerja dengan fitur seperti:

Customer
├── umur
├── pendapatan
├── frekuensi transaksi
└── total pembelian

Sementara Leiden bekerja terutama berdasarkan:

Node ─ Edge ─ Node ─ Edge ─ Node

Dengan kata lain:

Leiden mencari struktur kelompok berdasarkan hubungan dalam jaringan.

Apa Tujuan Utama Leiden Algorithm?

Tujuan Leiden adalah menemukan partition, yaitu pembagian node dalam graph menjadi beberapa komunitas berdasarkan suatu quality function.

Quality function digunakan untuk menilai seberapa baik sebuah partition.

Beberapa objective function yang dapat digunakan dalam implementasi Leiden antara lain:

• Modularity

• Constant Potts Model atau CPM

• RBConfiguration

• Significance

• Surprise

• objective lainnya, tergantung implementasi yang digunakan

Dalam leidenalg, berbagai objective tersebut tersedia melalui beberapa jenis VertexPartition.

Secara intuitif, algoritma berusaha menemukan struktur seperti:

Community A

●──●──●
│ ╲ │
●──●──●


       hubungan antar-komunitas lebih sedikit


Community B

●──●──●
│ ╲ │
●──●──●

Yang perlu dipahami adalah bahwa Leiden tidak memiliki definisi universal tentang "komunitas yang benar".

Hasilnya bergantung pada:

• graph yang diberikan,

• edge dan bobotnya,

• objective function,

• resolution parameter,

• jumlah iterasi,

• random seed,

• serta karakteristik jaringan.

Jadi Leiden bukan mesin yang mengetahui kelompok "sebenarnya" secara absolut. Ia mencari partition yang baik menurut objective yang dipilih.

Mengapa Leiden Algorithm Dibuat?

Untuk memahami Leiden, kita perlu melihat algoritma yang sangat terkenal sebelumnya, yaitu Louvain Algorithm.

Louvain juga digunakan untuk community detection dan secara umum bekerja melalui dua fase:

1. Memindahkan node antar-komunitas untuk meningkatkan quality function.

2. Mengagregasikan komunitas menjadi node pada graph yang lebih sederhana.

Proses tersebut kemudian diulang.

Masalahnya adalah penelitian Traag, Waltman, dan van Eck menunjukkan bahwa Louvain dapat menghasilkan komunitas yang terhubung dengan sangat buruk, bahkan dalam beberapa kondisi komunitas dapat terputus secara internal. Dalam eksperimen penelitian tersebut, hingga 25% komunitas pada jaringan tertentu ditemukan memiliki konektivitas yang buruk dan hingga 16% dapat terputus.

Bayangkan komunitas yang seharusnya berbentuk:

A ─ B ─ C ─ D

Namun hasil community detection justru:

A ─ B       C ─ D

Jika A, B, C, dan D tetap diberi label komunitas yang sama, maka komunitas tersebut sebenarnya memiliki dua bagian yang tidak terhubung.

Secara matematis, partition tersebut masih dapat memperoleh nilai objective yang baik.

Namun secara struktural, hasilnya bermasalah.

Leiden dirancang untuk mengatasi masalah tersebut.

Bagaimana Cara Kerja Leiden Algorithm?

Leiden memiliki tiga fase utama:

1. Local Moving of Nodes

2. Refinement of the Partition

3. Aggregation of the Network

Ketiga fase tersebut dijalankan secara iteratif.

Secara sederhana:

Graph awal
    ↓
Local Moving
    ↓
Refinement
    ↓
Aggregation
    ↓
Graph yang lebih sederhana
    ↓
Local Moving lagi
    ↓
Refinement lagi
    ↓
Aggregation lagi
    ↓
Berhenti ketika tidak ada peningkatan lebih lanjut

Namun, ada detail penting pada fase aggregation Leiden yang membedakannya dari Louvain: graph agregat dibangun berdasarkan partition hasil refinement, sementara partition non-refined digunakan sebagai partition awal pada graph agregat. Detail ini penting karena memberikan ruang bagi Leiden untuk menemukan partition dengan kualitas lebih tinggi.

Mari kita bahas satu per satu.

Fase 1: Local Moving

Pada awalnya, setiap node dapat dimulai sebagai komunitas tersendiri.

Misalnya:

A   B   C   D   E   F

Kemudian algoritma melihat hubungan antar-node.

Misalnya A memiliki hubungan kuat dengan B. Jika memindahkan A ke komunitas B meningkatkan quality function, perpindahan tersebut dapat dilakukan.

Hasilnya mungkin:

{A,B}   {C}   {D,E}   {F}

Proses tersebut berlanjut selama terdapat perpindahan yang meningkatkan quality function.

Leiden menggunakan fast local move procedure.

Ini merupakan salah satu perbaikan penting dibandingkan Louvain. Pada Louvain, node dapat terus dikunjungi meskipun lingkungannya tidak berubah. Leiden menggunakan mekanisme queue sehingga setelah suatu node dipindahkan, perhatian diarahkan terutama kepada node yang lingkungan atau neighborhood-nya berubah.

Secara sederhana:

Node berubah
     ↓
Tetangga yang terdampak masuk queue
     ↓
Periksa kembali node tersebut
     ↓
Pindahkan jika objective meningkat

Pendekatan ini membantu membuat proses local moving lebih efisien.

Fase 2: Refinement

Refinement adalah bagian yang paling membedakan Leiden dari Louvain.

Setelah local moving menghasilkan komunitas, Leiden tidak langsung menganggap komunitas tersebut sudah final.

Algoritma mencoba memperhalus struktur internal setiap komunitas.

Misalnya local moving menghasilkan:

Community A

A B C D E F

Namun struktur internal sebenarnya lebih menyerupai:

A ─ B ─ C

D ─ E ─ F

Refinement dapat menemukan bahwa komunitas tersebut lebih tepat direpresentasikan sebagai subkomunitas:

Community A1
A B C

Community A2
D E F

Yang penting, refinement tidak sekadar menjalankan clustering kedua secara bebas.

Refinement dimulai dari singleton partition di dalam komunitas sebelumnya, kemudian melakukan penggabungan lokal. Penggabungan hanya dilakukan di dalam komunitas yang sudah ditemukan pada partition sebelumnya dan mengikuti kondisi yang berkaitan dengan quality function serta connectivity.

Refinement juga tidak sepenuhnya greedy.

Dalam proses tertentu, komunitas tujuan dipilih secara acak dengan probabilitas yang dipengaruhi oleh peningkatan quality function. Semakin besar peningkatan kualitas, semakin besar kemungkinan komunitas tersebut dipilih. Parameter theta mengatur tingkat randomness dalam proses refinement pada formulasi asli Leiden.

Inilah salah satu alasan mengapa hasil Leiden dapat berbeda jika random seed berbeda.

Fase 3: Aggregation

Setelah refinement, Leiden membuat aggregate network.

Misalnya graph awal memiliki:

1.000 node

Kemudian ditemukan beberapa komunitas dan subkomunitas.

Graph tersebut dapat direpresentasikan sebagai graph yang lebih sederhana dengan node-node yang mewakili hasil refinement.

Secara konseptual:

Graph asli
1.000 nodes
      ↓
Community detection
      ↓
Communities
      ↓
Refinement
      ↓
Aggregate network

Graph baru tersebut kemudian dianalisis lagi.

Karena graph sudah lebih sederhana, proses berikutnya dapat dilakukan pada struktur yang lebih tinggi.

Inilah yang membuat Leiden dapat menghasilkan struktur komunitas secara hierarkis.

Apa Itu Community Detection?

Community detection adalah proses menemukan struktur komunitas dalam graph tanpa menentukan label komunitas terlebih dahulu.

Berbeda dengan supervised classification.

Pada classification, kita biasanya sudah memiliki label:

Data 1 → Kategori A
Data 2 → Kategori B
Data 3 → Kategori A

Pada community detection, kita hanya memiliki graph:

A──B──C
│  │
D──E

F──G──H
│     │
I─────J

Kemudian algoritma mencari struktur kelompok secara otomatis.

Hasilnya mungkin:

Community 1
A B C D E

Community 2
F G H I J

Karena label komunitas tidak diberikan sebelumnya, pendekatan ini umumnya dikategorikan sebagai unsupervised community detection.

Apa Itu Modularity?

Salah satu quality function yang paling populer dalam community detection adalah modularity.

Secara intuitif, modularity membandingkan:

berapa banyak hubungan yang benar-benar terjadi di dalam komunitas

dengan:

berapa banyak hubungan yang diharapkan muncul berdasarkan model null tertentu.

Bentuk modularity yang umum adalah:

Q = 1/(2m) Σij [Aij - (ki kj)/(2m)] δ(σi, σj)

Tidak perlu menghafalkan rumus tersebut untuk memahami konsep dasarnya.

Intinya:

• Aij merepresentasikan hubungan aktual antara node i dan j.

• ki dan kj berkaitan dengan degree node.

• m berkaitan dengan total edge weight.

• δ(σi, σj) menunjukkan apakah kedua node berada dalam komunitas yang sama.

Jika hubungan internal suatu komunitas jauh lebih banyak dibandingkan yang diharapkan berdasarkan model null, partition tersebut dapat memperoleh modularity yang lebih tinggi.

Dalam leidenalg, modularity tersedia melalui ModularityVertexPartition.

Namun penting untuk diingat:

Modularity yang lebih tinggi bukan berarti partition tersebut otomatis "benar" secara dunia nyata.

Modularity hanya menilai partition berdasarkan objective matematisnya.

Apa Itu Resolution Parameter?

Resolution parameter mengontrol skala komunitas yang ingin ditemukan.

Secara umum:

Resolution rendah
        ↓
lebih sedikit komunitas
        ↓
komunitas cenderung lebih besar

Sedangkan:

Resolution tinggi
        ↓
lebih banyak komunitas
        ↓
komunitas cenderung lebih kecil

Dokumentasi igraph menjelaskan hubungan tersebut secara langsung: resolution yang lebih tinggi cenderung menghasilkan lebih banyak komunitas yang lebih kecil, sedangkan resolution lebih rendah cenderung menghasilkan lebih sedikit komunitas yang lebih besar.

Misalnya:

Resolution = 0.1
→ 4 communities

Resolution = 0.5
→ 12 communities

Resolution = 1.0
→ 30 communities

Angka tersebut hanya ilustrasi.

Tidak ada satu nilai resolution yang benar untuk semua graph.

Pemilihannya harus disesuaikan dengan pertanyaan analisis.

Misalnya:

Pertanyaan 1:

"Apa saja kelompok besar dalam jaringan?"

Anda mungkin membutuhkan komunitas yang lebih besar.

Pertanyaan 2:

"Apa saja subkelompok kecil di dalam jaringan?"

Anda mungkin membutuhkan resolution yang lebih tinggi.

Jadi resolution sebaiknya diperlakukan sebagai parameter analisis, bukan sekadar tombol untuk mendapatkan jumlah cluster tertentu.

CPM sebagai Alternatif Modularity

Leiden juga dapat menggunakan Constant Potts Model atau CPM.

CPM menggunakan resolution parameter dengan formulasi yang berbeda dari modularity dan memiliki sifat penting: CPM tidak memiliki resolution-limit problem seperti yang dikenal pada modularity. Dokumentasi igraph secara eksplisit menyebut CPM sebagai objective yang tidak mengalami resolution limit tersebut.

Secara intuitif:

Modularity
→ membandingkan struktur aktual dengan model null

CPM
→ menggunakan fungsi berbasis kepadatan dan resolution

Karena itu, pemilihan antara modularity dan CPM bukan hanya persoalan library atau sintaks kode.

Keduanya mewakili cara berbeda dalam mendefinisikan partition yang dianggap berkualitas.

Untuk analisis yang serius, objective function sebaiknya dipilih berdasarkan karakteristik jaringan dan tujuan analisis.

Perbedaan Leiden dan Louvain

Perbandingan sederhananya:

Perbedaan paling penting bukan sekadar bahwa Leiden "lebih baru".

Leiden secara khusus dirancang untuk memperbaiki masalah badly connected communities pada Louvain. Paper asli memberikan jaminan bahwa komunitas yang dihasilkan Leiden terhubung pada setiap iterasi, serta jaminan tambahan mengenai kualitas struktur ketika algoritma terus diiterasikan.

Dalam benchmark penelitian asli, Leiden juga menunjukkan waktu eksekusi yang lebih rendah dan partition dengan kualitas lebih tinggi pada jaringan yang diuji. Pada beberapa jaringan empiris dalam eksperimen tersebut, perbedaan waktu bahkan mencapai sekitar 20 kali. Namun hasil tersebut adalah hasil benchmark penelitian, bukan jaminan bahwa Leiden selalu lebih cepat atau menghasilkan partition lebih baik pada setiap dataset.

Mengapa Refinement Sangat Penting?

Bayangkan sebuah jaringan:

A ─ B ─ C

D ─ E ─ F

Jika kedua bagian tersebut diberi label:

Community 1
A B C D E F

maka komunitas tersebut sebenarnya memiliki dua komponen.

Masalah seperti ini penting karena community detection sering digunakan untuk membuat interpretasi tentang node yang berada dalam komunitas yang sama.

Misalnya dalam citation network, komunitas dapat digunakan untuk mengidentifikasi kelompok artikel yang dianggap memiliki topik serupa.

Jika komunitas tersebut ternyata memiliki struktur internal yang sangat buruk, interpretasinya juga dapat menjadi bermasalah.

Refinement memberikan Leiden mekanisme untuk memperbaiki struktur tersebut sebelum proses aggregation dilanjutkan.

Apa Arti "Connected Community"?

Sebuah komunitas disebut terhubung apabila node-node di dalamnya dapat mencapai satu sama lain melalui jalur yang tetap berada di dalam komunitas tersebut.

Contoh:

A ─ B ─ C ─ D

Semua node terhubung.

Sedangkan:

A ─ B       C ─ D

memiliki dua komponen terpisah.

Jika semuanya diberi label komunitas yang sama, community tersebut tidak connected.

Salah satu kontribusi utama paper Leiden adalah memberikan jaminan matematis mengenai connectivity komunitas yang dihasilkan.

Perlu diperhatikan bahwa istilah dalam paper lebih kuat dan lebih spesifik daripada sekadar "connected". Leiden membahas properti seperti γ-connected, γ-separated, subpartition γ-dense, dan pada kondisi tertentu uniformly γ-dense serta subset optimal. Jadi, pernyataan populer bahwa "Leiden menjamin connected communities" adalah penyederhanaan dari teori tersebut.

Leiden pada Graph Berbobot

Leiden dapat digunakan pada graph berbobot.

Misalnya:

A ── B
    10

berarti hubungan A-B memiliki weight 10.

Sedangkan:

A ─ C
    2

berarti hubungan A-C memiliki weight 2.

Weight tersebut dapat digunakan untuk merepresentasikan kekuatan hubungan.

Contohnya pada jaringan transaksi:

Customer A ─ Customer B
             weight = 100

dapat berarti kedua customer memiliki tingkat kemiripan perilaku tertentu sebesar 100 berdasarkan definisi graph yang kita buat.

Dokumentasi igraph menjelaskan bahwa edge weight yang lebih besar diperlakukan sebagai hubungan yang lebih kuat pada fungsi community detection Leiden.

Hal ini penting karena dalam dunia nyata hubungan sering kali tidak bersifat biner.

Bukan hanya:

Ada hubungan
Tidak ada hubungan

tetapi:

Hubungan lemah
Hubungan sedang
Hubungan kuat

Apakah Leiden Harus Menggunakan Graph Berbobot?

Tidak.

Graph dapat berupa:

• graph tanpa bobot,

• graph berbobot,

• graph dengan node weight,

• serta struktur yang lebih kompleks, tergantung implementasi dan objective yang digunakan.

Jika tidak ada edge weight, setiap edge pada dasarnya dapat diperlakukan dengan bobot yang sama.

Yang jauh lebih penting adalah memastikan bahwa definisi edge memang relevan dengan pertanyaan analisis.

Leiden pada Temporal Network

Dalam temporal network, hubungan berubah dari waktu ke waktu.

Misalnya:

Januari
A ─ B ─ C

Februari
A ─ B ─ C ─ D

Maret
A ─ D ─ E

Community structure pada Januari belum tentu sama dengan Maret.

Dalam ekosistem Leiden, terdapat dukungan untuk skenario temporal dan multiplex pada implementasi tertentu.

Artinya analisis dapat dikembangkan dari:

"Siapa berada di komunitas mana?"

menjadi:

"Bagaimana struktur komunitas berubah dari waktu ke waktu?"

Ini sangat berguna untuk jaringan seperti:

• social network,

• collaboration network,

• communication network,

• transaction network,

• citation network.

Leiden Bersifat Random atau Deterministik?

Leiden memiliki komponen stokastik.

Dalam refinement, pemilihan komunitas tujuan melibatkan proses random yang dipengaruhi oleh peningkatan quality function. Karena itu, menjalankan algoritma dengan random seed berbeda dapat menghasilkan partition yang berbeda.

Contohnya:

Seed = 42
→ Community structure A

Seed = 123
→ Community structure B

Bukan berarti salah satu hasil otomatis salah.

Pada network yang memiliki beberapa partition yang hampir sama baiknya, variasi seperti ini dapat terjadi.

Karena itu, untuk analisis yang serius, sebaiknya:

1. menetapkan seed ketika membutuhkan reproducibility,

2. menjalankan beberapa seed ketika ingin menguji stabilitas,

3. membandingkan struktur komunitas antar-run.

Dalam leidenalg, parameter seed dapat digunakan untuk mengontrol randomisasi. Implementasi juga menyediakan parameter seperti n_iterations.

Apa Itu Number of Iterations?

Leiden bekerja secara iteratif.

Secara sederhana:

Iteration 1
↓
Partition A

Iteration 2
↓
Partition B

Iteration 3
↓
Partition C

Setiap iterasi dapat memperbaiki partition berdasarkan objective function.

Dalam dokumentasi igraph, n_iterations digunakan untuk menentukan jumlah iterasi Leiden dan setiap iterasi dapat meningkatkan partition.

Pada implementasi leidenalg, find_partition() memiliki default tertentu untuk jumlah iterasi, tetapi nilai default library tidak seharusnya dianggap sebagai aturan universal untuk semua analisis.

Untuk pekerjaan yang membutuhkan stabilitas, jumlah iterasi sebaiknya diuji bersama parameter lain.

Contoh Implementasi Python

Salah satu kombinasi library yang populer adalah:

• igraph untuk merepresentasikan graph.

• leidenalg untuk menjalankan algoritma Leiden.

Instalasi:

pip install igraph leidenalg

Contoh sederhana menggunakan modularity:

import igraph as ig
import leidenalg as la

# Membuat graph contoh
graph = ig.Graph.Famous("Zachary")

# Menjalankan Leiden dengan modularity
partition = la.find_partition(
    graph,
    la.ModularityVertexPartition,
    seed=42
)

print("Jumlah komunitas:", len(partition))
print("Membership:", partition.membership)

Output membership menunjukkan komunitas untuk setiap node.

Misalnya:

[0, 0, 1, 1, 2, 2, ...]

Artinya node pertama dan kedua berada pada komunitas 0, node berikutnya pada komunitas 1, dan seterusnya.

Pola penggunaan find_partition() tersebut sesuai dengan API leidenalg.

Menggunakan CPM

Jika ingin menggunakan Constant Potts Model:

import igraph as ig
import leidenalg as la

graph = ig.Graph.Famous("Zachary")

partition = la.find_partition(
    graph,
    la.CPMVertexPartition,
    resolution_parameter=0.1,
    seed=42
)

print("Jumlah komunitas:", len(partition))
print("Membership:", partition.membership)

Pada CPM, resolution parameter memiliki interpretasi yang berbeda dibandingkan modularity sehingga angka resolution tidak boleh dibandingkan secara langsung tanpa memahami objective function yang digunakan.

Menggunakan Edge Weight

Misalnya graph memiliki bobot:

import igraph as ig
import leidenalg as la

graph = ig.Graph(
    edges=[
        (0, 1),
        (1, 2),
        (2, 3),
        (0, 3)
    ]
)

graph.es["weight"] = [10, 8, 7, 2]

partition = la.find_partition(
    graph,
    la.ModularityVertexPartition,
    weights="weight",
    seed=42
)

print(partition.membership)

Dengan cara tersebut, algoritma tidak hanya melihat keberadaan edge, tetapi juga weight yang diberikan.

Namun jangan asal memberikan weight.

Weight harus memiliki arti yang jelas.

Misalnya:

weight = jumlah transaksi

atau:

weight = jumlah interaksi

atau:

weight = similarity score

Definisi tersebut akan menentukan apa sebenarnya arti community yang ditemukan.

Bagaimana Memilih Resolution yang Tepat?

Tidak ada satu angka resolution yang benar untuk semua graph.

Misalnya:

Resolution 0.1
→ 5 communities

Resolution 0.2
→ 8 communities

Resolution 0.5
→ 17 communities

Resolution 1.0
→ 30 communities

Pertanyaan yang benar bukan:

"Resolution mana yang menghasilkan jumlah komunitas paling bagus?"

Tetapi:

"Skala komunitas mana yang relevan dengan pertanyaan analisis saya?"

Misalnya pada organisasi:

Company
├── Division
│   ├── Department
│   └── Department

Jika kita ingin menemukan division, komunitas besar mungkin lebih relevan.

Jika kita ingin menemukan kelompok kerja informal, komunitas yang lebih kecil mungkin lebih berguna.

Karena itu, resolution harus diperlakukan sebagai bagian dari desain analisis.

Jangan Terjebak pada Angka Modularity

Kesalahan umum dalam community detection adalah menganggap:

"Modularity paling tinggi berarti komunitas paling benar."

Tidak sesederhana itu.

Modularity adalah objective function, bukan ground truth.

Sebuah partition dapat memiliki modularity tinggi tetapi belum tentu memiliki interpretasi bisnis yang berguna.

Selain itu, modularity memiliki resolution limit, yang dapat menyebabkan struktur komunitas tertentu, terutama komunitas kecil, tidak terdeteksi secara terpisah.

CPM merupakan salah satu alternatif yang dirancang untuk menghindari resolution-limit problem tersebut.

Karena itu, evaluasi Leiden sebaiknya tidak berhenti pada satu angka.

Kelebihan Leiden Algorithm

1. Menjamin Connectivity Komunitas

Ini adalah salah satu alasan utama Leiden dikembangkan.

Pada formulasi Leiden, setiap iterasi memberikan jaminan bahwa komunitas terhubung, sementara iterasi lanjutan memberikan jaminan yang lebih kuat terhadap struktur internal komunitas.

2. Efisien

Leiden menggunakan fast local move procedure sehingga tidak perlu terus-menerus memeriksa node yang tidak mengalami perubahan lingkungan.

Penelitian asli menemukan Leiden lebih cepat dibandingkan Louvain pada jaringan yang diuji.

3. Kualitas Partition yang Tinggi

Dalam benchmark penelitian asli, Leiden menghasilkan partition dengan kualitas lebih tinggi dibandingkan Louvain pada jaringan yang diuji.

4. Mendukung Berbagai Objective

Implementasi Leiden mendukung objective seperti:

• Modularity

• CPM

• RBConfiguration

• Significance

• Surprise

dan objective lainnya tergantung library yang digunakan.

5. Cocok untuk Graph Besar

Leiden dirancang untuk community detection pada jaringan besar sehingga dapat digunakan pada berbagai skenario network science.

6. Fleksibel

Leiden dapat digunakan pada graph:

• unweighted,

• weighted,

• dengan node weights,

• serta skenario multiplex dan temporal melalui implementasi tertentu.

Kekurangan Leiden Algorithm

Leiden bukan algoritma yang otomatis menyelesaikan semua masalah.

1. Tidak Memberikan Label Bisnis

Leiden mungkin menghasilkan:

Community 0
Community 1
Community 2

Tetapi Leiden tidak otomatis mengetahui bahwa:

Community 0
= pelanggan premium

atau:

Community 1
= kategori elektronik rumah tangga

Interpretasi tersebut harus dilakukan setelah community detection.

2. Hasil Dipengaruhi Parameter

Hasil dapat dipengaruhi oleh:

• objective function,

• resolution,

• edge weight,

• node weight,

• seed,

• jumlah iterasi,

• dan struktur graph.

3. Tidak Selalu Menghasilkan Satu Partition Unik

Sebuah network dapat memiliki beberapa struktur komunitas yang sama-sama masuk akal.

Karena Leiden bersifat stokastik, beberapa run juga dapat menghasilkan variasi partition.

4. Tidak Sama dengan Clustering Berbasis Fitur

Leiden bukan pengganti langsung K-Means, DBSCAN, atau algoritma clustering lainnya.

Leiden bekerja pada graph.

5. Tetap Membutuhkan Validasi

Hasil community detection perlu diperiksa menggunakan:

• objective value,

• connectivity,

• stability,

• sensitivity analysis,

• dan pengetahuan domain.

Leiden vs K-Means

Perbedaan Leiden dan K-Means sangat penting.

K-Means biasanya bekerja pada data dengan feature vector:

Customer A
├── umur
├── pendapatan
├── frekuensi pembelian
└── total transaksi

K-Means mencari kelompok berdasarkan jarak atau kemiripan dalam feature space.

Leiden bekerja pada graph:

Customer A ─ Customer B
Customer B ─ Customer C
Customer C ─ Customer D

Jadi secara sederhana:

K-Means
→ "Data mana yang memiliki fitur yang mirip?"

Leiden
→ "Node mana yang membentuk komunitas berdasarkan hubungan dalam graph?"

Keduanya dapat digunakan dalam project yang sama.

Misalnya:

Customer features
        ↓
K-Means
        ↓
Segmentasi berdasarkan karakteristik

Customer interaction graph
        ↓
Leiden
        ↓
Komunitas berdasarkan hubungan

Hasil keduanya bahkan dapat dibandingkan untuk mendapatkan perspektif berbeda terhadap dataset.

Leiden vs DBSCAN

DBSCAN juga berbeda dari Leiden.

DBSCAN mencari kelompok berdasarkan kepadatan titik dalam feature space.

Leiden mencari komunitas berdasarkan struktur graph.

DBSCAN
Data points
      ↓
Density

Leiden
Graph
      ↓
Connectivity / Community structure

Karena itu, memilih antara DBSCAN dan Leiden bukan hanya persoalan algoritma mana yang lebih modern.

Pertanyaannya adalah:

Apakah masalah kita sebenarnya berbentuk feature space atau network?

Leiden vs Louvain

Jika menemukan tutorial lama yang menggunakan Louvain, bukan berarti tutorial tersebut otomatis salah.

Louvain tetap merupakan algoritma penting dalam sejarah community detection.

Namun Leiden dikembangkan secara khusus untuk mengatasi masalah struktural pada Louvain, terutama komunitas yang dapat menjadi badly connected atau disconnected.

Secara konseptual:

Louvain

Local Moving
     ↓
Aggregation
     ↓
Repeat

Sedangkan:

Leiden

Local Moving
     ↓
Refinement
     ↓
Aggregation
     ↓
Repeat

Tambahan refinement tersebut merupakan perbedaan fundamental.

Contoh Penggunaan dalam Dunia Nyata

Bayangkan sebuah marketplace memiliki 10 juta pengguna.

Setiap pengguna berinteraksi dengan produk melalui:

• pembelian,

• klik,

• wishlist,

• review,

• view,

• atau interaksi lainnya.

Kita dapat membangun graph seperti:

User → Product

atau mengubahnya menjadi user-user graph berdasarkan kesamaan perilaku:

User A ─ User B
User B ─ User C
User C ─ User D

Leiden kemudian dapat digunakan untuk menemukan komunitas.

Misalnya hasilnya:

Community 1
Laptop
Monitor
Keyboard
Mouse

Community 2
Kulkas
Mesin Cuci
Rice Cooker

Community 3
TV
Soundbar
Speaker

Hasil tersebut kemudian dapat dimanfaatkan untuk:

• rekomendasi,

• segmentasi,

• personalisasi,

• merchandising,

• analisis perilaku,

• strategi marketing.

Namun Leiden sendiri hanya menemukan struktur komunitas.

Pemanfaatan bisnis dilakukan pada tahap berikutnya.

Contoh dalam Analisis Media Sosial

Misalnya kita memiliki jaringan 1 juta akun.

Edge menunjukkan interaksi antar-akun.

Setelah community detection:

Community 1 → 15.000 akun
Community 2 → 8.000 akun
Community 3 → 27.000 akun
...

Kita kemudian dapat menganalisis:

• ukuran komunitas,

• node paling terhubung,

• centrality,

• density,

• topik dominan,

• hubungan antar-komunitas,

• perubahan komunitas dari waktu ke waktu.

Dengan demikian, Leiden dapat menjadi langkah awal untuk memahami struktur jaringan, bukan keseluruhan analisis.

Leiden dalam Analisis SEO dan Topical Authority

Leiden juga menarik jika diterapkan pada jaringan konten.

Misalnya sebuah website memiliki:

URL
Keyword
Entity
Internal Link
Topic

Kita dapat membangun graph berdasarkan hubungan antarhalaman.

Contohnya:

SEO
├── Technical SEO
├── On-Page SEO
├── Off-Page SEO
├── Local SEO
└── Enterprise SEO

Setiap halaman dapat menjadi node.

Edge dapat merepresentasikan:

• internal link,

• semantic similarity,

• shared entity,

• shared keyword,

• topic similarity,

• atau hubungan lain yang kita definisikan.

Leiden kemudian dapat digunakan untuk menemukan community/topical cluster yang muncul dari struktur graph tersebut.

Namun ada satu hal yang sangat penting:

Leiden tidak menentukan topical authority Google.

Leiden hanya menemukan komunitas berdasarkan graph yang kita bangun.

Jika graph dibangun berdasarkan internal link, maka yang ditemukan terutama mencerminkan struktur internal-link graph.

Jika graph dibangun berdasarkan semantic similarity, hasilnya akan mencerminkan semantic graph.

Dengan kata lain:

Makna hasil Leiden ditentukan oleh cara kita membangun graph.

Prinsip Penting: Garbage In, Garbage Out

Prinsip ini sangat penting dalam implementasi Leiden.

Misalnya graph dibangun dengan edge yang tidak relevan:

A ─ B
A ─ X
A ─ Z

Leiden tetap akan melakukan optimisasi berdasarkan hubungan tersebut.

Algoritma tidak tahu bahwa edge tersebut sebenarnya tidak bermakna.

Karena itu:

Algoritma yang bagus tidak dapat memperbaiki graph yang dibangun secara salah.

Dalam project nyata, kualitas hasil sangat dipengaruhi oleh:

• definisi node,

• definisi edge,

• edge weight,

• preprocessing,

• filtering,

• objective function,

• resolution,

• dan kualitas data.

Sering kali, merancang graph justru merupakan pekerjaan yang lebih penting daripada mengganti satu algoritma community detection dengan algoritma lainnya.

Bagaimana Workflow Leiden yang Baik?

Workflow yang masuk akal adalah:

Data mentah
    ↓
Definisikan node
    ↓
Definisikan edge
    ↓
Tentukan edge weight
    ↓
Bersihkan graph
    ↓
Pilih objective function
    ↓
Pilih resolution
    ↓
Jalankan Leiden
    ↓
Evaluasi hasil
    ↓
Uji stabilitas
    ↓
Interpretasi komunitas
    ↓
Validasi dengan domain
    ↓
Gunakan hasil untuk analisis atau keputusan

Jangan berhenti pada:

"Saya sudah menjalankan Leiden dan mendapatkan 12 cluster."

Pertanyaan yang lebih penting adalah:

"Apakah 12 komunitas tersebut stabil, masuk akal, dan berguna untuk tujuan analisis?"

Bagaimana Mengevaluasi Hasil Leiden?

Ada beberapa hal yang dapat diperiksa.

1. Objective Function

Jika menggunakan modularity, periksa modularity.

Jika menggunakan CPM, evaluasi berdasarkan objective CPM.

Jangan membandingkan angka dari objective yang berbeda seolah-olah berada pada skala yang sama.

2. Connectivity

Periksa apakah komunitas memiliki struktur yang terhubung dan masuk akal.

Leiden memberikan jaminan connectivity dalam formulasi algoritmanya, tetapi validasi tetap berguna terutama ketika graph diproses atau ditransformasi lebih lanjut.

3. Stability

Jalankan beberapa random seed.

Misalnya:

Seed 1
→ Partition A

Seed 2
→ Partition A

Seed 3
→ Partition B

Seed 4
→ Partition A

Kemudian ukur seberapa konsisten struktur tersebut.

4. Sensitivity terhadap Resolution

Coba beberapa nilai resolution:

0.1 → 5 communities
0.2 → 7 communities
0.3 → 10 communities
0.5 → 18 communities

Kemudian periksa apakah struktur komunitas tertentu tetap muncul pada berbagai pengaturan.

5. Validasi Domain

Ini sering kali merupakan tahap paling penting.

Misalnya kita menganalisis customer network dan mendapatkan:

Community A
70% pelanggan premium

Temuan tersebut kemudian dapat dibandingkan dengan:

• nilai transaksi,

• kategori produk,

• lokasi,

• frekuensi pembelian,

• customer lifetime value,

• atau data bisnis lainnya.

Dengan begitu, community detection tidak berhenti sebagai output algoritma, tetapi menjadi insight yang dapat diuji.

Apakah Leiden Selalu Lebih Baik daripada Louvain?

Tidak tepat mengatakan:

"Leiden selalu lebih baik."

Pernyataan yang lebih akurat adalah:

Leiden dirancang untuk mengatasi kelemahan penting Louvain dan dalam penelitian asli menunjukkan performa yang lebih baik pada benchmark serta jaringan yang mereka evaluasi.

Penelitian tersebut menunjukkan bahwa Leiden lebih cepat dan menghasilkan partition dengan kualitas lebih tinggi pada eksperimen yang dilakukan, sekaligus memberikan jaminan connectivity yang tidak dimiliki Louvain secara umum.

Namun performa pada project nyata tetap bergantung pada:

• dataset,

• graph construction,

• objective function,

• resolution,

• edge weight,

• random seed,

• jumlah iterasi,

• dan tujuan analisis.

Jadi jika ingin membandingkan Leiden dan Louvain pada project tertentu, pendekatan yang tepat adalah benchmark pada graph yang sama, bukan hanya mengikuti klaim umum.

Apakah Leiden Sulit Dipelajari?

Untuk pengguna biasa, tidak terlalu sulit.

Pemahamannya dapat dibagi menjadi tiga level.

Level 1: Pengguna

Cukup memahami:

• graph,

• node,

• edge,

• community,

• resolution,

• membership.

Level 2: Data Analyst

Mulai memahami:

• modularity,

• CPM,

• edge weight,

• objective function,

• stability,

• random seed,

• evaluasi hasil.

Level 3: Data Scientist atau Researcher

Perlu memahami:

• graph theory,

• optimization,

• quality function,

• local moving,

• refinement,

• aggregation,

• resolution limit,

• stochasticity,

• convergence,

• serta jaminan matematis Leiden.

Untuk sebagian besar kebutuhan bisnis, Level 1 dan Level 2 sudah cukup untuk menggunakan Leiden secara bertanggung jawab.

Kesalahan Umum Saat Menggunakan Leiden

Ada beberapa kesalahan yang sering terjadi.

Menganggap Jumlah Community sebagai Ground Truth

Jika Leiden menghasilkan 10 komunitas, bukan berarti dunia nyata pasti memiliki 10 kelompok.

Menganggap Modularity sebagai Kebenaran Absolut

Modularity hanya mengukur kualitas berdasarkan objective tertentu.

Mengabaikan Cara Graph Dibangun

Graph yang buruk dapat menghasilkan insight yang buruk meskipun algoritmanya benar.

Menggunakan Resolution untuk Memaksa Jumlah Cluster

Resolution bukan sekadar parameter untuk memaksa output menjadi jumlah komunitas tertentu.

Menjalankan Algoritma Sekali

Karena Leiden memiliki unsur stochasticity, satu run tidak selalu cukup untuk menilai stabilitas struktur komunitas.

Tidak Melakukan Validasi Domain

Community yang terlihat bagus secara matematis belum tentu berguna secara bisnis.

Jadi, Kapan Leiden Cocok Digunakan?

Leiden sangat cocok ketika masalah yang kita hadapi memang berbentuk network.

Contohnya:

Social Network
        ↓
User communities

Citation Network
        ↓
Research communities

Product Network
        ↓
Product communities

Customer Interaction Network
        ↓
Customer communities

Website Link Graph
        ↓
Content communities

Biological Network
        ↓
Biological communities

Jika data kita hanya berupa tabel dengan fitur numerik tanpa hubungan antar-entitas yang jelas, Leiden mungkin bukan pilihan pertama.

Namun jika hubungan antar-entitas merupakan bagian penting dari masalah, community detection dapat menjadi pendekatan yang sangat relevan.

Ringkasnya, Leiden Algorithm Itu Apa?

Cara paling sederhana untuk mengingat Leiden Algorithm adalah:

Leiden Algorithm adalah algoritma community detection yang digunakan untuk menemukan kelompok alami dalam sebuah jaringan berdasarkan struktur hubungan antar-node.

Leiden bekerja melalui tiga fase utama:

Local Moving
      ↓
Refinement
      ↓
Aggregation

Local moving mencari perpindahan node yang meningkatkan quality function.

Refinement memperbaiki struktur internal komunitas dan memberikan ruang untuk memecah komunitas menjadi subkomunitas yang lebih baik.

Aggregation membuat graph yang lebih sederhana berdasarkan hasil refinement sehingga proses optimisasi dapat dilanjutkan pada level berikutnya.

Salah satu kontribusi terpenting Leiden dibandingkan Louvain adalah adanya jaminan mengenai connectivity komunitas, sementara fast local move procedure membantu membuat algoritma efisien pada graph besar. Penelitian asli juga menunjukkan hasil benchmark yang menguntungkan Leiden dalam hal kualitas partition dan waktu komputasi pada jaringan yang diuji.

Dalam praktiknya, Leiden dapat digunakan untuk berbagai jenis network:

• social network,

• citation network,

• collaboration network,

• customer network,

• product network,

• biological network,

• website graph,

• temporal network,

• dan berbagai graph kompleks lainnya.

Tetapi ada satu prinsip yang jauh lebih penting daripada sekadar memilih Leiden:

Leiden hanya sebaik graph yang kita berikan kepadanya.

Jika node didefinisikan dengan benar, edge memiliki makna yang jelas, weight merepresentasikan kekuatan hubungan secara tepat, objective function dipilih dengan alasan yang jelas, resolution diuji secara wajar, dan hasil divalidasi dengan domain knowledge, maka community detection dapat menjadi alat analisis yang sangat kuat.

Dengan cara pandang tersebut, Leiden tidak perlu dianggap sebagai algoritma yang penuh rumus dan sulit dipahami.

Pada dasarnya, Leiden adalah cara sistematis untuk menemukan struktur tersembunyi di dalam jaringan yang terlalu kompleks untuk dianalisis secara manual.