社會網絡分析(3-1)-基於圖理論的網絡表達及分析方法
Network Representation and Analysis based on Graph Theory；Stanford CS224W Machine Learning with Graphs — Lecture 2 to 3
前言
在前兩篇文章中，介紹了關於個人與群體意見形成時的一種表達，其中提到了不少基礎假設與模型推演結果，不論是 F-J 模型或是 Bounded Confidence，不約而同地都提到了關於同儕/社會中他者的概念，也就是在現實情況下，人們的意見多半會彼此參照，並基於這個假設，並給出一些其他的參數如個人起始意見、置信度等情況下，進行最終的意見模擬。
然而，實務中我們怎麼合理地去瞭解人們的交互參照情況呢 ? 這涉及到了兩個面向，其一是我們如何在給定一組資料的情況下快速地去找出誰與誰彼此參照，其二是我們找到了參照的情況以後，如何根據該情況去設定合理的權重來反映人們的參照影響程度 ? 本系列的第三部分就要透過 Stanford 的一篇論文對其進行剖析，連結如下 :
Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach : http://infolab.stanford.edu/~crucis/pubs/paper-nmfagm.pdf然而，在開始之前，我們要先建立一些概念，前兩篇說明的都是基於線性、非線性方程組對於個人資料的表達方法，如果要表達人與人之間的關係，我們需要進入到圖論的世界 (Graph Theory)，因此，在這裡我將會介紹一些基本的性質作為暖身，以方便我們進入到論文的世界中 :
* 說明，本篇文章的架構流程以 Stanford CS224W — Machine Learning with Graphs Lecture 2 to 3 課程設計為主體，其中我認為要補充的再額外補充。
圖結構與網絡
圖論在數學研究裡是很重要的一個領域，也是十分困難的研究方向，因此這邊我並不打算基於圖論進行太過深入的推理(對，實際上我也不會XD)，我要著重的是如何用圖論的方法表達人與人之間的關係，以及圖的各種性質與這些性質的潛在含意，首先我們看到下圖 :
基本上我們可以知道，以「你 (Ego)」為中心，會與不同人(上圖的節點，Vertex)產生連結(上圖的邊，Edge)，相似的人群之間又會構成群落(Community)，如上圖中紅色的代表高中好友，藍色代表一起修電腦科學的學生等等，這就是用圖來表達人與人之間的社交關係的方法。用數學的語言來看圖的話，通常我們可以這樣表達 :
1. 圖的表達方式 : G(V, E)；其中 G = Graph；V = Vertex 代表節點集合；E = Edge 代表邊集合； E ⊆ {(x, y) : (x, y) ∈ V^2, x ≠ y}；x, y 為邊的兩個端點2. 精準而言，以上的表達方式稱為無向圖(Undirected Graph)，也就是邊的兩端點互通，與之相對的有向圖(Directed Graph)則代表邊是有方向性的3. V, E 為有限集合，且 V ≠ ∅；但 E 可以 = ∅
圖論有許多種應用情境，有很多牽涉到關聯的數據都可以用圖的方式來表達，比如社交網路平台的好友關係、生物統計學元素之間的交互關係、流行病學中人與人之間的接觸關係等等。
當然，由於圖的多種可能性，根據其性質不同圖有許多種表達方法，比如 Bipartite Graph、Complete Graph、Directed Acyclic Graph 等等，我就不一一介紹，等到下方若有提及我再補充，對此有興趣的可以參考演算法筆記，對不同種類的圖有詳細介紹 :
此外在資料結構上，圖的表達可以很靈活，一樣詳細可以參考演算法筆記，但這邊只介紹幾種最常用的方式 :
【Edge List】
透過 List 的方式儲存每一個邊與邊的關係，舉例來說 :
這種儲存方式高效且比較不占空間，但相對來說會讓檢索變得比較麻煩。
【Adjacency List】
這種作法可能修過資料結構的人會比較懂，因此我這邊就不多說了。
【Adjacency Matrix】
雖然說犧牲了一些儲存空間，但容易檢索，且如果需要找出關鍵節點，比如可以通往所有其他地方的 Vertex，只要單列或單欄加總即可。
大部分來說紀錄方式都會是透過鄰接矩陣(Adjacency Matrix)的方法來實作，這樣的紀錄方式也頗為方便，如果想要更改人與人之間關係的權重(比如好友與普通同學的差異)，僅需要直接更改數值即可。此外，這樣的紀錄方法也便於我們找出孤立群體，也就是當我們將矩陣分解成小矩陣(線性代數第一堂課)的時候，如果能夠分割出零矩陣，那麼多半我們可以找出孤立群體，舉例來說 :
上圖中的 a 稱作 Disconnected Graph，b 當然就稱作 Connected Graph，由此可以衍生出不少性質，比如強連結(Strongly Connected Component)、關節點(Articulation Vertex)，一樣這邊不一一說明，感興趣的可以去演算法筆記挖寶，講解得十分完善。
此外，這邊也介紹一些圖(網絡，Networks)的幾種關鍵性質，在進行初始數據探索與分析時非常好用。
【一、Degree Distribution】
我們如果將每個節點連接的對象個數或權重加總，就可以得到每個節點連結了多少人或其重要性，這有助於我們快速發現群體之中的重要關鍵人物，或是在物流網路中的重要連結點，比如 :
【二、Shortest Path】
有時候，我們也想知道點與點之間的最短距離，這在物流上的應用當然就是最佳路徑，而在社交關係上的應用，通常也是用來找出人與人之間的距離並衍生一些相關分析。其中兩個點之間的 Diameter 被定義為兩點之間的最短路徑距離總和，通常我們對該數值以及其中會經過哪些點感興趣，找最短路徑有許多種方法，有學過演算法的讀者應該不難知道，如果一開始不知道圖的全貌，那麼這幾乎是一個 NP-Hard 問題，只要圖夠大那麼就不太可能在有限時間裡面找出最短路徑，但通常而言我們會知道圖的全貌，因此衍生出了許多種求解方法。詳細可參考 :
【三、Clustering Coefficient】
有時候我們也對一個節點到底與其他節點有多麼 "Connected" 感興趣，如果對於聚類算法(Clustering Algorithm)有些研究的讀者不難發現，這實際上就是一種如何定義聚類算法效能的方式。一般而言，定義一個點到底與多少個點連結是最簡單粗暴的辦法，但是很顯然，如果一個點連結的都是孤立成員，即使他連結數量再高，我們也很難說這個點與其他點關係緊密，因此，我們可以定義一個點的連結程度為 :
此時，我們就可以定義一個圖的連結程度為每個點的Clustering Coefficient的平均。此外，一般來說我們不會想要將整張圖拿來比較其Clustering Coefficient，因為這意義不大，而是將圖透過不同辦法，如聚類、BFS 找出幾種相近的子圖後，去比較各子圖之間的連接程度，尋找的辦法有很多種，我這邊也不一一介紹，如果有興趣一樣可以參考演算法筆記的內容。
以上的幾種性質怎麼應用呢 ? 以一個社交網站為例，我們可以用該些方式找出幾種重要問題的答案，比方說我們想知道群體中是否有幾種關鍵的意見領袖(Degree Distribution)、想知道不同群體之中人與人之間的平均距離與緊密程度(Shortest Path & Clustering Coefficient)等等，更比如透過現實網路的平均路徑分析，得出六度分隔理論等等(僅是設想，當初這東西實驗不是這樣做的XD)。
這邊分享一個維基百科很好玩的工具，可以讓你查詢兩個條目之間的最短距離，比如從「普世文化通則」到「鬼滅之刃」的最短路徑為 4。
[普世文化通則] => 禁忌
[禁忌] => 鬼
[鬼] => 鬼滅之刃
複雜網絡表達 Complex Network Representation
隨著資料傳遞的爆炸性增長，真實世界所形成的網絡也越來越複雜，這造成了兩個難題 : 一、真實世界到底是怎麼樣彼此相連接的；二、真實資料量級造成的成本令模擬研究變得十分困難。因此，研究者在圖論的基礎上，創造出了幾種可能的方法來構建模擬的網絡，一方面是方便後續的模擬研究，而不需每次都取得真實資料，二方面研究員們也想看看用怎樣的條件去進行模擬能夠更接近真實社會情況。
在這邊，我們介紹幾種模型 :
【一、Erdös-Renyi Random Graphs (ER隨機圖)】
ER 隨機圖的起始條件很簡單 : 一個擁有 N 個節點的圖，其每個邊(u, v)都會以一個獨立同分布產生出來的機率 p 生成，意思就是說在一個群體之中，每兩個人之間都有一樣多的機率彼此相關聯。ER 隨機圖有以下幾個性質 :
- Degree Distribution 為 Binomial
2. Clustering Coefficient 會等於 p
3. 兩點之間平均最短路徑以 log(n) 的速率增長
假設圖之間可以分成兩個子圖，S 與 V\S，兩子圖之間必然有零條以上的道路相連結，此時如果我們定義 :
定義這個東西做甚麼呢 ? 因為我們知道，如果一個擁有 N 個節點的圖裡面如果你隨便找出一對節點，那麼兩者之間一定有一條距離長度為 O(log(n)/α)的路徑，為甚麼呢 ? 因為 :
由上圖我們可以很明顯地看到，如果我們透過廣度優先搜尋，其實就能夠在對數時間內找到一條路徑，進行的模式是這樣的，首先我們先劃分出一個擁有 S 節點的子圖，那麼由於 α 有上限值的存在，最多我們僅需要搜索 α * S 條路徑就夠了，搜索完畢後，由於又搜尋到了一部分節點，我們進一步併攏成 S' 個節點的子圖，由此往下推送，隨著節點增長路徑搜索的難度僅會是對數時間增長。
以上就是 ER 隨機圖的性質，在早期的研究(約1960年代)中，大部分都是基於 ER 模型往下去做研究的，然而，隨著電腦網路發達，人們取得更多資料以後，大家也漸漸開始檢驗 ER 隨機圖到底與真實世界的情況是不是類似的。而答案想當然地是否定的，ER 隨機圖存在幾個問題 : 平均的 Degree 以及 Clustering Coefficient 都與真實世界相差太多，真實世界的節點關連性會更加稀疏，多半來說會形成一個一個的小社群，而 ER 隨機圖的定義中，每個人都有一樣的機會與在遙遠彼端的某個人連接上，這顯然是錯誤假設，因此，我們需要進一步拓展這個模型。
【二、Small World Model (小世界模型)】
真實世界的情況是怎麼樣的呢 ? 直覺來想就是一個一個的小圈圈，彼此高度緊密，即放到整體網絡，會發現大部分節點彼此並不相連，然而節點之間又往往僅需要少數幾步即可到達(如同上面提到的六度分隔理論)。也就是說，在上述的理論來看我們等同於想要一個 Clustering 程度很高，但 Diameter 很低的圖，這有點違反直覺因為通常來說，這兩個東西都是往同個方向移動的，當小社群越來越緊密時，平均跟整個社會中連結上的距離也就越長。
由上圖我們可以看到，一般我們想像中的都是如左邊或右邊的兩個極端，中間的圖是我們想要的，仔細觀察可以發現其實是在左邊 High Clustering 圖的基礎上，讓特定少數幾個點之間有跳躍性的連結，此時我們稱其為隨機捷徑(Random Shortcut)，這東西的存在使我們大幅降低了圖中的 Diameter。
也就是說，基於一般創建出來的隨機圖，從High Clustering/High Diameter出發，如果我們隨機賦予其中的幾個節點跳躍性的捷徑，那麼就可以快速降低整個圖的 Diameter，也就更貼近真實世界觀察到的結果。這樣的做法也通常被稱作 Watts Strogatz Model。
【三、Kronecker Graph Model (克羅內克圖模型)】
為了進一步逼近真實世界的情況，研究者們又引入了一個新的概念(也不是新概念，是老概念了只是第一次有人這麼用)，Kronecker Product (克羅內克積)，這東西的存在目的是為了生成真實世界的圖，如果讀者仔細回想一下剛才介紹的 Small World 模型，就會發現雖然 Small World 通過引入捷徑的方式改善了 ER 模型對於真實世界的表達能力不足的問題，卻還是沒有回答起始的 High Clustering, High Diameter 的圖應該怎麼生成，而 Kronecker 就在這個基礎之上去引進了一個想法，由於物體都會是與自身的某部分存在相近，也就是 Self-Similarity，如果我們已經有了一部分的圖，那就可以透過這種特性去生成下一部分。
首先，我們先來複習一下線性代數的一個基本觀念，Kronecker Product :
與傳統的矩陣相乘不同，克羅內克的相乘方法等於是把整個矩陣放大了相乘，力求兩個矩陣中的每一個元素都與彼此有相乘關係。那麼這東西要怎麼讓我們模擬一個真實世界的情況呢，假設我們一開始有一些真實資料，比方說是一個三乘三的矩陣，我們就可以透過 Kronecker 去遞迴相乘，如下 :
我們可以發現，不同的起始交互關係會影響遞迴運算後得到的圖結構，然而這裡出現一個問題，那就是按照這個方法進行下去的圖多半有著很強的規則性，但真實世界很顯然不可能有這種強規則性的存在，因此我們在這之上多引入一個隨機的概念，使其變成 Stochastic Kronecker Graph，他的概念也很簡單，初始引入的矩陣只要不是 0/1 矩陣就可以了，而是每個元素都是介於 0 到 1 之間的機率，在將其大於 0.5 的部分轉化為 1，小於的部分轉化為 0，就得到了一個隨機性的矩陣 :
這樣的作法能夠更貼近真實世界的情況(當然，可以視情況引入 Random Shortcut)，同時也很好地解決了資料的生成問題。
網絡結構分析與應用 Network Structural Analysis and Application
針對更加複雜的網絡當然也有更複雜的分析方法，當然一些比較經典的比如聚類算法等機器學習的演算法在這裡不會著墨太多，這邊只說明幾種基於圖論搜索、子圖拆解的分析方法，以及其在社會網絡分析中的可行應用。
【網絡圖形 Network Motifs】
如果把一個網絡分割成多個子圖(Subgraphs)，其中你總會看見某些區塊有著相似的連結方式，比如說某些部分可能是前饋的(Forward Feeding)，某些部份可能是循環的(Loops)。相似的形狀或說連結方式，通常代表著類似的運作機制，因此如何去辨別與分析圖形，可以幫助我們理解一個網絡中的運作模式，並理解在特定情況下如何去預測未來的模式。
現在的問題來了，圖形有這麼多種，比如說 :
以上兩種都是圖形，在一個網絡圖裡面你幾乎可以定義無限種圖形，但以分析的角度而言，我們總是需要知道哪一種圖形相對更重要一些，也就能幫助我們找出哪種類型的運作模式是比較有價值的。那麼怎麼去定義有價值呢? 如果在一個真實世界中出現頻率比較高的圖形，而且這個頻率明顯高過我們隨機產生的圖，很顯然這些圖形的價值就更高一些。
此時，我們怎麼去定義某個特定圖形(或是子圖，i)的重要性呢 ? 可以透過以下的標準化分數去定義他 :
Z分數越高，代表該圖的重要程度越高；此外，該圖在整個網絡中的相對重要性稱為 Network Significance Profile (SP)，定義為 :
由上述兩個定義，我們可以得出幾個結論，當給定幾種 Subgraph 的時候，我們就可以分別計算其 Z分數與 SP 分數，Z分數高的當然就代表這是重要的圖形，而SP分數通常與Z分數呈現同方向增加，代表在整個圖中的相對重要程度。
現在的問題來了，我們在一開始要怎麼樣找出這些圖形? 理論上圖形的數目隨著圖夠大，就可以有無限多種形式，假設有一個 Size K 的點集合，邊的構成數目就可以有 2^K 種；當然我們要扣掉一些同構的情況，意思是兩種產生出來的圖形是完全等價的(見下方參考連結)，但即使這樣要確定某一個圖形是否存在圖裡面，也是一個NP-完全問題，是非常難以計算的。
好在，現實中我們也往往不需要圖形的點數目過大，實用上的角度來說一個圖的節點數目通常是落在 3~8 個就很夠了，這樣來說我們就可以尋找圖形是否存在，這邊可以透過一個演算法稱為 ESU 算法，基本上分為兩部分 :
ESU (Exact Subgraph Enumeration) Algorithm : 1. 遍舉所有 Size = k 並且連通的子圖2. 透過圖同構檢驗，計算該子圖的出現次數
整個算法的概念是這樣的 : 首先從現有的一個子圖出發，最小單位當然就是任意節點 v，選擇一個備選節點 u 並加入圖形中，其中 u 要是最新加入的上一個節點的鄰居，且節點 id 必須比節點 v 還要大。
當然，按照傳統我們不能光說不練，以下是實作程式碼(以Adj.Matrix實作) :
上述的程式碼會印出所有 size = k 的圖形，因此，我們就可以根據需求決定 k 後，計算所有圖形的 Z 分數與 SP 分數，並最終得到我們的結論 : 從一個網絡之中，怎麼樣的運作模式是相對常見的。當然，上面的 ESU 演算法並沒有進行同構檢驗，因此我們需要另外將輸出的所有子圖檢視其是否有同構現象存在，如果有則進行排除。
如果數量小的話，當然我們肉眼觀察即可，數量級大的話，可採用 McKay’s nauty algorithm 進行檢驗，這邊僅附上參考連結，就不多談了。
【網絡中的結構性角色與分析 Structural roles and its Analysis in Networks】
接下來，我們來說明最後一個觀念。也就是結構性角色，角色(Roles)的概念是甚麼呢 ? 整個網絡中的每個 Node 都是一個最小單位，而其中每個單位所展現出來的結構性行為如果一致或類似，我們就說這些人有相似的角色，這樣的定義與群落、社群不同的是，角色是透過行為去定義的而非相似程度，舉例而言 :
上圖可以看出角色與群落的差別，群落也是很重要的分析一環，這個我在下一篇系列會提到，而角色代表的更多是相似功能的節點，比如同樣是關節點(Articulation Point，上圖紅點)等等；更精確的定義是，如果他們與其他點之間的連結關係類似，我們就會說這兩個點擁有相同的角色，而角色在直觀分析的角度也很容易理解，比方說我們希望找出的是社會中的關鍵意見人物、物流中的中轉站，或是我們也可以通過相似角色在不同社群間的定位來進行一些推理等等。
理解了角色的重要性以後，與圖形相同，我們需要想辦法將相似的角色找出來，這同樣也是一種無監督的學習方式，在這邊我們介紹一種算法 RoIX，這是一篇2011年提出的論文，用以抽取圖形中結構性角色，整體思路如下 :
來源 : https://web.eecs.umich.edu/~dkoutra/papers/12-kdd-recursiverole.pdf1. 起始由 Adjacency Matrix 出發2. 利用 Feature Extraction，即將每一個節點視為 Feature Vector，其中包含該 Node 連接的節點數量，其中包含的三角形數量等得出一個矩陣，得出一個 Node * Feature 矩陣 3. 透過低秩矩陣分解(如SVD, 譜分解皆可，不熟的快回去看線性代數)將其分解成 Node * Role 矩陣與 Role * Feature 矩陣 (需要預先定義分解後矩陣的 Size)，這步驟的目標是對 Feature 進行 Clustering，擁有相似 Feature 的 Node 就會擁有相同的角色(因為Feature代表其行為)4. 後續可以透過不同方式衡量模型的選擇成效(論文中使用 Minimum Description Length 方法，見下方連結)
後續我們也可以通過將不同 Roles 描繪出來的性質比較其相近程度(Affinity)，進一步對這些 Roles 彼此的相似程度進行研究。
整體而言，得到一個社交網絡後，我們可以透過 RoIX 分析去找出幾種關鍵角色，給予後續的分析方案一個好的研究方向。
結語
透過圖來描繪社交網絡實際上是一個大議題，後面還有更多分析可以實作，本篇作為一個起頭，介紹了一般而言圖的幾種性質，以及常見的分析，而後面更加複雜的分析則會作為單獨的文章慢慢寫出來。
以下也 Recap 一下這篇介紹的一些重點 :
一、背景介紹 : 如何透過圖來描述社交關係網絡 : 節點、邊與資料儲存方式，其中節點代表人或最小分析單位，邊代表兩單位之間的聯繫，可為 Binary 或權重二、網絡圖的性質 :
1. 透過 Degree Distribution 找出重要節點 : 物流中的關鍵中轉點、人群中的意見領袖等
2. 透過 Shortest Path 找出兩點之間最短距離 : 分析訊息傳遞、物流傳遞所需的最小路程
3. 透過 Clustering Coefficient 定義圖之間的聚合程度 : 了解不同群體之間的緊密程度與相似程度差異三、如何模擬真實世界網絡圖 : 從ER隨機圖、小世界模型到Kronecker Model四、網路結構分析與應用
1. 透過 ESU 演算法找出網絡中相似圖形與其重要性 : 代表某種特定運作模式在網絡中出現的頻繁程度
2. 透過 RoIX 演算法找出網絡中的結構性角色 : 找出網絡中的幾種重要角色
下一篇則會針對史丹佛的一篇論文去說明如何透過非負矩陣分解去找出網絡中的各式群落，以及這些群落代表的分析意涵。
