最近《復雜網路建模》這門課要考試了，正好也在跟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\)，
無向圖的平均度定義為：
\[\bar{k}=\langle k\rangle=\frac{1}{N} \sum_{i=1}^N k_i=\frac{2 E}{N} \]（這里用到握手定理：無向圖中節點的度之和等于邊數的兩倍）
而對于有向圖而言，我們定義節點的出度為“離開”該節點的邊數，入度為“進入”該頂點的邊數，有向圖中節點的度定義為其初度和入度的和，如對下面這個圖我們有：\(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\)個節點的無向圖所擁有的最大邊數為：
\[E_{\max }=\left(\begin{array}{c} 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\)，注意有向圖的鄰接矩陣不是對稱的，如對于下列的兩個圖
其鄰接矩陣分別為
\[A=\left(\begin{array}{llll} 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)
我們也可以用邊組成的集合來表示圖，如圖
就可以表示為
\[[(2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 2), (5, 1)] \]鄰接表(adjacency list)
鄰接表一般用于網路大而稀疏的情況，它可以讓我們快速地檢索到給定節點的鄰居，上面這張圖的鄰接表表示為：
現實世界中的網路常常是稀疏的，即\(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)
上面這個無權圖的鄰接矩陣為：
\[A_{i j}=\left(\begin{array}{cccc} 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)
帶權圖就是指圖中的每一條邊都有對應的一個數值權重，
上面這個帶權圖的鄰接矩陣為：
\[A_{i j}=\left(\begin{array}{cccc} 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\)被稱為一個自環，
上面這個帶自環圖的鄰接矩陣為：
\[A_{i j}=\left(\begin{array}{cccc} 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\)不為重邊，
上面這個多重圖的鄰接矩陣為：
\[A_{i j}=\left(\begin{array}{llll} 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] http://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] 《圖論概念梳理》
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525036.html
標籤：其他
上一篇：代碼隨想錄演算法訓練營第七天|454、四數相加Ⅱ|383、贖金信|15、三數之和|18、四數之和
下一篇：底層邏輯-曹政