大家好，我是愛生活，AI風(fēng)控的小伍哥，今天給大家?guī)?lái)第一篇文章，關(guān)于圖異常檢測(cè)的。

一、概? ?述

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

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

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

論文名稱：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é)點(diǎn)）

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

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

1 、CliqueStar（基于密度）

基于密度的方法可以識(shí)別出下面兩種Ego-net的異常結(jié)構(gòu)：

Near-Star：在正常的社交網(wǎng)絡(luò)中，我們通常認(rèn)為朋友之間可能會(huì)相互認(rèn)識(shí)，因此一階Ego-net中的鄰居之間沒有任何關(guān)聯(lián)是非?？梢傻模菩切?，鄰居之間很少聯(lián)系（如通話關(guān)系網(wǎng)絡(luò)中的中介、電催人員、營(yíng)銷號(hào)碼，他們大量的聯(lián)系別人，然而聯(lián)系人中之間幾乎沒啥聯(lián)系），這種結(jié)構(gòu)的Ego-net被稱為star，如下圖所示，中心節(jié)點(diǎn)與大量節(jié)點(diǎn)存在關(guān)聯(lián)，但是鄰居之間無(wú)聯(lián)系或者聯(lián)系很少。

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

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

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

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

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

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

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

2、HeavyVicinity(權(quán)重)

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

度量方法：總邊權(quán)重～邊數(shù)

大多數(shù)節(jié)點(diǎn)Ego-net中總邊權(quán)重～邊數(shù)也服從冪律分布（對(duì)數(shù)坐標(biāo)），?β?越高表示越異常

圖（a）選舉中，民主黨（DNC）的大量的資金給為數(shù)不多的候選者

3 、DominantPair（主導(dǎo)邊）

Dominant heavy links指“主導(dǎo)的邊”，Ego-Net中存在某條邊權(quán)重異常大（如學(xué)者投稿會(huì)議網(wǎng)絡(luò)中，“Toshio Fukuda” 擁有115篇papers，投稿了17個(gè)會(huì)議，但其中87篇pager投稿了一個(gè)ICRA）：

度量方法：主特征值～總權(quán)重

大多數(shù)節(jié)點(diǎn)Ego-net對(duì)應(yīng)帶權(quán)鄰接矩陣中主特征值(principal eigenvalue，即最大特征值)～總邊權(quán)重也服從冪律分布，其中系數(shù) λ 表示Ego-net中邊權(quán)均勻分布，?λ 接近1表示存在DominantPair的情況。