社群網路的圖的定義
- Node - 點, 個人
- Edge - 邊, 人與人的關係
- Undirected graph and directed graph
- undirected graph - 邊沒有特定方向
- directed graph - 邊具有方向性
- Adjacency matrix - 用矩陣來表達圖的關係, 1 代表有連接, 0 代表沒有連接
- Paths - 路徑, 一連串由 Edge 連接起來的 Node 組成的東西
- Simple Path - 無重複點的路徑
- Cycles - 只有起點跟終點是同一點的路徑
- 特點是 - redundancy - 代表這個圈就算任一邊斷掉，也是相連的
- 在社群網路中 很常見
- Connected Graph - 此 Graph 上任兩點間都有 path ，使之能夠抵達另一點
- 大部分的社群網路都是這樣，越大越是如此
- 在社群網路中 很常見
- Connected components
下面是有三個 node 的範例
- Giant Components
- 有顯著影響力(很大的)的 Components
- 幾乎所有的 large network 都有 giant component
- 幾乎所有大網路都只有一個 giant component
- 因為兩邊所有點都沒連接的機率非常低
- 假設雙方各有 N 個點，點跟點連接的機率是 99%
- 則完全沒有點連接的機率是 $0.01*{N^2}$
- Distance
- 兩點之間最短距離
- 用BFS演算法(breadth-first search)找最快
- First find all friends at a distance of 1
- Find all their friends (not including distance-1 friends), and declare these to be distance 2
- Repeating this procedure to find friends of farther away
- Small-world property
- Giant Components 中任兩點距離比想像中短
- Six degrees of separation
- 每個人走六個點就能夠到達另一點
