大家好，我是愛生活，AI風控的小伍哥，今天給大家?guī)淼谝黄恼拢P于圖異常檢測的。

一、概? ?述

基于圖的異常檢測分為孤立點檢測和異常群簇檢測，本文是孤立點檢測中較經(jīng)典的論文，通過研究Ego-net總結幾種異常模型及提供度量方式：

異常結構	含義	度量方式?
CliqueStar	呈星狀或者團狀結構	邊數(shù)~節(jié)點鄰居數(shù)
HeavyVicinity	總邊權重異常大	總邊權重~邊數(shù)
DominantPair	存在某條權重異常大的邊	主特征值~總邊權重

文章調(diào)查了Ego-net中存在的異常模式，并給出了檢測異常模式的依據(jù)基于上述模式，提出了OddBall，一種用于異常點檢測的無監(jiān)督方法，將OddBall應用于真實數(shù)據(jù)集，并驗證了算法的有效性

論文名稱：OddBall: Spotting Anomalies in Weighted Graphs

論文地址：http://www.cs.cmu.edu/~mmcgloho/pubs/pakdd10.pdf

代碼地址：https://www.andrew.cmu.edu/user/lakoglu/pubs.html#code

二、Ego-net（中心節(jié)點）

以中心節(jié)點(ego)及其鄰居組成的子圖，一般用于研究個體性質(zhì)以及局部社區(qū)發(fā)現(xiàn)，本文僅考慮一階鄰居，這是為了減少計算量并提和高可解釋性。

三、Ego-net模式及度量方法

1 、CliqueStar（基于密度）

基于密度的方法可以識別出下面兩種Ego-net的異常結構：

Near-Star：在正常的社交網(wǎng)絡中，我們通常認為朋友之間可能會相互認識，因此一階Ego-net中的鄰居之間沒有任何關聯(lián)是非常可疑的，近似星型，鄰居之間很少聯(lián)系（如通話關系網(wǎng)絡中的中介、電催人員、營銷號碼，他們大量的聯(lián)系別人，然而聯(lián)系人中之間幾乎沒啥聯(lián)系），這種結構的Ego-net被稱為star，如下圖所示，中心節(jié)點與大量節(jié)點存在關聯(lián)，但是鄰居之間無聯(lián)系或者聯(lián)系很少。

Near-Clique：與上述相反，鄰居之間存在大量關聯(lián)也是非常可疑的，這種結構的Ego-net被稱為cliques。正如下圖所示，中心節(jié)點與大量節(jié)點存在關聯(lián)，鄰居之間的聯(lián)系非常密集，近似環(huán)狀，鄰居之間聯(lián)系緊密（如某個討論組、恐怖組織）。

度量方法：邊數(shù)～鄰居數(shù)

如下圖所示，可以看出大多數(shù)節(jié)點Ego-net中邊數(shù) E 與鄰居數(shù) N 服從冪律分布（對數(shù)坐標后呈線性）、給定某節(jié)點i對應的 Ei 、Ni ，求出冪律系數(shù)?α?，若：

α?接近1（黑色虛線），節(jié)點i的Ego-net呈現(xiàn)Near-Clique?

α 接近2（藍色虛線），節(jié)點i的Ego-net呈現(xiàn)Near-Star

紅線是擬合中位數(shù)，藍色和黑色虛線是邊界線。

大多數(shù)Graph都遵循該模式：

2、HeavyVicinity(權重)

HeavyVicinity指“較重的鄰居“，Ego-net中邊數(shù)一定時，總邊權重異常大（如騙貸者通過頻繁撥打電話偽造通話記錄），中心節(jié)點與一小部分節(jié)點之間存在權重非常大的關聯(lián)也是可疑的，如騙貸者通過頻繁撥打電話偽造通話記錄。正如下圖所示，中心節(jié)點與少部分節(jié)點之間的連接權重非常大。