圖數據挖掘(一)：網路的基本概念和表示方法
最近《複雜網路建模》這門課要考試了，正好也在跟Stanford的《CS224W：Machine Learning With Graphs》這門課，這裡就一邊整理筆記一邊複習了。
1. 網路的定義
網路(network)是一些通過鏈接(links)連接起來的對象集合，它包含以下成分：
- 對象：節點(nodes)/頂點(vertices)， 用\(N\)表示；
- 交互：鏈接(links)/邊(edges)，用\(E\)表示；
對象和交互組成的系統我們就稱為網路(或圖，graph)，用\(G(N,E)\)表示。
一般而言，我們用術語網路來稱呼一個真實的系統，如Web、社交網路、代謝網路等，此時伴隨著術語節點和鏈接進行使用；而相對應地，我們用術語圖來稱呼一個網路的數學表示，如web圖、社交圖等，此時伴隨著術語頂點和邊來使用。當然，大多數情況下我們會互換使用這兩個術語。
2. 常見網路類型及表示
2.1 有向圖和無向圖
無向圖
無向圖的鏈接是無方向(undirected)的，也對稱(symmetrical)、互反的(reciprocal), 常見的例子包括合作網路、Facebook上的朋友關係等。
有向圖
有向圖的鏈接是有方向(directed)的，此時的有向邊也稱為弧(arcs)，常見的例子包括打電話網路、Twitter上的關注網路等。
2.2 節點的度
對於無向圖而言，節點\(i\)的度(degree)\(k_i\)是指和節點\(i\)相鄰的邊數。如下圖所示\(k_A=4\)。
無向圖的平均度定義為：
\]
（這裡用到握手定理：無向圖中節點的度之和等於邊數的兩倍）
而對於有向圖而言，我們定義節點的出度為「離開」該節點的邊數，入度為「進入」該頂點的邊數。有向圖中節點的度定義為其初度和入度的和。如對下面這個圖我們有：\(k_C^{\text {in }}=2,k_C^{\text {out }}=1, k_C=3\)，有向圖的平均度定義為：
\]
在有向圖中，我們有總入度等於總出度之和，即\(\overline{k^{\text {in }}}=\overline{k^{\text {out }}}\)。此外，我們將入度\(k^{in}=0\)的節點稱為源節點(source)，將出度\(k^{out}=0\)的節點稱為匯點(slink)。
2.2 完全圖
一個有\(N\)個節點的無向圖所擁有的最大邊數為：
N \\
2
\end{array}\right)=\frac{N(N-1)}{2}
\]
邊數\(E=E_{max}\)的無向圖稱為完全圖(complete graph)，其平均度為\(N-1\)。下圖展示了一個完全圖：
2.3 二分圖
二分圖的節點可以被分為兩個不相交的子集\(U\)和\(V\)，使得每條邊都連接著\(U\)中的一個頂點和\(V\)中的一個頂點。也就是說，\(U\)和\(V\)是獨立集(independent sets)。
常見的二分圖包括：作者和其撰寫的論文構成的網路、演員和其出演的電影構成的網路、用戶和其打分的電影構成的網路。
對於上面這個二分圖，我們還可以畫出其對應的「摺疊」（folded）網路如下：
「摺疊」網路可以用來表示作者之間的合作關係和電影合作網路。
2.4 圖的表示
鄰接矩陣(adjacency matrix)
我們可以用鄰接矩陣\(A\)來表示圖，其中當節點\(i\)和\(j\)之間存在鏈接時\(A_{ij}=1\)，否則\(A_{ij}=0\)。注意有向圖的鄰接矩陣不是對稱的。如對於下列的兩個圖
其鄰接矩陣分別為
0 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0
\end{array}\right), \quad A=\left(\begin{array}{llll}
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0
\end{array}\right)
\]
邊表(edge list)
我們也可以用邊組成的集合來表示圖，如圖
就可以表示為
\]
鄰接表(adjacency list)
鄰接表一般用於網路大而稀疏的情況，它可以讓我們快速地檢索到給定節點的鄰居。上面這張圖的鄰接表表示為：
& □\space 1: \\
&□\space 2: 3,4 \\
&□\space 3: 2,4 \\
&□\space 4: 5 \\
&□\space 5: 1,2
\end{aligned}
\]
現實世界中的網路常常是稀疏的，即\(E\ll E_{max}\)(或\(\bar{k}\ll N – 1\))，比如下面就列出了幾種現實世界網路的屬性：
| 網路名稱 | 節點數\(N\) | 平均度\(\bar{k}\) |
|---|---|---|
| WWW(Stanford-Berkeley) | 319,717 | 9.65 |
| Social networks(LinkedIn): | 6,946,668 | 8.87 |
| Communication(MSN IM): | 242,720,596 | 11.1 |
| Coauthorships (DBLP): | 317,080 | 6.62 |
| Internet (AS-Skitter): | 1,719,037 | 14.91 |
| Roads (California): | 1,957,027 | 2.82 |
| Proteins(S. Cerevisiae): | 1,870 | 2.39 |
這樣用鄰接矩陣進行存儲的話就會有大量的0導致存儲空間浪費（鄰居矩陣密度(\(E/N^2\))：\(\text{WWW}=1.51\times 10^{-5}\), \(\text{MSN IM}=2.27\times 10^{-8}\)）。此時鄰接表就有了用武之地。
關於邊屬性(edge attributes)
圖的邊可能還自帶有屬性，包括：
- 權重： 如通訊頻率
- 排名： 如最好的朋友、第二好的朋友
- 類型： 如朋友、親屬、同事
- 符號： 如朋友vs陌生人、信任vs不信任
- 一些依賴於圖其餘部分結構的屬性：如共同朋友的數量
2.5 更多圖的類型
無權圖(unweighted graph)
上面這個無權圖的鄰接矩陣為：
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0
\end{array}\right)
\]
這裡\(A_{ii} = 0\)，\(A_{ij}=A_{ji}\)。
其邊數\(E=\frac{1}{2} \sum_{i, j=1}^N A_{i j}\)，平均度\(\bar{k}=\frac{2 E}{N}\)。
常見的無權圖例子包括朋友網路，超鏈接網路。
帶權圖(weighted graph)
帶權圖就是指圖中的每一條邊都有對應的一個數值權重。
上面這個帶權圖的鄰接矩陣為：
0 & 2 & 0.5 & 0 \\
2 & 0 & 1 & 4 \\
0.5 & 1 & 0 & 0 \\
0 & 4 & 0 & 0
\end{array}\right)
\]
這裡\(A_{ii}=0\)，\(A_{ij}=A_{ji}\)。
其邊數\(E=\frac{1}{2} \sum_{i, j=1}^N \operatorname{nonzero}\left(A_{i j}\right)\)，平均度\(\bar{k}=\frac{2 E}{N}\)。
常見的帶權圖例子包括合作網路、英特網、公路網路。
帶自環(self-loops/self-edges)的圖
對\(E\)中的邊\(e=(u, v)\)，若\(u=v\)，則\(e\)被稱為一個自環。
上面這個帶自環圖的鄰接矩陣為：
1 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1
\end{array}\right)
\]
這裡\(A_{ii}\neq 0\)，\(A_{ij}=A_{ji}\)。
其邊數\(E=\frac{1}{2} \sum_{i, j=1, i \neq j}^N A_{i j}+\sum_{i=1}^N A_{i i}\)。
常見的帶自環的圖包括蛋白質網路，超鏈接網路等。
多重圖(multigraph)
多重圖是一個允許有重邊（也稱多重邊，平行邊）的圖，重邊即兩個頂點之間可能存在多條邊。在無向圖中，關聯一對頂點的無向邊如果多於1條，則稱這些邊為重邊；在有向圖中，關聯一對頂點的有向邊如果多於1條，並且這些邊的始點與終點相同(也就是他們的方向相同)，稱這些邊為重邊。這也就是說在無向圖中\((u, v)\)和\((v, u)\)算一組重邊，而在有向圖中，\(u\rightarrow v\)和\(v\rightarrow u\)不為重邊。
上面這個多重圖的鄰接矩陣為：
0 & \underline{2} & 1 & 0 \\
\underline{2} & 0 & 1 & \underline{3} \\
1 & 1 & 0 & 0 \\
0 & \underline{3} & 0 & 0
\end{array}\right)
\]
這裡\(A_{ii}=0\)，\(A_{ij}=A_{ji}\)。
其邊數\(E=\frac{1}{2} \sum_{i, j=1}^N \text { nonzero }\left(A_{i j}\right)\)，平均度\(\bar{k}=\frac{2 E}{N}\)。
常見的多重圖例子包括通訊網路，合作網路等。
3. 圖的連通性
無向圖的連通性
對於無向圖，若任意兩個頂點都能夠通過一條路徑連接，則我們稱其為連通的。
一個不連通的圖由兩個或多個連通的分量（connected components）組成（也稱為連通塊）。其中巨大的連通分量我們將其稱為gaint component，如下圖所示就有3個連通分量：
圖中的節點\(H\)的度\(d(H)=0\)，我們將其稱為孤立點(isolated node)。
我們有以下定義
- 橋邊(bridge edge)/割邊(cut edge)：如果將該邊去除，則圖變得不連通。可以發現，一條邊\(e\)是橋邊當且僅當\(G /\{e\}\)的連通分量個數大於\(G\)的連通分量個數。
- 關節點(Articulation node)/割點(cut vertex)：如果將該點去除，則圖變得不連通。一個點\(v\)是割點當且僅當\(G /\{v\}\)的連通分量個數大於\(G\)的連通分量個數。
有向圖的連通性
對於有向圖，若圖中每個節點都有一條到其它節點的路徑（反之亦然），如A-B路徑和B-A路徑，我們就稱它是強連通的；如果只有在我們忽視了邊的方向的條件下才是連通的，則稱它為弱連通的。
上面這個有向圖是連通的，但不是強連通的（比如不存在按照邊的方向從\(F\)到\(G\)的路徑）。
4. 現實世界中的常見網路類型
- Email網路： 有自環的有向多重圖
- Facebook朋友關係網路：無向、無權圖
- 引用網路：有向、無權、無環（acyclic）的圖（無環是因為較早發表的文章不能引用較晚發表的文章）
- 合作網路：無向（帶權？）多重圖
- 打電話網路：有向（帶權？）多重圖
- 蛋白質相互作用網路：無向、無權、有自環的圖（蛋白質可以自我相互作用）
參考
[1] //web.stanford.edu/class/cs224w/
[2] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.
[3] Barabási A L. Network science[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1987): 20120375.
[4] 《圖論概念梳理》
