1.背景

在社交網絡、在線電商中，用戶之間或用戶與商家之間會想成網絡。例如，Twitter上用戶之間的follow，可以形成“who-rate-who”網絡；電商中用戶在商家下的購買和評論行為也是個巨大的網絡，“who-buy-who”,“who-rate-who”。

在這些巨大的網絡中，有些人在做著不光彩的事。

在Twitter、微博里，有些人為了提升自己或者一個話題的影響力，會購買轉發形成“虛假轉發“，也有人會購買“虛假跟隨者”；電商為了提高自己的銷量或聲譽，會花錢雇人虛假購買自己的產品，撰寫虛假的評論，造成”虛假交易“和”虛假評論“。

 今天介紹Alex Beutel 博士論文《User Behavior Modeling with Large-Scale Graph Analysis 》中的一個工作：CatchSync，其目的就是找到這些水軍。

2.CatchSync

事實上，這些異常行為在網絡中會體現為dense subgraph，成為網絡中的異常數據。

然而，正常用戶也會產生dense subgraph，因為正常人也可能進行扎堆轉發，扎堆購買的行為。這就導致了僅僅依靠的網絡結構無法準確的區分作弊者和正常人。

CatchSync就是一個不僅利用網絡結構，也利用網絡節點的上下文特征進行異常行為檢測的框架。

CatchSync檢測異常的出發點是異常行為的兩個特點：

1）一致性：異常的源節點會傾向于形成同步行為，即他們指向的目標節點之間具有相似性；

2）異常性：異常的源節點與大多數節點很不同，即他們指向的目標節點與一般節點較為不同。

那么在網絡中檢測異常行為的問題可以總結為如下：

已知：節點之間的連接圖

尋找：一組可疑的源節點（水軍），以及對應的目標節點（雇傭水軍的人）

為實現這個目標，首先從網絡中提取節點特征。實際上，基于圖的拓撲結構可以提取的特征很多，包括但不僅限于：

1）出度，入度

2）HITS得分

3）中介中心度

4）左右奇異向量的第i個元素值

文中使用了HITS模型中的authoritativeness和入度作為基本特征。從圖1中的左圖的直觀展示可以看出，異常源節點對應的目標節點分布的較為集中，而正常源節點對應的目標分布很分散。這正體現出了異常用戶的目標存在一致性。

有了可用的節點特征之后，下一步就是計算源節點（跟隨者）的正常性和一致性。首先定義如何計算兩個節點的v和v'之間的臨近程度：

很粗暴，這里怎么分Grid cell也沒細講。

接下來就可以利用這個臨近程度計算方法計算一致性和正常性了：

有了這兩個值后就可以畫出“正常性-一致性”的圖啦（圖1右側）。異常節點具有較高的一致性，較低的正常性。提取出這部分樣本的方法很多，文中使用的3δ。

圖1 X對應異常的節點，Y對應正常的節點。左側兩圖為authoritativeness-indegree圖，即原始特征空間圖；右側兩圖為normality-synchronicity圖，即用于判斷節點是否為異常的“正常性-一致性圖”。左側圖中X其指向的節點（target）分布較為集中，而Y指向的節點分布較為分散。右側圖中X集中在正常性低，而一致性高的部分。

3 效果

直接看在真實數據集上的實驗結果，數據是從twitter和騰訊微博收來的真實數據，場景是“跟隨”。其中OutRank是一個很出名的檢測網絡中異常的方法，SPOT是一種基于微博內容判斷是否異常的方法。

表1 CatchSync及其他方法的識別精度（不知道什么條件下統計的 - -！）

圖2 在Twitter和騰訊微博上的PR曲線對比。

4 總結

優點：

1.不需要參數，不依賴其他的特征；

2.直觀好理解。

局限性：

1.在實際應用中僅僅依靠網絡的拓撲結構往往難以達到要求，文中也提到跟基于內容的方法相結合能夠取得更好的結果，在應用中可以考慮在計算正常性和一致性時多考慮些額外的信息。再擴展開，文中的正常性和一致性的計算方法未必是最優和普適的，可以擴展出有很多方法來。