# Graph + Social Netwrok Analyze
## Graph


## Complete Graph(完整圖)

## Subgraph(子圖)
## Path (路徑)
## Simple Path (簡單路徑)
## Cycle (迴圈)
## Connected (連通)
- Tree也是connected、no cycle、edge = (n-1)條
[原因]: Tree 的 root 到每個node都有路徑


## 分支度(Degree)

## Degree 與 Edge 間的關係:公式

## Adjacency Matrix (相鄰矩陣)
#### 無向圖-Adjacency Matrix，必對稱

#### 有向圖-Adjacency Matrix，不一定對稱


## Adjacent list
### 無向圖的Adjacent list



### 有向圖的Adjacent list




#### adjacent matrix v.s. adjacent list

# Graph Traversal

### Tree 的 edge 種類
>邊的分類(Edge classification)
>1. Tree edge : 若可以經由一條邊走訪到新的節點，則稱該邊為Tree edge
>2. Foward edge : 可以直接存取到子孫的邊
>3. Backward edge : 可以直接存取到祖父的邊
>4. Cross edge : 連接了兩棵子樹的邊
>
| 追蹤方式 | 有向圖 DFS | 無向圖 DFS | 有向圖 BFS | 無向圖 BFS |
| -------- | ---------- | --------- | --- | --- |
| 追蹤的edge種類 | Tree edge、Back edge、Foward edge、Cross edge |Tree edge、Back edge | Tree edge、Back edge、Cross edge |Tree edge、Cross edge |

## DFS (Depth First Search,深度先搜尋)
>DFS顧名思義，就是盡量的深入遍歷整張圖。找到一個節點v，遍歷所有v能夠到達的節點，一但v能夠到達的節點都已經被發現，則回朔到v的前驅節點，也就是v的父節點，接著以該節點作為出發的節點，繼續尋找能夠到達的節點，不斷重複這樣的過程，直到整張圖被遍歷

>程式碼走訪完結果 = A B D E F C
#### Stack實作DFS

def dfs(start_vertex, graph_dict):
    visited = set()   # 使用集合來保存已訪問的節點
    stack = [start_vertex]  # python的list可做為stack

    while stack:  # 當堆疊不為空時
        vertex = stack.pop()   # pop()掉最上面的node
        if vertex is not visited:  # 如果這個節點還未訪問
            print(vertex, end=" ")  # 印出來
            visited.add(vertex)     # 並標記加入到訪問過的set中
            stack.extend(graph_dict[vertex])  # 先對該node的鄰居全都丟入stack，後續會再處理
            # 利用list.extend()用於將一個list（或任何可迭代對象）的所有元素添加到另一個list的末端
            # 因為是while loop 再回去前面一一pop 檢視是否visited過了


# 測試 dfs_stack 函數
graph_dict = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
dfs('A', graph_dict)

---
#### Recrusive 版 DFS

visited = set()  # 建立一個初始化集合
graph_dict = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}


def dfs(vertex):  # vertex為目標走訪值
    global visited, graph_dict  # 當一個區域變數要修改全域變數的值時，要宣告為Global variable才能真正修改
    if vertex in visited:  # 如果當前節點已經被訪問過（即它已經在 visited 集合中）
        return visited    # 則回傳 visited 集合
    visited.add(vertex)   # 若當前節點尚未被訪問，則將其添加到 visited 集合中
    print(vertex, end=" ")   # 印出該點

    # 要去拜訪vertex的鄰居們，利用vertex去比對dict的key，當有找到時就回傳該列表
    for neighbor in graph_dict[vertex]:
        # neighbor會走訪該列表內的node
        if neighbor not in visited:  # 若該點未被拜訪過，則代表它不在visited集合內
            dfs(neighbor)            # 對它做 dfs 去拜訪他
    return visited


# 測試 dfs 函數
dfs('A')

## BFS (Breadth First Search, 廣度先搜尋)
>BFS是用來遍歷一張圖的最簡單演算法，也是很多在圖論演算法的原型，許多演算法都是基於BFS，像是Prim最小生成樹，Dijkstra演算法等等。
>
>給定一張圖G(V,E)，和一個節點s，BFS可以走訪s能夠到達的所有節點v，並且能夠紀錄s到各個節點的最少邊數，也就是最短距離，同時會產生出一棵BST Tree。這個數會以s作為樹的根結點，並且包含s能夠到達的所有節點v。BST可以用在有向圖，也可以用在無向圖中。
> - BFS在undirected graph中,邊的種類只有tree 及 cross edge
>- 在一個unweighted,undirected graph(無加權無向圖)中,只有BFS 可以找到shortest path
>

adjacency_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}


def BFS(start_vertex):
    visited = set()
    queue = [start_vertex]  # 利用list可實現Queue
    while queue:
        vertex = queue.pop(0)  # FIFO 利用pop(0)取出最前端元素
        if vertex not in visited:
            print(vertex, end=" ")
            visited.add(vertex)
            queue.extend(
                neighbor for neighbor in adjacency_list[vertex] if neighbor not in visited)

BFS('A')

## AOV Network (Activity On Vertex)

## Topological Order
>給定一個不具備cycle的AOV network,則至少可以找到>=1組的頂點拜訪順序，滿足若在AOV network中,頂點i有路徑到達頂點j,則在此拜訪順序中,i必定出現在j之前

>常用於AOV網路來確保所有的任務都按照正確的先後順序進行


###############################################




### Topology Sort
> 1. 拓撲排序是有向非循環圖(DAG)的節點的線性排序，使得對於圖中的每一條有向邊(u, v)，節點u都出現在節點v之前。
>
> 2. 拓撲排序的一個常見算法是使用DFS。當DFS訪問一個節點並完成訪問其所有鄰居後，該節點被推入一個堆疊。因此，最後一個被訪問的節點是最先被推入堆疊的，這實際上給了我們一個拓撲排序
> 3. 最重要的一點：只有directed acyclic graph(DAG)的Topological Sort(拓撲排序)才有意義。

import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict  # 有包好的資料結構

class Graph:
    def __init__(self, vertices):  # 類別初始化
        self.adjacencyList = defaultdict(list)  # 相鄰列表，用於儲存邊
        self.vertices = vertices  # 　儲存圖的節點數
        self.visited = [False] * vertices  # 使用bool值=False，來記錄DFS所訪問過的node
        self.stack = []  # 儲存Topology Sort完的結果
        self.G = nx.DiGraph()  # 是 networkx 的有向圖物件，將用它來畫圖

    def createEdge(self, u, v):  # 目的是在圖中添加一條邊，從節點 u 指向節點 v
        # 將node v 添加到node u 的adjacent list中。代表圖中會存在一條從 u 到 v 的邊
        self.adjacencyList[u].append(v)
        self.G.add_edge(u, v)  # 　視覺化用，將邊(u, v)添加到 networkx 的圖中

    def dfs(self, v):   # 先定義DFS，等等要給Topology Sort使用
        self.visited[v] = True   # 將拜訪的該點先設為True

        for i in self.adjacencyList[v]:  # 遍歷該點v的所有相鄰節點
            if not self.visited[i]:  # 若有相鄰節點未被訪問
                self.dfs(i)  # Recrusive，訪問他!

        self.stack.insert(0, v)
        # 使用模仿stack 的行為，但透過insert(0, v)以確保最後完成DFS的節點在拓撲排序中的位置是正確的。如果使用 append，那麼在返回拓撲排序結果之前，我們還需要反轉這個列表
        # 使用 self.stack.insert(0, v)，會將節點 v 放在 "堆疊" 的最底部（也就是list的開頭）。隨著更多的節點完成DFS，它們會持續被放到這個 "堆疊" 的最底部。
        # 所以，最後當DFS完成，self.stack 的第一個元素（也就是最底部）是最後一個完成DFS的節點，而最後一個元素（也就是最頂部）是第一個完成DFS的節點。
        # 這是拓撲排序的核心步驟，因為最依賴於所有其他節點的節點，應該先被處理。所以把它插入到list前端

    def topologicalSort(self):
        for i in range(self.vertices):  # 遍歷Graph中所有點
            if not self.visited[i]:  # 檢查節點 i 是否已被訪問
                self.dfs(i)          # 如果還沒有，則執行 DFS
        return self.stack            # 返回結果堆疊，這是拓撲排序的結果。

    def drawGraph(self):
        pos = nx.spring_layout(self.G)
        nx.draw(self.G, pos, with_labels=True, node_size=700, node_color="skyblue",
                font_size=15, font_weight='bold', width=2.0, edge_color="gray")
        plt.title("Directed Acyclic Graph (DAG)")
        plt.show()


# 測試
G = Graph(6)
G.createEdge(0, 1)
G.createEdge(0, 2)
G.createEdge(1, 3)
G.createEdge(1, 5)
G.createEdge(2, 3)
G.createEdge(2, 5)
G.createEdge(3, 4)
G.createEdge(5, 4)
print("Topological Sort Order:", G.topologicalSort())
G.drawGraph()


>>輸出 :Topological Sort Order: [0, 2, 1, 5, 3, 4]
>>
>>[解釋]
>>從In-degree=0開始，每個節點的排序位置都在其父節點之後。
>>結果不唯一，可能會得到不同的結果，例如[0, 1, 2, 5, 3, 4]

## AOE Network (Activity On Edge) ★★★(資管常用)



EX.


### Articulation Point(關節點 or 切點)
>在一個connected無向圖中，若將某個頂點及其他連結的邊刪除後，剩下的Graph會變成unconnected
>

### Biconnected Graph (二連通圖)
>一個不具有Articulation Point 的 connected undirected grapg 即是。
>
>特點: 斷了一條還是有其他路徑可到，不會造成不連通。
>應用: 通訊網路布局(不想因某個server 或基地台掛了，而造成通訊中斷)


### Biconnected Component (二連通子圖)
> 令G=(V,E)是connected無向圖，令G'是G的一個子圖，且滿足:
> 1. G'是Biconnected Graph (沒有關節點)
> 2. G'是Max component (代表無其他子圖可包含G'，且此子圖是Biconnected)


EX.

### Vertex Cover(頂點覆蓋)
>又稱node cover。Node集合之所有連結的邊會涵蓋(等於)Graph所有的邊集合
>

### Minimum vertex cover
>採用最少頂點數的vertex cover。是NP-Hard Problem
>

---

### Bipartite graph (二裂圖)
>Graph中vertex集合會分解成兩個disjoint set,使得在兩個集合中都沒有原先Graph中互相相鄰的頂點
>著色問題:給兩個顏色，相鄰頂點必不同色
>A bipartite graph must be two-colorable
>Bipartite graphs are equivalent to two-colorable graphs.

### Clique
>是某無向圖的子圖，且子圖為Complete Graph(具有最多邊數的子圖)
>
















> k代表可以允許少幾個連結





>當節點數量呈子數級成長時，節點之前平均距離的成長是呈線性的


### 如何找 Articulation Points?
難:Leetcode hard ★★★★★
1. 對Graph實施DFS，求出每個頂點的dfn(DFS number,初值可以從0 or 1開始)
2. 畫出DFS spanning tree, 也標示出back edges
3. 求出每個頂點v的low值
>low(x) = min{ dfn(x) , dfn(w) } //dfn(w)為x之後的所有後代子孫，若有後退邊可透過他往回走，取出較小的DFS值
4. 開始判斷。規則:
>1. If x 是 DFS spanning Tree的root:
>>如果x的子節點數(degree)>1,則x是articulation point
>2. If x 不是root，也不是leaf:
>>則針對x的任一個子點W, if low(W) >= dfn(x)成立，則x是articulation point
>3. If x 不是root，是leaf:
>>絕對不是articulation point
>>

Code:

https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

## Social Network data
用來處理關係間的資料

在基本的鄰接矩陣中，無權重的圖用0和1表示節點間是否存在邊。其中1表示兩個節點之間存在邊，0表示不存在。

- 若是加權圖（每條邊都有一個相應的權重或成本），則鄰接矩陣中的值會是邊的權重。在這種情況下，鄰接矩陣可以包含除0和1之外的其他數值。

若資料中呈現很多0，代表有關聯的其實不多，會呈現出稀疏矩陣(sparse matrix)樣子
所以要改用Directed matrix(有向性矩陣)去存，避免空值太多而浪費空間
----
# Social Network 範疇
## Graph Data
可以記錄在一個應用場景下，角色之間的關係
eg. Twitter是、Meta等社群媒體也皆採用Graph去存data

[優點]:
1. 底層資料儲存與傳統DB不同 快!
2. 實現不犧牲accuray情況下，又可提高precision

- 此圖展示測量值的精確度(Precise)和準確度(Accurate)之間的關係
#### 精確(Precise):代表與其他測量值彼此是很接近的，但不一定接近真實值(有可能會不準確)
#### 準確(Accurate):代表接近真實值，但可能與其他測量值相距較遠(可能會不精確)
左上：表示精確且準確。
左下: 很精確(兩個測量值皆在相同位置)但不準確(遠離真實值)
右上: 較準確但不精確(接近真實值但兩個測量值結果相距遠)
右下: 既不精確也不準確










### 名詞定義

>在有向網路，兩個node的關係有四種可能(eg. 無關係、你到他、他到你、雙向連結)，此圖有3個node，又存在3個邊，共有4^3種關係

## Introduction to the Formal Analysis of Social Networks
[Typers of network data]
## 1. Egocentered Networks (自我中心網路)

選某個node作為中心與周邊的node進行分析

## 2. Complete Networks
所有node都會有連結
eg. 友誼間的關係建立。
但現實中資料取得會是個大問題








#### Eccentricity (離心率)
>用來測量所有node在網路中的位置，用來判斷是中心or邊緣節點。利用計算所有node的最大最短路徑，數值愈小就是中心node，愈大就是邊緣node。


### Diameter 直徑
>最大的eccentricity(從所有node的最大最短路徑中)即是直徑

### Radius 半徑
>最小的eccentricity(從所有node的最大最短路徑中)即是半徑


>老師講解:https://tronclass.scu.edu.tw/course/77502/learning-activity/full-screen#/567269

### 互惠度


### 結構洞



#### 冗餘度、有效規模、效率計算方法:
>1. 先求出目標node:E的degree = 4 (有四個相互連接的子點)
>2. 再計算相鄰的頂點。
>3. A: A的degree = 2，扣掉與E相鄰的一條,剩下1
>4. B: B的degree = 1，扣掉與E相鄰的一條,剩下0
>5. C: C的degree = 2，扣掉與E相鄰的一條,剩下1
>6. D: D的degree = 3，扣掉與E相鄰的一條,剩下2
>7. 全部相鄰節點ABCD相加，再除目標節點的degree即為冗餘度(Redundancy)
>8. 有效規模 = 目標E的degree - Redundancy
>9. 效率 = 有效規模/(實際規模,就是degree)



>老師講解: https://www.youtube.com/watch?v=T4hBzxWzXZ4&ab_channel=%E8%83%A1%E7%AD%B1%E8%96%87

### Transitivity 傳遞性




參考來源:
1. 東吳 胡筱薇教授 社群網路分析授課
2. 聯合 陳士杰教授 資料結構授課
3. 洪逸 資料結構