Rantai Markov & Graf
Bab 17 membahas pemodelan sistem dinamik waktu kontinu menggunakan persamaan diferensial dan eksponensial matriks. Bab ini mengalihkan fokus analisis menuju sistem dinamik waktu diskrit yang memuat unsur ketidakpastian probabilistik: Rantai Markov. Kita akan mempelajari bagaimana sebuah sistem berpindah dari satu kondisi ke kondisi lainnya memanfaatkan operator matriks stokastik, mengunci eksistensi distribusi stasioner jangka panjang melalui analisis nilai eigen dominan, serta memetakan struktur interaktif tersebut ke dalam representasi jaringan kuantitatif melalui Teori Graf Spektral dan matriks Laplacian.
18.1 Definisi Formal Rantai Markov Stokastik
Dalam pemodelan real-world, banyak fenomena perubahan keadaan tidak berjalan secara deterministik murni. Sebagai contoh, fluktuasi pergerakan konsumen antar-merek dagang, penyebaran populasi penduduk antar-kota besar, atau urutan antrean server internet memuat unsur probabilitas. Proses stokastik waktu diskrit ini dapat dianalisis secara presisi jika memenuhi sebuah asumsi ketiadaan memori yang disebut sebagai sifat Markov.
Sebuah proses stokastik waktu diskrit dinyatakan bertindak sebagai sebuah Rantai Markov jika probabilitas bersyarat dari sistem untuk berpindah menuju kondisi masa depan pada langkah ke-$(k+1)$ hanya dan pasti bergantung secara eksklusif pada kondisi aktif saat ini pada langkah ke-$k$. Riwayat rekam jejak kondisi masa lalu pada langkah-langkah sebelumnya ($k{-}1, k{-}2, \ldots, 0$) sama sekali tidak memuat kontribusi informasi apa pun terhadap peluang masa depan:
Jika sebuah sistem memuat sebanyak total $n$ buah kemungkinan pilihan kondisi yang saling lepas, maka himpunan kondisi tersebut didefinisikan secara formal sebagai ruang keadaan (state space). Pergerakan probabilitas dari satu kondisi ke kondisi lainnya di dalam ruang keadaan ini direpresentasikan secara aljabar menggunakan barisan elemen vektor matematika.
Sebuah pemodelan meteorologi menyederhanakan kondisi cuaca harian ke dalam dua buah variasi kondisi saja: Hari Cerah (Kondisi 1) dan Hari Hujan (Kondisi 2). Pengamatan statistik menunjukkan histori perilaku probabilitas sebagai berikut:
- Jika hari ini cerah, peluang besok tetap cerah adalah sebesar $0{,}70$, sedangkan peluang besok berubah menjadi hujan adalah sebesar $0{,}30$.
- Jika hari ini hujan, peluang besok berubah menjadi cerah adalah sebesar $0{,}40$, sedangkan peluang besok tetap hujan adalah sebesar $0{,}60$.
Formulasikan ruang keadaan dari fenomena stokastik tersebut, dan jabarkan analisis Anda mengenai pemenuhan kriteria sifat Rantai Markov jika dikaitkan dengan prediksi cuaca jangka panjang.
Penyelesaian Analitis:
Berdasarkan data deskriptif di atas, ruang keadaan dari sistem waktu diskrit ini memuat dua elemen kondisi diskrit:
Analisis Karakteristik Markov: Model ini sah diasumsikan sebagai Rantai Markov karena peluang terjadinya hujan pada hari esok dihitung murni hanya berdasarkan kondisi cuaca pada hari aktif ini saja. Informasi mengenai apakah cuaca pada dua hari yang lalu atau satu minggu yang lalu bertindak sebagai hari badai atau hari kering sama sekali diabaikan dari perhitungan rasio peluang, memenuhi kriteria ketiadaan memori dari Definisi 18.1. $\checkmark$
18.2 Matriks Transisi Probabilitas & Vektor Distribusi
Untuk melacak dan mengomputasikan pergerakan probabilitas Rantai Markov secara efisien menggunakan komputer, kita mengorganisasikan seluruh data peluang bersyarat ke dalam format operator linear. Kita menyusun nilai probabilitas tersebut menjadi sebuah matriks khusus yang disebut sebagai matriks transisi.
Misalkan sebuah Rantai Markov memuat sebanyak total $n$ buah pilihan ruang keadaan. Matriks Transisi Probabilitas, dinotasikan secara universal dengan simbol $P$ berukuran $n \times n$, dikonstruksi secara sistematis dengan meletakkan peluang perpindahan kondisi dari keadaan $j$ menuju keadaan $i$ pada koordinat entri baris ke-$i$ kolom ke-$j$:
Sebuah matriks persegi diklasifikasikan secara formal sebagai matriks stokastik kolom (column-stochastic matrix) jika setiap entri di dalamnya bernilai non-negatif ($p_{ij} \geq 0$) dan jumlah total dari seluruh entri sepanjang **setiap satu kolom tunggal bernilai tepat satu murni** secara mutlak:
Kondisi awal serta probabilitas posisi sistem pada langkah ke-$k$ direpresentasikan melalui vektor distribusi keadaan (state distribution vector), dinotasikan sebagai $\mathbf{x}_k = \begin{bmatrix} x_1 & x_2 & \cdots & x_n \end{bmatrix}^T$. Komponen entri dari vektor ini menampung nilai peluang aktif posisi sistem, di mana jumlah total seluruh elemen vektor wajib memenuhi kriteria ternormalisasi bernilai tepat satu murni ($\sum x_i = 1$).
Berdasarkan sifat penentuan matriks stokastik, pelacakan kondisi probabilitas masa depan dari satu langkah ke langkah berikutnya dihitung secara mekanis memanfaatkan aksi perkalian matriks-vektor dari arah kiri:
Dengan menerapkan prinsip induksi aljabar berantai sekuensial untuk sebarang bilangan langkah ke-$k$ dari titik awal waktu nol murni, diperoleh hubungan formulasi eksponen matriks waktu diskrit:
Susunlah matriks transisi probabilitas stokastik kolom $P$ berdasarkan data deskriptif perubahan cuaca pada Contoh 18.1. Jika diketahui probabilitas cuaca pada hari ini (langkah awal, $k=0$) dipastikan bertindak sebagai hari hujan secara mutlak, hitunglah vektor distribusi peluang cuaca untuk dua hari ke depan ($\mathbf{x}_2$).
Penyelesaian Analitis:
Langkah 1: Mengonstruksi Susunan Matriks Transisi $P$
Petakan ruang keadaan sesuai urutan indeks $1 = \text{Cerah}$ dan $2 = \text{Hujan}$. Masukkan nilai peluang bersyarat ke dalam entri kolom secara vertikal:
- Kolom 1 (Kondisi Awal Cerah): Peluang tetap cerah $a_{11} = 0{,}70$; peluang menjadi hujan $a_{21} = 0{,}30$. Periksa jumlah kolom: $0{,}70 + 0{,}30 = 1$ $\checkmark$
- Kolom 2 (Kondisi Awal Hujan): Peluang menjadi cerah $a_{12} = 0{,}40$; peluang tetap hujan $a_{22} = 0{,}60$. Periksa jumlah kolom: $0{,}40 + 0{,}60 = 1$ $\checkmark$
Langkah 2: Menentukan Vektor Kondisi Batas Awal $\mathbf{x}_0$
Karena hari ini dikondisikan dipastikan bertindak sebagai hari hujan secara mutlak, maka peluang cerah bernilai nol dan peluang hujan bernilai satu murni:
Langkah 3: Menghitung Distribusi Peluang Langkah Pertama ($\mathbf{x}_1$)
Langkah 4: Menghitung Distribusi Peluang Langkah Kedua ($\mathbf{x}_2$)
Kesimpulan: Vektor distribusi peluang cuaca untuk dua hari ke depan dikunci sebesar $\mathbf{x}_2 = \begin{bmatrix} 0{,}52 & 0{,}48 \end{bmatrix}^T$, mengonfirmasi bahwa peluang hari berubah menjadi cerah adalah sebesar $52\%$ dan peluang hari tetap hujan mengevaluasi sebesar $48\%$. $\checkmark$
Tiga perusahaan teknologi — Merek A, Merek B, dan Merek C — bersaing memperebutkan pangsa pasar konsumen. Survei bulanan menunjukkan pola perpindahan loyalitas pelanggan sebagai berikut:
- Dari pelanggan Merek A: $60\%$ tetap di A, $20\%$ pindah ke B, $20\%$ pindah ke C.
- Dari pelanggan Merek B: $20\%$ pindah ke A, $50\%$ tetap di B, $30\%$ pindah ke C.
- Dari pelanggan Merek C: $10\%$ pindah ke A, $30\%$ pindah ke B, $60\%$ tetap di C.
Jika pada bulan awal distribusi pelanggan adalah $\mathbf{x}_0 = \begin{bmatrix} 0{,}50 & 0{,}30 & 0{,}20 \end{bmatrix}^T$, hitunglah distribusi pangsa pasar setelah satu bulan ($\mathbf{x}_1$) dan setelah dua bulan ($\mathbf{x}_2$).
Penyelesaian Analitis:
Langkah 1: Mengonstruksi Matriks Transisi $3 \times 3$
Susun entri peluang bersyarat ke dalam kolom sesuai urutan $\text{A} \to \text{B} \to \text{C}$:
Verifikasi stokastik kolom: kolom 1 $= 0{,}60 + 0{,}20 + 0{,}20 = 1{,}00$ $\checkmark$; kolom 2 $= 0{,}20 + 0{,}50 + 0{,}30 = 1{,}00$ $\checkmark$; kolom 3 $= 0{,}10 + 0{,}30 + 0{,}60 = 1{,}00$ $\checkmark$.
Langkah 2: Menghitung $\mathbf{x}_1 = P \,\mathbf{x}_0$
Verifikasi: $0{,}38 + 0{,}31 + 0{,}31 = 1{,}00$ $\checkmark$. Setelah satu bulan, pangsa Merek A menurun dari $50\%$ menjadi $38\%$.
Langkah 3: Menghitung $\mathbf{x}_2 = P \,\mathbf{x}_1$
Verifikasi: $0{,}321 + 0{,}324 + 0{,}355 = 1{,}000$ $\checkmark$.
Kesimpulan: Setelah dua bulan, distribusi pangsa pasar bergerak menuju $\mathbf{x}_2 = \begin{bmatrix} 0{,}321 & 0{,}324 & 0{,}355 \end{bmatrix}^T$. Terlihat tren konvergensi: pangsa Merek A terus menurun ($50\% \to 38\% \to 32{,}1\%$), sementara Merek C terus meningkat ($20\% \to 31\% \to 35{,}5\%$). Perilaku ini mengindikasikan keberadaan titik kesetimbangan stasioner yang akan dibahas pada Bagian 18.3. $\checkmark$
18.3 Eksistensi dan Karakteristik Distribusi Stasioner
Jika kita meneruskan proses perkalian berulang $\mathbf{x}_{k+1} = P \,\mathbf{x}_k$ untuk nilai langkah yang sangat besar ($k \to \infty$), kita akan menyadari sebuah fenomena aljabar yang luar biasa: komponen-komponen entri di dalam vektor distribusi akan mulai mandek konvergen menuju suatu nilai kesetimbangan konstan murni. Kondisi setimbang di mana sistem tidak lagi mengalami pergeseran probabilitas disebut sebagai distribusi stasioner.
Misalkan $P$ adalah sebuah matriks transisi probabilitas stokastik kolom berukuran $n \times n$. Sebuah vektor probabilitas $\mathbf{q} \in \mathbb{R}^n$ dinyatakan bertindak sebagai vektor distribusi stasioner (atau steady-state vector) dari Rantai Markov terkait jika ia memenuhi hubungan identitas invarian:
Di mana komponen elemen vektor $\mathbf{q}$ wajib memenuhi kriteria positif definit non-negatif ($q_i \geq 0$) bersama dengan batasan normalisasi kapasitas penuh: $\sum_{i=1}^{n} q_i = 1$.
Mari kita bedah struktur dari persamaan fundamental $P\mathbf{q} = \mathbf{q}$. Jika kita menata ulang persamaan tersebut dengan menyisipkan matriks identitas, kita mendapatkan format sistem homogen: $(P - I_n)\,\mathbf{q} = \mathbf{0}$.
Hubungan aljabar ini membuktikan secara eksplisit bahwa vektor distribusi stasioner $\mathbf{q}$ sejatinya tidak lain berwujud sebagai **vektor eigen** dari matriks transisi $P$ yang berpasangan secara eksklusif dengan nilai eigen **$\lambda = 1$**. Mencari kondisi stasioner jangka panjang diselesaikan secara mekanis cukup dengan mengisolasi basis ruang kosong (nullspace) dari matriks koefisien khusus $(P - I_n)$.
Hitunglah entri komponen vektor distribusi stasioner jangka panjang $\mathbf{q}$ dari matriks transisi cuaca reguler $P = \begin{bmatrix} 0{,}70 & 0{,}40 \\ 0{,}30 & 0{,}60 \end{bmatrix}$ memanfaatkan kriteria sistem homogen ruang kosong.
Penyelesaian Analitis:
Langkah 1: Menyusun Struktur Sistem Homogen $(P - I_2)\,\mathbf{q} = \mathbf{0}$
Kurangkan angka satu murni dari entri diagonal utama matriks $P$:
Langkah 2: Eksekusi Operasi Baris Elementer untuk Mengisolasi Basis
Sandingkan matriks koefisien konstan dengan ruas kanan nol murni:
Baris kedua runtuh melebur menjadi nol murni, membuktikan eksistensi nilai eigen $\lambda = 1$ terbukti valid $\checkmark$. Baris pertama memuat hubungan aljabar: $-0{,}30\,q_1 + 0{,}40\,q_2 = 0 \implies 0{,}30\,q_1 = 0{,}40\,q_2 \implies q_1 = \tfrac{4}{3}\,q_2$.
Langkah 3: Intervensi Batasan Normalisasi Probabilitas Kapasitas Penuh
Substitusikan hubungan variabel di atas ke dalam kriteria syarat mutlak penjumlahan probabilitas murni ($q_1 + q_2 = 1$):
Hitung nilai komponen pertama memanfaatkan hubungan rasio transisi: $q_1 = \tfrac{4}{3}\!\left(\tfrac{3}{7}\right) = \boxed{\tfrac{4}{7}}$.
Kesimpulan: Vektor distribusi stasioner dari Rantai Markov ini adalah $\mathbf{q} = \begin{bmatrix} 4/7 & 3/7 \end{bmatrix}^T \approx \begin{bmatrix} 0{,}571 & 0{,}429 \end{bmatrix}^T$. Hal ini mengonfirmasi bahwa dalam jangka panjang, peluang hari bertindak sebagai hari cerah akan stabil konvergen di kisaran $57{,}1\%$ dan peluang hari hujan menetap sebesar $42{,}9\%$, sepenuhnya independen dari status cuaca awal hari ini. $\checkmark$
Hitunglah vektor distribusi stasioner $\mathbf{q}$ dari matriks transisi tiga merek pada Contoh 18.3:
Penyelesaian Analitis:
Langkah 1: Bentuk sistem homogen $(P - I_3)\,\mathbf{q} = \mathbf{0}$
Langkah 2: Eliminasi Gauss-Jordan
Langkah 3: Baca hubungan parametrik
Dari baris tereduksi diperoleh:
- $2q_1 - 1{,}375\,q_3 = 0 \implies q_1 = 0{,}6875\,q_3 = \tfrac{11}{16}\,q_3$
- $q_2 - 0{,}875\,q_3 = 0 \implies q_2 = 0{,}875\,q_3 = \tfrac{7}{8}\,q_3$
Langkah 4: Normalisasi $q_1 + q_2 + q_3 = 1$
Kesimpulan: Vektor distribusi stasioner adalah $\mathbf{q} = \begin{bmatrix} 11/41 & 14/41 & 16/41 \end{bmatrix}^T \approx \begin{bmatrix} 0{,}268 & 0{,}341 & 0{,}390 \end{bmatrix}^T$. Dalam jangka panjang, Merek C akan mendominasi pangsa pasar sebesar $\approx 39{,}0\%$, diikuti Merek B $\approx 34{,}1\%$, dan Merek A $\approx 26{,}8\%$. Bandingkan dengan $\mathbf{x}_2 = \begin{bmatrix} 0{,}321 & 0{,}324 & 0{,}355 \end{bmatrix}^T$ pada Contoh 18.3 — tren konvergensi menuju $\mathbf{q}$ sudah terlihat jelas hanya dalam dua langkah. $\checkmark$
18.4 Konvergensi Rantai via Teorema Nilai Eigen Dominan
Apakah sebarang matriks transisi probabilitas di dunia ini selalu dijamin memiliki satu vektor stasioner unik yang mampu dicapai dari sebarang variasi vektor kondisi awal $\mathbf{x}_0$ apa pun? Jaminan teoretis ini dikunci secara mutlak oleh **Teorema Perron-Frobenius** melalui klasifikasi Rantai Markov reguler.
Sebuah matriks transisi probabilitas stokastik $P$ diklasifikasikan bersifat reguler jika terdapat suatu bilangan bulat positif eksponen $k \geq 1$ sedemikian rupa sehingga seluruh entri komponen internal di dalam matriks pangkat $P^k$ memuat nilai positif murni ($p_{ij} > 0$) secara total, tanpa memuat satu pun entri bernilai nol murni.
Jika $P$ bertindak sebagai sebuah matriks transisi stokastik kolom yang bersifat reguler, maka properti spektral dan karakteristik batas berikut dijamin pasti terpenuhi:
- Angka $\lambda = 1$ bertindak sebagai nilai eigen dominan tunggal dari matriks $P$, memuat nilai multiplisitas aljabar tepat satu ($m_a(1) = 1$). Seluruh nilai eigen sisa lainnya dipastikan memuat magnitudo absolut yang lebih kecil: $|\lambda_i| < 1$.
- Eksis satu buah vektor distribusi stasioner unik $\mathbf{q}$ yang seluruh entrinya bernilai positif murni ($q_i > 0$).
- Untuk sebarang pilihan vektor distribusi kondisi awal $\mathbf{x}_0$ apa pun, barisan rantai iterasi waktu diskrit dijamin pasti konvergen menuju vektor stasioner unik tersebut secara mutlak:
\[ \lim_{k \to \infty} P^k \,\mathbf{x}_0 = \mathbf{q} \]
Buktikan bahwa matriks transisi cuaca $P = \begin{bmatrix} 0{,}70 & 0{,}40 \\ 0{,}30 & 0{,}60 \end{bmatrix}$ diklasifikasikan sebagai matriks stokastik reguler dengan menghitung $P^2$.
Penyelesaian Analitis:
Perhatikan bahwa matriks $P$ sendiri sudah memuat seluruh entri positif (tidak ada nol), sehingga secara trivial $P^1$ telah memenuhi syarat. Namun, untuk melatih mekanisme verifikasi, kita hitung $P^2$:
Verifikasi stokastik kolom: kolom 1 $= 0{,}61 + 0{,}39 = 1{,}00$ $\checkmark$; kolom 2 $= 0{,}52 + 0{,}48 = 1{,}00$ $\checkmark$.
Seluruh empat entri $P^2$ bernilai positif murni ($0{,}61, 0{,}52, 0{,}39, 0{,}48 > 0$), sehingga $P$ terbukti reguler. Oleh Teorema 18.1, rantai ini dijamin memiliki vektor stasioner unik yang dapat dicapai dari sebarang $\mathbf{x}_0$ — sesuai dengan hasil $\mathbf{q} = \begin{bmatrix} 4/7 & 3/7 \end{bmatrix}^T$ yang telah kita hitung pada Contoh 18.4. $\checkmark$
Catatan Penting: Entri $(P^2)_{12} = 0{,}52$ memiliki interpretasi probabilistik langsung: ini adalah peluang bahwa sistem berpindah dari kondisi Hujan menuju kondisi Cerah dalam tepat dua langkah waktu, melewati satu kondisi perantara apa pun. Secara umum, entri $(P^k)_{ij}$ menyatakan peluang transisi $k$-langkah dari keadaan $j$ menuju keadaan $i$.
Tinjau matriks transisi berikut yang memodelkan sistem dua keadaan di mana perpindahan hanya terjadi satu arah pada setiap langkah:
Periksa apakah $P$ bersifat reguler dan analisis implikasinya terhadap konvergensi.
Penyelesaian Analitis:
Entri $p_{12} = 0$ menunjukkan bahwa dari keadaan 2, peluang berpindah ke keadaan 1 secara langsung dalam satu langkah adalah nol. Mari kita periksa $P^2$:
Entri $(P^2)_{12} = 0$ masih bertahan nol. Secara induksi, dapat dibuktikan bahwa $(P^k)_{12} = 0$ untuk semua $k \geq 1$ (karena kolom kedua selalu memiliki pola $[0 \;\; 1]^T$ yang tidak berubah oleh perkalian). Oleh karena itu, tidak ada pangkat $P^k$ yang seluruh entrinya positif.
Kesimpulan: $P$ bukan matriks stokastik reguler. Meskipun demikian, untuk contoh spesifik ini rantai tetap konvergen menuju $\mathbf{q} = \begin{bmatrix} 0 & 1 \end{bmatrix}^T$ dari sebarang $\mathbf{x}_0$ manapun — dapat diverifikasi bahwa peluang berada di keadaan 1 meluruh secara eksponensial: $x_{k,1} = (0{,}50)^k \, x_{0,1} \to 0$. Yang dilanggar adalah syarat $q_i > 0$ dari Teorema 18.1 poin (2) — vektor stasioner memiliki entri nol murni ($q_1 = 0$), menandakan keadaan 1 bersifat transient (populasi akan meninggalkan keadaan 1 selamanya dalam batas tak hingga). Sebagai perbandingan, rantai periodik $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ merupakan contoh rantai tidak reguler yang benar-benar gagal konvergen karena distribusi berosilasi selamanya antara $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ dan $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. Contoh ini menegaskan bahwa syarat keteraturan pada Definisi 18.4 bersifat sufficient but not necessary untuk eksistensi vektor stasioner maupun konvergensi. $\checkmark$
18.5 Pemetaan Graf: Matriks Adjacency & Matriks Laplacian
Abstraksi aljabar linear tidak hanya mampu melacak pergerakan probabilitas waktu diskrit. Kita dapat memperluas instrumen matriks untuk memetakan hubungan keterhubungan konektivitas makro dari sekelompok objek interaktif. Bidang studi yang menjembatani struktur jaringan diskrit dengan operator linear persegi ini disebut sebagai Teori Graf Spektral (Spectral Graph Theory).
Sebuah jaringan atau objek graf secara formal dinotasikan sebagai $G = (V, E)$, di mana $V = \{v_1, v_2, \ldots, v_n\}$ bertindak sebagai himpunan **titik simpul (vertices / nodes)**, dan $E$ bertindak sebagai himpunan **garis sisi penghubung (edges / links)** yang mengikat interaksi antar-simpul tersebut. Struktur fisik graf ini dikonversi secara presisi menjadi dua buah operator matriks fundamental.
Misalkan $G$ adalah sebuah graf tidak berarah (undirected graph) yang memuat sebanyak total $n$ buah titik simpul. Matriks Adjacency, dinotasikan secara universal dengan simbol $A$ berukuran $n \times n$, didefinisikan secara formal melalui penentuan nilai entri biner berikut:
Karakteristik Aljabar: Karena graf bersifat tidak berarah, interaksi keterhubungan berlaku dua arah secara simetris ($a_{ij} = a_{ji}$). Oleh karena itu, matriks adjacency $A$ dijamin pasti bertindak sebagai matriks simetris riil, sehingga ia mewarisi seluruh sifat Teorema Spektral Bab 15.
Misalkan $G$ adalah sebuah graf dengan $n$ buah titik simpul. Matriks Derajat, dinotasikan sebagai $D$ berukuran $n \times n$, merupakan sebuah matriks diagonal murni yang entri diagonalnya menampung kuantitas jumlah total garis sisi penghubung yang melekat pada simpul terkait (disebut nilai derajat simetris, $d_i$):
Misalkan $G$ adalah sebuah graf tidak berarah tanpa bobot. Matriks Laplacian dari graf tersebut, dinotasikan secara baku dengan simbol $L$ berukuran $n \times n$, didefinisikan sebagai hasil operasi pengurangan antara matriks derajat dengan matriks keterhubungannya:
Sebuah struktur jaringan graf sederhana memuat tiga buah titik simpul ($V = \{v_1, v_2, v_3\}$) yang membentuk formasi geometri segitiga penuh, di mana simpul 1 terhubung ke simpul 2 dan 3, serta simpul 2 terhubung ke simpul 3. Konstruksikan entri matriks $A, D,$ dan $L$ yang bersesuaian.
Penyelesaian Analitis:
Langkah 1: Mengunci Nilai Matriks Adjacency $A$
Karena setiap simpul terhubung dengan semua simpul lainnya secara komplit, entri off-diagonal bernilai satu dan diagonal utama bernilai nol:
Langkah 2: Mengunci Nilai Matriks Derajat $D$
Hitung kuantitas jalinan hubungan pada masing-masing baris simpul: simpul 1 memuat derajat 2, simpul 2 memuat derajat 2, dan simpul 3 memuat derajat 2. Susun ke format diagonal:
Langkah 3: Formulasi Matriks Laplacian $L$
Kurangkan matriks derajat $D$ dengan matriks keterhubungan $A$ sesuai aturan rumus Definisi 18.7:
Kesimpulan: Matriks Laplacian pengikat jaringan segitiga berhasil terbentuk secara presisi $\checkmark$. Perhatikan karakteristik biner uniknya: entri diagonal utama menyimpan informasi kuantitas derajat, sementara entri off-diagonal menyimpan informasi biner negatif dari keterhubungan fisik jaringan. $\checkmark$
Empat stasiun kereta ($v_1, v_2, v_3, v_4$) terhubung secara linear membentuk jalur: $v_1$—$v_2$—$v_3$—$v_4$. Tidak ada jalur langsung antara $v_1$ dan $v_3$, maupun antara $v_2$ dan $v_4$. Konstruksikan matriks $A$, $D$, dan $L$.
Penyelesaian Analitis:
Himpunan garis sisi: $E = \{(v_1, v_2),\, (v_2, v_3),\, (v_3, v_4)\}$. Total 3 buah sisi penghubung.
Matriks Adjacency:
Matriks Derajat: $d_1 = 1$ (ujung), $d_2 = 2$ (tengah), $d_3 = 2$ (tengah), $d_4 = 1$ (ujung).
Matriks Laplacian:
Kesimpulan: Matriks Laplacian dari graf rantai linear memiliki pola tridiagonal yang khas — entri non-nol hanya muncul pada diagonal utama dan dua sub-diagonal segera di atas dan di bawahnya. Pola struktur ini secara langsung mencerminkan topologi keterhubungan lokal dari graf path. $\checkmark$
18.6 Teori Graf Spektral Terapan
Kekuatan sejati dari matriks Laplacian $L = D - A$ terletak pada analisis spektral nilai eigen penyusunnya. Karena $L$ merupakan hasil dari struktur simetris yang dominan diagonal, ia mewarisi properti luar biasa yang mengaitkan nilai eigen matriks secara langsung dengan karakteristik topologi fisik dari jaringan nyata.
18.6.1 Teorema-Teorema Aljabar Struktur Topologi Graf
Misalkan $L$ adalah matriks Laplacian dari sebuah graf tidak berarah $G$ berukuran $n \times n$. Maka properti matematika berikut dijamin pasti berlaku secara absolut:
- Nilai Eigen Nol Trivial: Angka $\lambda_1 = 0$ selalu bertindak sebagai nilai eigen pertama dari matriks $L$, berpasangan dengan vektor eigen konstan berupa vektor satuan $\mathbf{1} = \begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}^T$.
- Sifat Semi-Definit Positif: Seluruh nilai eigen sisa lainnya dipastikan bernilai non-negatif murni: $0 = \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n$.
- Nilai Konektivitas Aljabar (Nilai Fiedler): Nilai eigen terkecil kedua yang non-nol, dinotasikan sebagai $\lambda_2$, disebut sebagai konektivitas aljabar atau Fiedler value. Graf $G$ dinyatakan bersifat terhubung secara utuh (connected) jika dan hanya jika nilai $\lambda_2 > 0$. Jika $\lambda_2 = 0$, berarti graf tersebut terpecah menjadi beberapa subgraf yang terisolasi.
Gunakan matriks Laplacian graf segitiga dari Contoh 18.8:
(a) Buktikan secara eksplisit melalui perkalian matriks-vektor bahwa $L\,\mathbf{1} = \mathbf{0}$.
(b) Hitung seluruh nilai eigen $L$ dan identifikasi nilai Fiedler $\lambda_2$.
Penyelesaian Analitis:
Bagian (a): Verifikasi Langsung $L\,\mathbf{1} = \mathbf{0}$
Terbukti bahwa $\lambda_1 = 0$ dengan vektor eigen $\mathbf{1}$, sesuai Teorema 18.2 properti (1).
Bagian (b): Komputasi Polinomial Karakteristik
Gunakan trik substitusi: misalkan $\mu = 2 - \lambda$, maka matriks menjadi $\begin{bmatrix} \mu & -1 & -1 \\ -1 & \mu & -1 \\ -1 & -1 & \mu \end{bmatrix}$.
Faktorkan: $\mu^3 - 3\mu - 2 = (\mu + 1)^2(\mu - 2)$. Verifikasi: $(\mu+1)^2(\mu-2) = (\mu^2 + 2\mu + 1)(\mu - 2) = \mu^3 - 2\mu^2 + 2\mu^2 - 4\mu + \mu - 2 = \mu^3 - 3\mu - 2$ $\checkmark$
Akar-akar: $\mu = -1$ (multiplisitas 2) dan $\mu = 2$. Karena $\lambda = 2 - \mu$:
Hasil Spektral: $\sigma(L) = \{0, 3, 3\}$. Nilai Fiedler $\lambda_2 = 3 > 0$, mengonfirmasi bahwa graf segitiga adalah graf terhubung utuh sesuai Teorema 18.2 properti (3) $\checkmark$. Nilai Fiedler yang besar ($\lambda_2 = 3$) mengindikasikan konektivitas yang sangat kuat — konsisten dengan fakta bahwa graf segitiga ($K_3$) adalah graf lengkap yang setiap simpulnya terhubung langsung ke semua simpul lainnya.
Pertimbangkan graf rantai linear tiga simpul $v_1$—$v_2$—$v_3$ dengan matriks Laplacian:
(a) Hitung seluruh nilai eigen dan identifikasi $\lambda_2$.
(b) Hitung vektor eigen Fiedler (Fiedler vector) dan interpretasikan tanda entrinya untuk segmentasi graf.
Penyelesaian Analitis:
Bagian (a): Polinomial Karakteristik
Kembangkan sepanjang baris pertama:
Sehingga nilai eigen: $\boxed{\lambda_1 = 0,\quad \lambda_2 = 1,\quad \lambda_3 = 3}$.
Nilai Fiedler $\lambda_2 = 1 > 0$, mengonfirmasi graf rantai tiga simpul bersifat terhubung utuh $\checkmark$. Bandingkan dengan $\lambda_2 = 3$ untuk graf segitiga — nilai Fiedler yang lebih kecil mengindikasikan konektivitas yang lebih lemah, yang masuk akal karena graf rantai hanya memiliki satu jalur penghubung antara $v_1$ dan $v_3$ (melalui $v_2$ sebagai titik jembatan).
Bagian (b): Vektor Eigen Fiedler
Selesaikan $(L - I)\,\mathbf{v} = \mathbf{0}$ untuk $\lambda_2 = 1$:
Dari baris pertama: $-v_2 = 0 \implies v_2 = 0$.
Dari baris ketiga: $-v_2 = 0 \implies v_2 = 0$ (konsisten).
Dari baris kedua: $-v_1 + v_2 - v_3 = 0 \implies -v_1 - v_3 = 0 \implies v_1 = -v_3$.
Vektor eigen Fiedler (setelah normalisasi):
Interpretasi Segmentasi: Tanda entri vektor Fiedler membagi simpul ke dalam dua kelompok berdasarkan polaritas:
- $f_1 = +1 > 0$: simpul $v_1$ masuk Klaster A
- $f_2 = 0$: simpul $v_2$ berada tepat di batas (titik jembatan)
- $f_3 = -1 < 0$: simpul $v_3$ masuk Klaster B
Berdasarkan tanda, partisi spektral dua-arah yang wajar adalah $\{v_1\}$ vs $\{v_2, v_3\}$ (dengan ambang batas tanda $> 0$), yang memotong tepat satu garis sisi ($v_1$—$v_2$). Alternatifnya, partisi $\{v_1, v_2\}$ vs $\{v_3\}$ (ambang batas $\geq 0$) memotong sisi $v_2$—$v_3$. Kedua partisi ini merupakan minimum cut — jumlah minimum pemotongan sisi yang mungkin untuk membagi graf rantai tiga simpul menjadi dua komponen non-kosong. Inilah esensi metode Spectral Clustering — vektor Fiedler secara otomatis menemukan pemotongan optimal jaringan $\checkmark$.
18.6.2 Aplikasi Analisis Data: Metode Spectral Clustering
Dalam dunia machine learning dan analisis data masif, Teorema 18.2 melandasi sebuah algoritma partisi segmentasi yang sangat perkasa bernama Spectral Clustering. Ketika kita harus mengelompokkan ribuan data interaktif rumit yang tidak dapat dipisahkan secara linear, kita membangun matriks Laplacian jaringan dari data tersebut.
Dengan menghitung vektor eigen yang bersesuaian dengan nilai fiedler $\lambda_2$ (disebut sebagai Fiedler vector), tanda aljabar dari entri koordinat internal vektor tersebut ($+$ atau $-$) bertindak sebagai pisau pemotong cerdas yang membagi simpul-simpul jaringan ke dalam klaster kelompok yang paling optimal, meminimalkan jumlah garis sisi penghubung yang terpotong secara otomatis tanpa proses kalkulus yang berat.
Pertimbangkan graf empat simpul yang terpecah menjadi dua komponen terisolasi: $\{v_1, v_2\}$ terhubung satu sama lain, dan $\{v_3, v_4\}$ terhubung satu sama lain, tetapi tidak ada sisi antara kedua kelompok. Matriks Laplacian-nya berbentuk blok diagonal:
Karena matriks berbentuk blok diagonal, nilai eigen matriks adalah gabungan nilai eigen dari setiap blok. Setiap blok $\begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix}$ memiliki eigenvalue $\{0, 2\}$. Sehingga:
Nilai eigen nol memiliki multiplisitas 2, dengan dua vektor eigen linier independen: $\mathbf{v}_1 = \begin{bmatrix} 1 & 1 & 0 & 0 \end{bmatrix}^T$ (mendukung komponen 1) dan $\mathbf{v}_2 = \begin{bmatrix} 0 & 0 & 1 & 1 \end{bmatrix}^T$ (mendukung komponen 2). Karena $\lambda_2 = 0$, Teorema 18.2 langsung mendeteksi bahwa graf ini tidak terhubung. Jumlah nilai eigen nol ($\text{nullity}(L)$) selalu sama persis dengan jumlah komponen terhubung dalam graf.
Bab 18 memperluas fungsionalitas aljabar linear dari sistem fisik waktu kontinu menuju analisis sistem stokastik diskrit dan relasi jaringan abstrak. Kita melihat bagaimana dekonstruksi nilai eigen mampu menjawab tantangan ketidakpastian masa depan.
Melalui pembuktian Teorema Perron-Frobenius, eksistensi nilai eigen dominan tunggal $\lambda = 1$ memberikan kepastian hukum bahwa sistem stokastik reguler akan selalu meluncur tenang menuju satu titik kesetimbangan stasioner unik, sepenuhnya melupakan kondisi awal waktu nol. Contoh 18.7 menunjukkan batasan teorema ini: rantai tidak reguler mungkin tetap memiliki stasioner dan konvergen, namun jaminan universal Teorema 18.1 — termasuk sifat positif seluruh entri vektor stasioner — tidak lagi berlaku.
Peralihan menuju Teori Graf Spektral membuktikan bahwa matriks dapat bertindak sebagai cermin yang merekam topologi konektivitas makro sebuah jaringan. Komputasi eksplisit pada Contoh 18.10 dan 18.11 mendemonstrasikan bagaimana spektral Laplacian — dari nilai eigen nol trivial hingga vektor Fiedler — mengungkap struktur tersembunyi graf. Karakteristik nilai fiedler $\lambda_2$ pada matriks Laplacian menegaskan bahwa geometri abstrak ruang eigen mampu mendeteksi tingkat keretakan fisik sebuah graf. Dua pilar terapan ini — rantai probabilitas stokastik dan partisi klaster spektral — bertindak sebagai motor penggerak industri terpenting yang akan langsung kita perluas untuk mengolah reduksi dimensi data masif pada Bab 19 (Analisis Data: PCA & Regresi).
- Sebuah proses migrasi populasi penduduk antar-kota memuat nilai data peluang bersyarat waktu diskrit yang disusun ke dalam matriks transisi stokastik kolom berikut:
\[ P = \begin{bmatrix} 0{,}80 & 0{,}30 \\ 0{,}20 & 0{,}70 \end{bmatrix} \]Jika diketahui distribusi populasi awal pada tahun pertama (waktu awal, $k=0$) diwakili oleh vektor keadaan $\mathbf{x}_0 = \begin{bmatrix} 0{,}80 & 0{,}20 \end{bmatrix}^T$, hitunglah entri komponen vektor distribusi peluang populasi untuk dua langkah waktu diskrit berikutnya ($\mathbf{x}_2$).
- Tinjau kembali matriks transisi stokastik kolom $P$ dari soal nomor 1. Buktikan secara formal bahwa matriks tersebut diklasifikasikan sebagai matriks stokastik reguler, kemudian carilah komponen entri vektor distribusi stasioner jangka panjangnya ($\mathbf{q}$) memanfaatkan skenario penyelesaian sistem homogen ruang kosong $(P - I_2)\,\mathbf{q} = \mathbf{0}$.
- Sebuah struktur jaringan graf tidak berarah memuat empat buah titik simpul ($V = \{v_1, v_2, v_3, v_4\}$) dengan alur keterhubungan konektivitas fisik sebagai berikut: simpul 1 terhubung ke simpul 2 dan 3; simpul 2 terhubung ke simpul 4; serta simpul 3 terhubung ke simpul 4 (membentuk formasi cincin persegi). Konstruksikan susunan entri matriks Adjacency ($A$), matriks Derajat ($D$), dan matriks Laplacian ($L$) yang bersesuaian secara presisi.
- Buktikan secara umum (bukan hanya untuk graf tertentu) bahwa setiap baris matriks Laplacian $L = D - A$ dari sebarang graf tidak berarah selalu menjumlah menjadi nol. Dari sifat ini, jelaskan mengapa $\lambda_1 = 0$ dijamin selalu menjadi nilai eigen pertama yang berpasangan dengan vektor eigen $\mathbf{1} = \begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}^T$ untuk semua graf, tanpa terkecuali.
- Soal Pemikiran Analitis Nilai Fiedler: Jika dikondisikan sebuah graf tidak berarah $G$ memuat karakteristik matriks Laplacian yang menghasilkan nilai eigen terkecil kedua berupa $\lambda_2 = 0$, berikan analisis kritis teoretis Anda mengenai status konektivitas fisik dari graf tersebut. Apa dampaknya terhadap keberhasilan proses segmentasi data jika dieksekusi memanfaatkan metode Spectral Clustering?
- Soal Komputasi Spektral: Hitunglah polinomial karakteristik dan seluruh nilai eigen dari matriks Laplacian graf rantai linear empat simpul pada Contoh 18.9:
\[ L = \begin{bmatrix} 1 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \]Identifikasi nilai Fiedler $\lambda_2$ dan nyatakan kesimpulan Anda mengenai konektivitas graf. Petunjuk: nilai eigen-nya adalah $0,\; 2 - \sqrt{2},\; 2,\; 2 + \sqrt{2}$.