基於社交網路分析演算法（SNA）的反欺詐（二）

關於SNA基礎知識和指標，可參看本系列文章《基於社交網路分析演算法（SNA）的反欺詐（一）》，本文主要講SNA演算法。

演算法一：PageRank演算法

PageRank演算法用一句古文來講，就是「近朱者赤，近墨者黑」，也就是被高質量網頁引用的網頁也是高質量網頁，或者被用戶訪問越多的網頁可能質量越高。我們在大學寫論文投期刊的時候，也會看到類似的數字，比如：期刊的影響因子、被引用次數。影響因子和被引用次數越高，表示這個期刊越好，如果被這樣的期刊錄用，也表示你的學術水平得到了極大的認可。再比如，相信每個支付寶用戶都受到過芝麻信用的善意提醒：多結交信用度高的朋友，有助於提高自己的芝麻分，也是一樣的道理。《黑鏡》第三季第一集便是把信用評分社會誇張到極致，也是對社交網路的一種詮釋。

PageRank演算法被廣泛用於搜索引擎結果排序，而為了抵禦Spam，各搜索引擎採用的排名演算法實際上是保密的，PageRank的具體計算方法也不盡相同。這裡，我只講一種最簡單，但也可以揭示PageRank本質的演算法——基於頁面鏈接屬性的PageRank演算法。

背景假設：

（1） 全世界只有4個網頁，ABCD，我們講每個網頁抽象成一個節點；

（2） 如果頁面A有鏈接指向B，我們就認為有一條從A到B的有向邊；

（3） 假設一個用戶停留在某一頁面時，跳轉到頁面上每個鏈接的概率是相等的；

那麼，假設我們根據以上背景，繪製了這4個網頁的關係圖，如下：

我們定義這個一個矩陣，其第i行j列第值表示用戶從頁面j跳轉到i的概率，並將其命名為轉移矩陣（transition Matrix）。那麼，我們繪製上圖的轉移矩陣M，如下：

為了計算每個網頁的rank值，我們先初始化各頁面值，令其相等。在這個例子中，也就是ABCD都是1/4。那麼，建立rank值的初始向量v：

那麼，一個用戶來到這個網頁，隨機點開網頁，會使四個頁面的rank值更改至如下：

第二個人來，再次點擊，會再次更改rank為MMv，如此這般不斷迭代，最終rank值會不斷收斂到某個設定的閾值，得到的值就是整個頁面的PageRank值。再這個例子中，大約收斂到（A，B，C，D）T=（1/4，1/4，1/5，1/4）T。

實際應用中，網頁外鏈到其他網頁的概率並不相同，或者可能停留在此頁面，可以增加一個阻尼因子（a）表示用戶停留當前頁面不鏈接到其他頁面的概率。

演算法二：社區發現演算法

社區發現演算法的思路就是在複雜網路中發現連接緊密的節點簇（社區結構），與聚類的思路如出一轍。發現這些社區結構的方式有很多中，本文主要介紹幾種簡單但常用的演算法：GN演算法，Louvain演算法，LPA演算法和SLPA演算法。

2.1 GN（Girvan-Newman）演算法

GN演算法是一個最經典的社區發現演算法，屬於分裂的層次聚類演算法（自上而下）。因最初由Michelle

Girvan和Mark Newman提出而得名。GN演算法的基本思想是不斷刪除網路中具有相對於所有源節點的最大邊介數的邊，然後，再重新計算網路中剩餘的邊的相對於所有源節點的邊介數，重複這個過程，直到網路中所有的邊都被刪除。怎麼理解呢？通過介數的定義我們知道，介數是多少個節點對必須經過本節點實現最小跳數互達的值，而介數高的邊必然要比介數低的邊更可能是社區之間的邊（兩個社區中的節點之間的最短路徑都要經過那些社區之間的邊，所以它們的介數會很高）。為了方便理解，可以參看下圖，方塊節點和圓形節點的最短路徑，必然要經過邊AB，因此邊AB的介數最大，拆除這條邊，就可以將其分成1#和2#兩個團體了，或者稱之為兩個社區。

然而，雖然GN演算法的準確率很高，但是計算量大，時間複雜度也很高。

2.2 Louvain演算法

Louvain可以理解成GN的逆過程，GN的思路是不斷拆邊，類似於自上而下的層次聚類。而Louvain則是不斷凝聚，類似於自下而上的層次聚類。為了理解Louvain演算法的過程，我們先來學習一個社區評價指標——模塊度。

模塊度（Modularity）用來衡量一個社區的劃分是不是相對比較好的結果。一個相對好的結果在社區內部的節點相似度較高，而在社區外部節點的相似度較低。

設Avw為網路的鄰接矩陣的一個元素，定義為：

假設cv和cw分別表示點v和點w所在的兩個社區，社區內部的邊數和網路中總邊數的比例：

函數δ(cv,cw)的取值定義為：如果v和w在一個社區，即cv=cw，則為 1，否則為 0。m

為網路中邊的總數。

模塊度的大小定義為社區內部的總邊數和網路中總邊數的比例減去一個期望值，該期望值是將網路設定為隨機網路時同樣的社區分配所形成的社區內部的總邊數和網路中總邊數的比例的大小，於是模塊度Q為：

其中kv表示點v的度。

在進行每次劃分的時候計算Q值，Q取值最大的時候則是此網路較理想的劃分。Q值的範圍在0-1之間，Q值越大說明網路劃分的社區結構準確度越高，在實際的網路分析中，Q值的最高點一般出現在0.3-0.7之間。

好，介紹完模塊度，我們就可以開始使用Louvain演算法了。首先，我們把每一個節點當作一個獨立的社區，假如我們把V1和V2加入到i都會使其模塊度增加， 我們比較兩者的數值，選擇增量較大的一個加入到i社區中。如此這般反覆迭代，直到模塊度Q的值不再增加為止。

3.3 LPA（Label Propagation Algorithm）

LPA演算法的穩定性不是很好，但優點是可擴展性強，時間複雜度接近線性，且可以控制迭代次數來劃分節點類別，不需要預先給定社區數量，適合處理大規模複雜網路。LPA的計算步驟也十分簡單：

第一步：為所有節點指定一個唯一標籤；

第二步：刷新標籤：對於某一個節點，考察其所有鄰居節點的標籤，並進行統計，將出現個數最多的那個標籤賦給當前節點（如果最多的標籤不唯一，隨機選擇一個）；

第三步：重複步驟二，直到收斂為止。

3.4 SLPA （Speaker-listener Label Propagation Algorithm）

SLPA是一種改進的LPA，是一種重疊社區發現演算法，其中涉及一個重要的閾值參數r。通過對r的適當選取，可將其退化為非重疊型。

SLPA中引入了listener和speaker兩個比較形象的概念。可以這麼理解：在刷新節點的過程中，我們將要被刷新的節點定義為listener，其臨近節點就是它的speaker，speaker通常不止一個，在眾多speaker七嘴八舌時，listener該聽誰的呢？這時我們就要制定一個規則。

在LPA中，我們以出險次數最多的標籤來做決斷，這其實就是一種規則。只不過在SLPA框架里，規則的選取方式多由用戶指定（通常結合業務邏輯和場景決定）。

與LPA相比，SLPA最大的特點在於它不是僅僅的刷新替代原標籤，而是記錄每一個節點在刷新迭代過程中的歷史標籤序列（例如迭代T此，則每一個節點將保留一個長度為T的序列，見上面著名的手繪圖）。當迭代停止時，對每一個節點歷史標籤序列中各標籤出現的頻率做統計，按照某一個給定的閾值過濾掉那些出現概率小的標籤，剩下的標籤為該節點的標籤（通常有多個）。

PS: SLPA後來被作者改名為GANXiS

引申閱讀，目前已有的社區發現演算法及複雜度：

感謝作者張洋：http://blog.jobbole.com/23286/

感謝作者八刀一閃：https://www.jianshu.com/p/44c4206979a6

感謝作者皮果提：http://blog.csdn.net/cleverlzc/article/details/39494957

推薦閱讀：