---
# System prepended metadata

title: PageRank

---


---

## **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)**  

```python
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:  

```python
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  

---

