---

## **Apa itu PageRank?**
PageRank adalah algoritma yang dikembangkan oleh **Larry Page dan Sergey Brin** (pendiri Google) untuk mengukur **"kepentingan"** suatu halaman web berdasarkan struktur tautan (link) dalam jaringan.

> Ide utama:
> **Halaman yang banyak ditauti oleh halaman penting → juga penting.**

---

## **Konsep Matematis**

Misalkan:
- $G=(V,E)$: graf berarah dengan $n$ node (halaman)
- $A$: matriks adjacency (jika ada link dari $i\to j$, maka $A_{ij}=1$)
- $d$: **damping factor** (biasanya $d=0.85$)
- $\mathbf{r}$: vektor PageRank (ukuran $n\times1$)

### **Rumus PageRank (Versi Stokastik)**

$\mathbf{r}=d\cdot M\mathbf{r}+\frac{1-d}{n}\mathbf{1}$

Di mana:
- $M$: matriks transisi stokastik (kolom jumlahnya 1)
- $\mathbf{1}$: vektor semua elemen 1
- $\frac{1-d}{n}$: probabilitas "teleportasi acak" ke halaman mana saja

> **Catatan**: Dalam PageRank asli, **matriks $M$ dibangun dari kolom**, bukan baris (karena aliran "suara" datang **ke** suatu halaman).

---

## **Algoritma PageRank (Iteratif)**

1. **Bangun matriks adjacency** dari graf.
2. **Normalisasi kolom** → jadikan matriks stokastik $M$ .
- Jika node $j$ punya out-degree = 0 (dangling node), ganti kolomnya dengan $\frac{1}{n}$ (teleportasi penuh).
3. **Inisialisasi** vektor PageRank: $\mathbf{r}^{(0)}=\left[\frac{1}{n},\frac{1}{n},\dots,\frac{1}{n}\right]^T$
4. **Iterasi** hingga konvergen:
$\mathbf{r}^{(k+1)}=d\cdot M\mathbf{r}^{(k)}+\frac{1-d}{n}\mathbf{1}$
5. **Hentikan** jika $\|\mathbf{r}^{(k+1)}-\mathbf{r}^{(k)}\|_1<\epsilon$ (misal $\epsilon=10^{-6}$)

---

## Contoh Manual

---

### **0: Definisikan Graf**

Misalkan kita punya **3 halaman web**: A, B, C
Dengan tautan sebagai berikut:
- **A → B**
- **A → C**
- **B → C**
- **C → A**

> Tidak ada tautan keluar dari C selain ke A.
> Tidak ada dangling node (semua node punya out-degree ≥ 1).

**Label node**:
- A = node 0
- B = node 1
- C = node 2

---

### **1: Bangun Matriks Adjacency**

Matriks adjacency $A$ (baris = dari, kolom = ke):

$$
A =
\begin{bmatrix}
0 & 1 & 1 \\ % A → B, A → C
0 & 0 & 1 \\ % B → C
1 & 0 & 0 % C → A
\end{bmatrix}
$$

---

### **2: Bangun Matriks Transisi $M$ (Kolom-Stokastik)**

> **Penting**: Dalam PageRank asli, **aliran masuk** dihitung → kita butuh **matriks transisi berdasarkan out-degree**, lalu **transpose** agar kolom merepresentasikan "dari".

#### a. Hitung out-degree tiap node:
- out(A) = 2 → bagi baris A dengan 2
- out(B) = 1 → bagi baris B dengan 1
- out(C) = 1 → bagi baris C dengan 1

Matriks probabilitas transisi (baris-stokastik):

$$
P =
\begin{bmatrix}
0 & 1/2 & 1/2 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{bmatrix}
$$

#### b. Transpose agar jadi **kolom-stokastik** (untuk PageRank):

$$
M = P^T =
\begin{bmatrix}
0 & 0 & 1 \\
1/2 & 0 & 0 \\
1/2 & 1 & 0
\end{bmatrix}
$$

> Sekarang, **kolom $j$** menunjukkan distribusi probabilitas **dari node $j$** ke node lain.

Contoh:
- Kolom 0 (dari A): 0 ke A, 1/2 ke B, 1/2 ke C → benar.
- Kolom 2 (dari C): 1 ke A, 0 ke B, 0 ke C → benar.

---

### **3: Inisialisasi Vektor PageRank**

Jumlah node: $n = 3$
Vektor awal:

$$
\mathbf{r}^{(0)} = \begin{bmatrix} 1/3 \\ 1/3 \\ 1/3 \end{bmatrix} \approx \begin{bmatrix} 0.3333 \\ 0.3333 \\ 0.3333 \end{bmatrix}
$$

Gunakan **damping factor** $d = 0.85$
Teleportasi: $\frac{1 - d}{n} = \frac{0.15}{3} = 0.05$

---

### **4. Inisialisasi**
$\mathbf{r}^{(0)}=\begin{bmatrix}\frac{1}{3}\\\frac{1}{3}\\\frac{1}{3}\end{bmatrix},\quad d=0.85,\quad\frac{1-d}{n}=0.05$

---

### **5. Iterasi 1: $\mathbf{r}^{(1)}=0.85\cdot M\mathbf{r}^{(0)}+0.05\cdot\mathbf{1}$**

Hitung $M\mathbf{r}^{(0)}$:

$M\mathbf{r}^{(0)}=\begin{bmatrix}0\cdot\frac{1}{3}+0\cdot\frac{1}{3}+1\cdot\frac{1}{3}\\\frac{1}{2}\cdot\frac{1}{3}+0\cdot\frac{1}{3}+0\cdot\frac{1}{3}\\\frac{1}{2}\cdot\frac{1}{3}+1\cdot\frac{1}{3}+0\cdot\frac{1}{3}\end{bmatrix}=\begin{bmatrix}\frac{1}{3}\\\frac{1}{6}\\\frac{1}{2}\end{bmatrix}\approx\begin{bmatrix}0.3333\\0.1667\\0.5000\end{bmatrix}$

Kalikan dengan 0.85:
$0.85\cdot M\mathbf{r}^{(0)}\approx\begin{bmatrix}0.2833\\0.1417\\0.4250\end{bmatrix}$

Tambahkan 0.05:
$\mathbf{r}^{(1)}=\begin{bmatrix}0.2833+0.05\\0.1417+0.05\\0.4250+0.05\end{bmatrix}=\begin{bmatrix}0.3333\\0.1917\\0.4750\end{bmatrix}$

---

### **6. Iterasi 2: $\mathbf{r}^{(2)}=0.85\cdot M\mathbf{r}^{(1)}+0.05\cdot\mathbf{1}$**

$M\mathbf{r}^{(1)}=\begin{bmatrix}0\cdot0.3333+0\cdot0.1917+1\cdot0.4750\\\frac{1}{2}\cdot0.3333+0+0\\\frac{1}{2}\cdot0.3333+1\cdot0.1917+0\end{bmatrix}=\begin{bmatrix}0.4750\\0.16665\\0.35835\end{bmatrix}$

Kalikan dengan 0.85:
$\approx\begin{bmatrix}0.40375\\0.14165\\0.30460\end{bmatrix}$

Tambahkan 0.05:
$\mathbf{r}^{(2)}=\begin{bmatrix}0.45375\\0.19165\\0.35460\end{bmatrix}\approx\begin{bmatrix}0.4538\\0.1917\\0.3546\end{bmatrix}$

---

# Penjelasan

> - Bangun matriks $P$ di mana $P_{ij}=$ probabilitas **dari $i$ ke $j$** (baris-stokastik).
> - Maka, update PageRank:
> $\mathbf{r}^{(k+1)}=d\cdot P^T\mathbf{r}^{(k)}+\frac{1-d}{n}\mathbf{1}$
> - Ini setara dengan:
> $r_i^{(k+1)}=d\sum_{j\to i}\frac{r_j^{(k)}}{\text{out-degree}(j)}+\frac{1-d}{n}$

---

Rumus langsung per node:
$r_i=d\sum_{j\in\text{in-links}(i)}\frac{r_j}{\text{out-degree}(j)}+\frac{1-d}{n}$

Untuk graf kita:
- in(A) = {C} → $r_A=d\cdot\frac{r_C}{1}+0.05$
- in(B) = {A} → $r_B=d\cdot\frac{r_A}{2}+0.05$
- in( C) = {A, B} → $r_C=d\cdot\left(\frac{r_A}{2}+\frac{r_B}{1}\right)+0.05$

Coba dengan $\mathbf{r}^{(0)}=[1/3,1/3,1/3]$:
- $r_A^{(1)}=0.85\cdot(1/3)+0.05=0.2833+0.05=0.3333$
- $r_B^{(1)}=0.85\cdot(1/3)/2+0.05=0.85\cdot1/6+0.05≈0.1417+0.05=0.1917$
- $r_C^{(1)}=0.85\cdot(1/6+1/3)+0.05=0.85\cdot0.5+0.05=0.425+0.05=0.475$

data seterusya

---
## **Implementasi Python (Scratch)**

import numpy as np

def pagerank(adj_matrix, d=0.85, max_iter=100, tol=1e-6):
    """
    Hitung PageRank dari matriks adjacency.
    
    Parameters:
        adj_matrix : array-like, shape (n, n)
            Matriks adjacency (1 jika ada link i -> j)
        d : float
            Damping factor (default: 0.85)
        max_iter : int
            Maksimum iterasi
        tol : float
            Toleransi konvergensi
    
    Returns:
        r : ndarray, shape (n,)
            Vektor PageRank
    """
    adj = np.array(adj_matrix, dtype=float)
    n = adj.shape[0]
    
    # Tangani dangling nodes (baris dengan jumlah 0)
    out_degree = np.sum(adj, axis=1)
    for i in range(n):
        if out_degree[i] == 0:
            adj[i, :] = 1.0  # taut ke semua halaman
    
    # Normalisasi baris → jadi matriks transisi (baris jumlah = 1)
    # TAPI: PageRank asli menggunakan TRANSPOSE → aliran masuk
    # Jadi kita transpos untuk membuat kolom = out-link
    M = adj / np.sum(adj, axis=1, keepdims=True)
    M = M.T  # Sekarang M[j,i] = probabilitas dari i ke j
    
    # Inisialisasi
    r = np.ones(n) / n
    teleport = (1 - d) / n
    
    for _ in range(max_iter):
        r_new = d * M @ r + teleport
        if np.linalg.norm(r_new - r, 1) < tol:
            break
        r = r_new
    
    return r

# Contoh penggunaan
if __name__ == "__main__":
    # Graf: 0 → 1, 0 → 2, 1 → 2, 2 → 0
    A = [
        [0, 1, 1],  # 0 links to 1 and 2
        [0, 0, 1],  # 1 links to 2
        [1, 0, 0],  # 2 links to 0
    ]
    
    pr = pagerank(A)
    print("PageRank:")
    for i, score in enumerate(pr):
        print(f"Node {i}: {score:.4f}")

### Output Contoh:

PageRank:
Node 0: 0.3878
Node 1: 0.2143
Node 2: 0.3979

> Node 2 paling penting karena ditauti oleh Node 0 dan 1, dan menauti kembali ke Node 0.

---

## **Menggunakan NetworkX **

Implementasi menggunakan Networkx:

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(0, 1), (0, 2), (1, 2), (2, 0)])

pr = nx.pagerank(G, alpha=0.85)
print(pr)

---
## Damping Factor
**Damping factor** (faktor redaman) adalah parameter dalam algoritma PageRank yang merepresentasikan probabilitas seorang pengguna web akan terus mengikuti tautan (link) saat menjelajah internet
**Mengapa Damping Factor ($d=0.85$)?**
- Mencegah **jebakan** (misal: dua halaman saling menauti tapi tidak keluar).
- Mewakili perilaku pengguna:
- 85% waktu: mengikuti link
- 15% waktu: melompat acak ke halaman lain

---