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

05-01

社交網路分析演算法並不新鮮，且已經廣泛應用於社交人物影響力計算、好友和商品推薦、社交圈子分析等領域。近幾年，社交網路分析演算法的應用不斷拓展，已經開始應用於各種金融和保險等反欺詐領域，且效果很好。

為了講解基於SNA的反欺詐，我先簡單介紹下SNA的原理。為了方便理解，我會直接忽略很多細節（例如：入度和出度的概念），以下內容都是為了有助於理解反欺詐建模，想了解SNA更系統的知識請參看其他材料。

#基礎知識#

節點（Vertice）和邊（Edge）

社交網路，顧名思義，就是表現人和人之間關係的網路。類似的，社交網路分析演算法，也就是為了研究節點（可以理解成人）和節點關係（邊，可以理解成人和人之間的關係）的演算法。通過對關係的研究，可以對節點關係做梳理，從而聚成團。

為了方便對下文指標的理解，我們定義節點數 N = |V|, 邊數 M = |E|

圖（Graph），有向圖，無向圖

用邊把節點連接起來形成的網路，稱為圖（Graph）。圖又可以分成無向圖和有向圖，如下圖所示：

無向圖僅表示節點和節點之間是否有關係，例如：在P2P行業反欺詐建模中，我們通過申請者通訊錄去獲取其社會關係，例如，如果張三和李四的通訊錄都有老賴王五，那麼，張三和李四的貸款申請違約風險就會比較高。

有向圖相比於無向圖會攜帶方向信息，一個最簡單的例子就是傳銷圖。傳銷有非常成熟的上下線制度，是發展團隊十分迅速有效的手法，也被互聯網公司廣泛用於發展用戶——好友邀請制度，此外，保險銷售公司也有類似的提成機制。如被不法分子利用規則，對互聯網公司，產生的後果就是大規模虛假註冊；對保險銷售公司，產生的後果就是內外勾結騙取額外提成。

社區（Community），非重疊社區，重疊社區

社區可以理解成UML中的群組，也就是同一個社區中節點和節點關係緊密，而社區和社區之間關係稀疏。

如果任意兩個社區的節點集合的交集為空則被稱為非重疊社區，否則稱為重疊社區。

派系（Clique），完全子圖

派系是指任意兩個點都相連的節點的集合，又稱為完全子圖。

#分析指標#

指標一：度

簡單來講，度就是指從你這個節點發散出去了多少條邊，或者可以理解成你有多少個朋友。

指標二：度中心性

我們在每個節點上都標註上其度的值大小，如下圖所示：

我們接下來做標準化處理，用度除以最大連接可能（N-1），則得到：

形象地講，中心性指越高，表示與你有聯繫的人越多，或者說，你的社交人物影響力就大。這是一個社交網站分析用戶行為時一個常用的指標。

指標三：集中度（Centrality）

集中度表示一個群體的緊密程度，或者可以理解成密度。集中度又可以分為度集中度，緊密集中度和介數集中度，還有圖集中度、特徵向量集中度等，以下我們主要介紹前三種。

3.1 度集中度（Degree centrality）

度量集中度的方式有很多，例如，基尼係數、標準差和Freeman集中度公式。以下，我們以Freeman集中度通用公式為例計算：

其中，v*指度最大的節點。

根據上述公式計算如下兩圖的度集中度：

3.2 緊密集中度（Closeness centrality）

依賴於從一個結點出發到其它所有結點的最短路徑長度，並被定義為總長度的倒數。

節點i的緊密中心如下所示：

而通常我們講緊密中心度，是指其標準化形式，也即總距離長除以(N-1)

3.3 介數集中度（betweenness centrality）

直觀理解，介數就是多少個節點對必須經過本節點實現最小跳數互達。定義如下：

其中，gjk表示節點jk最短路徑的個數，gjk(i)表示i位於最短路徑的個數。

同樣，我們將其標準化，除以除本節點外其他節點對個數，得到：

還是以下面兩圖作為示例來計算介數集中度：

A在(B,C),(B,D),(B,E),(B,F),(C,D),(C,E),(C,F),(D,E),(D,F),(E,F)十個節點對的最短路徑上，非標準化值為10；

BCDEF不在任何節點對的最短路徑上，所以非標準化值為0。

簡單解釋一下：

對於節點A和E，都不在任何節點對的最短路徑上，所以為0；

對於節點B，在（A,C）,(A,D)和(A,E)三個節點對最短路徑上，非標準化值為3。類似地，節點D與B情況相同，也為3；

對於節點C，在（A,D）,(A,E),(B,D)和（B,E）四個節點對最短路徑上，非標準化值為4。

感謝作者mryqu：http://blog.sina.com.cn/s/blog_72ef7bea0102v748.html

感謝作者du00cs: http://blog.sina.com.cn/s/blog_439371b501012lgt.html

感謝作者fionaplanet：http://www.cnblogs.com/fionacai/p/6262527.html

Centrality定義：維基百科https://en.wikipedia.org/wiki/Centrality