【2013/ICDM】On Anomalous Hotspot Discovery in Graph Streams

文章链接：http://charuaggarwal.net/ICDM-hotspot.pdf

TL;DR

文章中提出了一种在网络流图中检测出异常的hotspots的方法，设计了一个localized principal component analysisi（PCA） algorithm. 使用快速的增量特征向量更新算法来维持局部相关信息。

Algorithm/Model

利用$G(t)=(N(t), A(t))$表示一个时序网络，$N(t)$ 和$A(t)$ 表示$t$ 时刻的$nodes$和$edges$，$n^t_{ij}$表示边$(i,j)$出现的次数，$T(i,j,1)...(T,i,j,n^t_{ij})$表示边$(i,j)$出现的时间戳。文章中处理的是无向图，但是在我们项目中估计要作为有向图处理。

首先定义$t$时刻边$(i,j)$上加权的频率如下：

$$F(i, j, t)=\sum_{k=1}^{n_{i j}^{t}} 2^{-\lambda \cdot(t-T(i, j, k))}$$

当边上的频率发生突然变化时，那么可能发生异常。

显然只有这部分是不够的。由于文章中的定义太多，就不详细写了，只关注我需要的部分。

$t$时刻节点$i$局部特征定义：$S(i,t)=\left\{j_{1}^{i}(t) \ldots j_{ | S(i, t)}^{i}\right\}$，由直接与节点$i$有边相连的节点组成。Decay-based product matrix$M(i, t)$定义如下：

$$M(i,t)=|S(i, t)| \times|S(i, t)|=S(i,t)^{T}S(i,t)$$

设$\overline{W(i,t)}, \alpha (i,t)$表示$M(i,t)$最大的特征向量及其对应的特征值，那么activity correlation change定义为：

$$C(t_1, t_2)=1-\overline{W(i,t_1)} \cdot \overline{W(i,t_1)}$$

Activity Magnitude change 定义如下：

$$\gamma (i, t_1, t_2)=1-\overline{\alpha (i,t_1)} \cdot \overline{\alpha (i,t_1)}$$

Experiment Detail

Thoughts

文中提出的算法对于计算graph之间的change有一定启发，但是整体定义偏多实验较少，质量一般。

联系作者