# **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 |
| -------- | -------- | -------- |
| | | |
| 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 |
| -------- | -------- | -------- |
| |||
| 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 |
| -------- | -------- | -------- |
| |||
| 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||
| -------- | -------- |
|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||
| -------- | -------- |
|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||
| -------- | -------- |
|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 |  |
| 5 |  |
| 6 |  |
### 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]
```
### SimRank 中的 Decay Factor
- 在 SimRank 演算法中，Decay Factor 控制著隨著節點距離的增加，相似性減少的速度。
- 針對 Graph_3.txt 進行實驗結果如下。在這個熱圖中，我們使用 SimRank 演算法計算了相似度矩陣，並測試了不同的 Decay Factor。橫軸和縱軸表示節點的索引，而每個小格子的深淺色彩反映了相對應節點對之間的相似度。深色表示較高的相似度，淺色表示較低的相似度。每張小圖的標題顯示了相對應的衰減因子，這有助於比較不同衰減因子下的相似度分佈。
- 高 Decay Factor (0.9) 下，分數整體上較高，表明更多的權重被分配給了相互連接的節點，並且 PageRank 的分數受到更強烈的 Decay Factor 影響。
## ★ **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 需要計算節點對之間的相似性，並在多次執行迴圈中進行更新。這在圖的規模變大時會變得較耗時。
Sign in with Wallet
Connect another wallet