---
# System prepended metadata

title: Data Mining HW3 Report
tags: [homework]

---

# **Data Mining HW3 Report**
學生：王嘉臻 Q56124068

## ★ **Find a way**
- Graph 1：增加 1→4 ,4→1
    在原始Graph_1圖上增加了兩條新的邊，分別是 1→4 和 4→1，最後成功地提高了節點1的 Authority、Hub 和 PageRank 值。透過雙向連結，節點1和節點4之間形成了更緊密的聯繫，導致節點1的 Authority 和 Hub 值的提升。


|  | original | new |
| -------- | -------- | -------- |
|      | ![graph_1](https://hackmd.io/_uploads/HkOPlOh8p.png)| ![graph_1 copy_image](https://hackmd.io/_uploads/Hk_1Z_hUT.png)|
| Authority | [ <span class="blue">0.</span>  0.2 0.2 0.2 0.2 0.2]     | [0.143 0.143 0.143 0.286 0.143 0.143]    |
| Hub       | [0.2 0.2 0.2 0.2 0.2 0. ]     | [0.286 0.143 0.143 0.286 0.143 0.   ]     |
| PageRank  | [0.056 0.107 0.152 0.193 0.23  0.263]| [0.155 0.114 0.147 0.246 0.155 0.184]     |

- Graph 2：增加 3→1 ,4→1, 1→3
    透過增加了 3→1、4→1、1→3 這些額外的連結，節點1成為了更重要的中心節點，更多的節點指向它，使得其在網絡中的 Authority、Hub 和 PageRank 值中影響力增加。

|  | original | new |
| -------- | -------- | -------- |
|      |![graph_2_image](https://hackmd.io/_uploads/H1oPL_hIa.png)|![graph_2 copy_image](https://hackmd.io/_uploads/H1B_L_n86.png)|
| Hub         | [0.2 0.2 0.2 0.2 0.2]     | [0.375 0.125 0.25  0.125 0.125]     |
| Authority   | [0.2 0.2 0.2 0.2 0.2]     | [0.25  0.125 0.25  0.25  0.125]     |
| PageRank    | [0.2 0.2 0.2 0.2 0.2]     | [0.303 0.156 0.297 0.154 0.089]     |


- Graph 3：增加 1→3 ,1→4 ,3→1
    在 Graph 3 中，透過增加 1→3、1→4、3→1 這些雙向連結，對節點1的中心性進行了微調，成功提升了節點1的中心性。然而，由於節點3和節點4之間與節點1和節點3之間的雙向連結，節點3的中心性仍然相對較高。

|  | original | new |
| -------- | -------- | -------- |
|      |![graph_3_image](https://hackmd.io/_uploads/ByZoUd2I6.png)|![graph_3 copy_image](https://hackmd.io/_uploads/Sy0oI_2U6.png)|
| Hub         | [0.191 0.309 0.309 0.191]     | [0.222 0.222 0.333 0.222]     |
| Authority   | [0.191 0.309 0.309 0.191]     | [0.333 0.222 0.333 0.111]     |
| PageRank    | [0.172 0.328 0.328 0.172]     | [0.227 0.203 0.367 0.203]     |

## ★ **Algorithm description**
### 1. PageRank 
1. 初始化每個節點的 PageRank 分數，一開始都設為 1/節點數(1/N)。
2. 在指定的 iteration 內：
    - 根據其他節點的入鏈(向某一節點的連接)，計算新的 PageRank 分數。
    - 使用 damping factor 更新 PageRank 分數。
    - 對 PageRank 分數進行正規化，確保總和為 1。
3. 返回最終的 PageRank 分數。
```python=
def PageRank(adj_matrix, iteration, damping_factor):
    n_nodes = len(adj_matrix)   

    PageRanks  = np.ones(n_nodes) / n_nodes

    for _ in range(iteration):
        newPageRanks = np.zeros(n_nodes)
        for i in range(n_nodes):
            for j in range(n_nodes):
                if adj_matrix[j, i] == 1:
                    newPageRanks[i] += PageRanks[j] / np.sum(adj_matrix[j, :])
        
        PageRanks = damping_factor/n_nodes + (1-damping_factor) * newPageRanks
    
    PageRanks = PageRanks / (PageRanks.sum())
    return PageRanks
```

### 2. HITS 
1. 初始化每個節點的 authority 和 hub 分數，一開始都設為1。。
2. 在指定的 iteration 內：
    - 透過將 adjacency_matrix 的轉置（transpose）與先前的 hub 分數相乘，計算新的 authority 分數。
    - 透過將 adjacency_matrix 與先前的 authority 分數相乘，計算新的 hub 分數。
    - 對 authority 和 hub 進行正規化。
3. 返回最終的 authority 和 hub 分數。
```python=
def HITS(adj_matrix, iteration):
    n_nodes = len(adj_matrix)   
    authority = np.ones(n_nodes)
    hub = np.ones(n_nodes)
    
    old_hubs = np.copy(hub)
    old_authorities = np.copy(authority)
    for _ in range(iteration):
        new_authority = np.dot(adj_matrix.T, old_hubs)
        new_hub = np.dot(adj_matrix, old_authorities)
        
        authority = new_authority / np.sum(new_authority)
        hub = new_hub / np.sum(new_hub)
    
    return authority, hub
```
### 3. SimRank 
1. 定義了一個 calculate_SimRank 函數，根據節點的入鄰居以及 SimRank 公式計算兩個節點之間的相似度。
2. 初始化相似度矩陣 simRank，對角線元素設為1。
3. 定義了一個 update_sim_value 函數，用於更新節點對的 SimRank 值。
4. 在指定的 iteration 內：
    - 基於每對節點的入鄰居，更新相似度矩陣中的 SimRank 值。
    - 返回更新後的相似度矩陣。
```python=
def SimRank(adj_matrix, iteration, decay_factor):

    n_nodes = len(adj_matrix)

    def calculate_SimRank(a, b, simRank):
        if a == b:
            return 1.0
        
        a_neighbors = np.where(adj_matrix[:, a] != 0)[0]
        b_neighbors = np.where(adj_matrix[:, b] != 0)[0]
        a_in_size, b_in_size = len(a_neighbors), len(b_neighbors)
        
        if not a_in_size or not b_in_size:
            return 0.0
        
        temp = 0
        for i in a_neighbors:
            for j in b_neighbors:
                temp += simRank[i, j]
        
        return decay_factor * temp / (a_in_size * b_in_size)
    
    simRank = np.eye(n_nodes)  
    
    def update_sim_value(n1, n2, simRank):
        new_SimRank = calculate_SimRank(n1, n2, simRank)
        simRank[n1, n2] = simRank[n2, n1] = new_SimRank
    
    for _ in range(iteration):
        new_simRank = np.zeros_like(simRank)
        for n1 in range(n_nodes):
            for n2 in range(n1, n_nodes):
                update_sim_value(n1, n2, simRank)
                new_simRank[n1, n2] = new_simRank[n2, n1] = simRank[n1, n2]
        
        simRank = new_simRank
    
    return simRank
```

## ★ **Result analysis and discussion**
### Graph_1
- 節點1的 Authority 為0，因為沒有其他節點指向它；節點6的 Hub 為0，因為它沒有指向其他節點。這反映了節點在網絡中的被指向和指向其他節點的程度。
- 由於圖是單向的，從節點1開始，途經每個節點最終到達節點6。PageRank 考慮了節點被指向的次數以及指向其他節點的權重。節點6的PageRank相對較低，這可能表示在整個網絡中節點6被指向的次數相對較少。

|graph|![graph_1](https://hackmd.io/_uploads/HkOPlOh8p.png)| 
| -------- | -------- | 
|Authority|[0.  0.2 0.2 0.2 0.2 0.2]|
|Hub|[0.2 0.2 0.2 0.2 0.2 0. ]|
|PageRank|[[1. 0. 0. 0. 0. 0.]<br/>[0. 1. 0. 0. 0. 0.]<br/>[0. 0. 1. 0. 0. 0.]<br/>[0. 0. 0. 1. 0. 0.]<br/>[0. 0. 0. 0. 1. 0.]<br/>[0. 0. 0. 0. 0. 1.]]|
|SimRank|[0.025 0.06 0.152 0.107 0.259  0.378]|

### Graph_2
- 節點之間存在有向邊，從節點1指向節點2，節點2指向節點3，以此類推，最後節點5指向節點1，形成了一個閉環。
- Hub表示節點指向其他節點的能力，所以在Graph_2中，每個節點都有一條出向的邊，因此每個節點的 Hub 分數相等，反映了它們相似的指向性。

|graph|![graph_2_image](https://hackmd.io/_uploads/H1oPL_hIa.png)| 
| -------- | -------- | 
|Authority|[0.2 0.2 0.2 0.2 0.2]|
|Hub|[0.2 0.2 0.2 0.2 0.2]|
|PageRank|[[1. 0. 0. 0. 0. ]<br/>[0. 1. 0. 0. 0. ]<br/>[0. 0. 1. 0. 0. ]<br/>[0. 0. 0. 1. 0. ]<br/>[0. 0. 0. 0. 1. ]]|
|SimRank|[0.2 0.2 0.2 0.2 0.2]|

### Graph_3
- 節點2和節點3的 PageRank 值較高，這可能表示它們在圖中的連結和位置使得它們在 PageRank 算法中具有較高的重要性。
- SimRank 用來衡量節點之間的相似性，這裡的數值相對較高，表示節點之間的相似性較大。

|graph|![graph_3_image](https://hackmd.io/_uploads/ByZoUd2I6.png)| 
| -------- | -------- | 
|Authority|[0.191 0.309 0.309 0.191]|
|Hub|[0.191 0.309 0.309 0.191]|
|PageRank|[[1.    0.    0.538 0.   ]<br/>[0.    1.    0.    0.538]<br/>[0.538 0.    1.    0.   ]<br/>[0.    0.538 0.    1.   ]]|
|SimRank|[0.172 0.328 0.328 0.172]|


### Graph_4~6
| graph |                           Figure                           |
|:-----:|:----------------------------------------------------------:|
|   4   | ![graph_4_image](https://hackmd.io/_uploads/HyT04t2La.png) |
|   5   | ![graph_5_image](https://hackmd.io/_uploads/SyEUHY2Ua.png) |
|   6   | ![graph_6_image](https://hackmd.io/_uploads/rkgxrFhUa.png) |

### PageRank 中的 Damping Factor
- 在 PageRank 演算法中，Damping Factor 代表著一個隨機瀏覽者繼續沿著圖形尋訪的機率，而不是隨機跳到其他節點。
- 針對 Graph_3.txt 進行實驗結果如下。較高的 Damping Factor (0.9) 導致 PageRank 在節點之間的分佈更加均勻，並且有助於防止出現「懸空節點」，即沒有外部連結的節點。高 Damping Factor 有助於演算法更快地達到穩定狀態。相反，較低的Damping Factor (0.1) 使PageRank值分佈得更廣泛，不太集中在高品質的節點上。
```
Damping Factor: 0.1
PageRank Scores: [0.17241379 0.32758621 0.32758621 0.17241379]

Damping Factor: 0.3
PageRank Scores: [0.18518519 0.31481481 0.31481481 0.18518519]

Damping Factor: 0.5
PageRank Scores: [0.2 0.3 0.3 0.2]

Damping Factor: 0.7
PageRank Scores: [0.2173913 0.2826087 0.2826087 0.2173913]

Damping Factor: 0.9
PageRank Scores: [0.23809524 0.26190476 0.26190476 0.23809524]
```
![image](https://hackmd.io/_uploads/Hye3nthLp.png)

### SimRank 中的 Decay Factor
- 在 SimRank 演算法中，Decay Factor 控制著隨著節點距離的增加，相似性減少的速度。
- 針對 Graph_3.txt 進行實驗結果如下。在這個熱圖中，我們使用 SimRank 演算法計算了相似度矩陣，並測試了不同的 Decay Factor。橫軸和縱軸表示節點的索引，而每個小格子的深淺色彩反映了相對應節點對之間的相似度。深色表示較高的相似度，淺色表示較低的相似度。每張小圖的標題顯示了相對應的衰減因子，這有助於比較不同衰減因子下的相似度分佈。
- 高 Decay Factor (0.9) 下，分數整體上較高，表明更多的權重被分配給了相互連接的節點，並且 PageRank 的分數受到更強烈的 Decay Factor 影響。

![image](https://hackmd.io/_uploads/BJCgh53Ip.png)


## ★ **Effectiveness analysis**


|  Graph   | Nodes | Edges | PageRank | HITS  | SimRank |
|:--------:|:-----:|:-----:|:--------:|:-----:|:-------:|
| graph_1  |   6   |   5   |  0.004   | 0.002 |  0.013  |
| graph_2  |   5   |   5   |  0.002   | 0.001 |  0.005  |
| graph_3  |   4   |   6   |  0.001   | 0.001 |  0.002  |
| graph_4  |   7   |  18   |  0.003   | 0.000 |  0.007  |
| graph_5  |  469  | 1102  |  0.931   | 0.002 | 30.608  |
| graph_6  | 1228  | 5220  |  6.101   | 0.008 |   NAN   |
| ibm-5000 |  998  | 4798  |  4.076   | 0.005 |   NAN   |


- 總體而言，演算法執行時間的分析呈現 SimRank 通常是最耗時的，而 HITS 通常比 PageRank 更快。這也取決於圖的規模和結構，以及演算法的複雜性。較小型的圖通常能夠較快地執行，而較大型或複雜的圖可能需要更長的執行時間。
- 在大型圖（如Graph_5）上，PageRank 的執行時間相對較長，這是因為PageRank需要計算每個節點的分數，這在規模較大的圖上會變得更加耗時。
- HITS 通常只需要執行少量的迴圈，並且計算比較簡單，因此在大多數情況下執行時間相對較短。
- SimRank 的執行時間最長，因為 SimRank 需要計算節點對之間的相似性，並在多次執行迴圈中進行更新。這在圖的規模變大時會變得較耗時。