OddBall: Spotting Anomalies in Weighted Graphs
目标：在带权图中发现异常点
几种异常情况：
（1）Near-star（上方的是一个toy sketch，下方的是在真实数据集的情况）
红色节点为异常节点，可以看到它的neighbor节点互相之间的连接非常少（按理说，朋友的朋友有比较多一部分也应该互相是朋友）。
（2）Near-clique
红色节点为异常节点，它的neighbor之间的连接太多了。
（3）Heavy vicinities
假设节点i与n个不同的neighbor相连，我们希望与节点i有关的边的总权重是与n有关的函数。如果总权重过大，那么认为节点i是异常的。
（4）Dominant edge
红色节点为异常节点，它和1-step neighbor之间有一条heavy link。
Proposed Method
definition
当focus on一个节点时，我们称之为ego。
节点i的k-step-neighborhood，指的是所有关于节点i的k-step-away nodes组成的集合。所有这些节点的connections组成的图称为induced sub-graph。
一个节点的1-step neighborhood称为它的egonet。
一般k取一个较小的值，本文推荐取k=1，本文后面的描述也是基于k=1的。
Feature Extraction
文中列出了几个比较好的feature：
•Ni：ego i的neighbors数(degree)
•Ei：egonet i的边数
•Wi：egonet i的所有权重之和
•λw,i：egonet i的带权邻接矩阵的主特征值（绝对值最大的特征值）
在不同场景下比较好的特征组合。
•E和N：CliqueStar：发现near-cliques and stars（对应前面图片的1，2）
•W和E：HeavyVicinity：发现recurrences of interactions（对应前面的图片3）
•λw,i和W：DominantPair：发现strongly connected pair（对应前面的图片4）
Laws and Observations
文中表述了normal neighborhoods应该具有的特点。
G表示图，i∈V(G)表示节点，Gi表示节点i的egonet。
Observation 1(EDPL: Egonet Density Power Law)
与near-cliques and stars相关
Gi中的nodes数量Ni和边数量Ei满足
在本文的实验中，α一般在1.10到1.66之间。α=1与stars相关，α=2与cliques相关。
Observation 2(EWPL: Egonet Weight Power Law)
与recurrences of interactions相关
Gi中的所有权重和Wi与边数量Ei满足
在本文的实验中，β一般能到达1.29。β越大表示越异常。
Observation 3 (ELWPL: Egonet λw,i Power Law)
与strongly connected pair相关
Gi的带权邻接矩阵的主特征值λw,i和权重之和Wi满足
在本文的实验中，γ一般在0.53到0.98之间。γ=0.5表示均匀的权重分布，γ接近1表示在egonet中有dominant heavy edge。如果egonet中只有一条边，则γ=1.
Observation 4(ERPL: Egonet Rank Power Law)
Gi的rank Ri,j和边j的权重Wi,j满足
其中Ri,j表示对边按权重进行排序后边j的rank。ERPL表明egonet中的边权分布应该是一个偏态分布(skewed distribution)。直觉上的理解就是，以friendship network为例，一个人有很多不是那么close 的朋友(light links)，但只有比较少的close friends(heavy links)。
当ERPL成立时，EWPL也会成立。
写的正式一些有引理如下：
ERPL暗含了EWPL。也就是，如果
则有
其中Gi是一个egonet，它的所有权重和为Wi，它所有的边总数为Ei，ω i表示带权边的有序集合，Wi,j表示边j的权重，Ri,j表示Wi,j在集合ω i中的rank（从大到小排）。
证明如下：
先证明θ<-1时有β>1
再证明-1≤θ≤0时有β=1
综上得证。
Anomaly Detection
我们可以利用上面的几个observation来做异常检测，因为异常点在这几个方面会表现的和normal pattern不一样。
对于节点i，有特征xi和yi，构成了特征pair f(x,y)。对于f(x,y)，有幂律方程y=Cx^θ 。定义节点i的out-line score为
yi为实际值，y为fitting line上的期望值。
out-line(i)反应了节点i偏离fitting line的程度。
最小的out-line(i)为0，此时yi=Cxi^θ
但是上面的方法对于一类的异常节点没有办法检测到：那些靠近fitting line但是离大多数节点很远的点，这些点通常发生在x和y值很大的时候。
我们希望也能检测到这样的异常节点，于是考虑和另一种基于密度的异常检测方法相结合。本文使用了LOF，计算出节点i的out-lof(i)。计算最后的score方法为两者归一化（除以最大值）求和，即out-score(i)=out-line(i)+out-lof(i).
Python3实现
https://github.com/gloooryyt/oddball_py3
喜欢的话记得给我点个小星星~
网友评论