基于社交网络分析算法（SNA）的反欺诈（二）

关于SNA基础知识和指标，可参看本系列文章《基于社交网络分析算法（SNA）的反欺诈（一）》，本文主要讲SNA算法。

算法一：PageRank算法

PageRank算法用一句古文来讲，就是“近朱者赤，近墨者黑”，也就是被高质量网页引用的网页也是高质量网页，或者被用户访问越多的网页可能质量越高。我们在大学写论文投期刊的时候，也会看到类似的数字，比如：期刊的影响因子、被引用次数。影响因子和被引用次数越高，表示这个期刊越好，如果被这样的期刊录用，也表示你的学术水平得到了极大的认可。再比如，相信每个支付宝用户都受到过芝麻信用的善意提醒：多结交信用度高的朋友，有助于提高自己的芝麻分，也是一样的道理。《黑镜》第三季第一集便是把信用评分社会夸张到极致，也是对社交网络的一种诠释。

PageRank算法被广泛用于搜索引擎结果排序，而为了抵御Spam，各搜索引擎采用的排名算法实际上是保密的，PageRank的具体计算方法也不尽相同。这里，我只讲一种最简单，但也可以揭示PageRank本质的算法——基于页面链接属性的PageRank算法。

背景假设：

（1） 全世界只有4个网页，ABCD，我们讲每个网页抽象成一个节点；

（2） 如果页面A有链接指向B，我们就认为有一条从A到B的有向边；

（3） 假设一个用户停留在某一页面时，跳转到页面上每个链接的概率是相等的；

那么，假设我们根据以上背景，绘制了这4个网页的关系图，如下：

我们定义这个一个矩阵，其第i行j列第值表示用户从页面j跳转到i的概率，并将其命名为转移矩阵（transition Matrix）。那么，我们绘制上图的转移矩阵M，如下：

为了计算每个网页的rank值，我们先初始化各页面值，令其相等。在这个例子中，也就是ABCD都是1/4。那么，建立rank值的初始向量v：

那么，一个用户来到这个网页，随机点开网页，会使四个页面的rank值更改至如下：

第二个人来，再次点击，会再次更改rank为MMv，如此这般不断迭代，最终rank值会不断收敛到某个设定的阈值，得到的值就是整个页面的PageRank值。再这个例子中，大约收敛到（A，B，C，D）T=（1/4，1/4，1/5，1/4）T。

实际应用中，网页外链到其他网页的概率并不相同，或者可能停留在此页面，可以增加一个阻尼因子（a）表示用户停留当前页面不链接到其他页面的概率。

算法二：社区发现算法

社区发现算法的思路就是在复杂网络中发现连接紧密的节点簇（社区结构），与聚类的思路如出一辙。发现这些社区结构的方式有很多中，本文主要介绍几种简单但常用的算法：GN算法，Louvain算法，LPA算法和SLPA算法。

2.1 GN（Girvan-Newman）算法

GN算法是一个最经典的社区发现算法，属于分裂的层次聚类算法（自上而下）。因最初由Michelle Girvan和Mark Newman提出而得名。GN算法的基本思想是不断删除网络中具有相对于所有源节点的最大边介数的边，然后，再重新计算网络中剩余的边的相对于所有源节点的边介数，重复这个过程，直到网络中所有的边都被删除。怎么理解呢？通过介数的定义我们知道，介数是多少个节点对必须经过本节点实现最小跳数互达的值，而介数高的边必然要比介数低的边更可能是社区之间的边（两个社区中的节点之间的最短路径都要经过那些社区之间的边，所以它们的介数会很高）。为了方便理解，可以参看下图，方块节点和圆形节点的最短路径，必然要经过边AB，因此边AB的介数最大，拆除这条边，就可以将其分成1#和2#两个团体了，或者称之为两个社区。

然而，虽然GN算法的准确率很高，但是计算量大，时间复杂度也很高。

2.2 Louvain算法

Louvain可以理解成GN的逆过程，GN的思路是不断拆边，类似于自上而下的层次聚类。而Louvain则是不断凝聚，类似于自下而上的层次聚类。为了理解Louvain算法的过程，我们先来学习一个社区评价指标——模块度。

模块度（Modularity）用来衡量一个社区的划分是不是相对比较好的结果。一个相对好的结果在社区内部的节点相似度较高，而在社区外部节点的相似度较低。

设Avw为网络的邻接矩阵的一个元素，定义为：

假设cv和cw分别表示点v和点w所在的两个社区，社区内部的边数和网络中总边数的比例：

函数δ(cv,cw)的取值定义为：如果v和w在一个社区，即cv=cw，则为 1，否则为 0。m为网络中边的总数。

模块度的大小定义为社区内部的总边数和网络中总边数的比例减去一个期望值，该期望值是将网络设定为随机网络时同样的社区分配所形成的社区内部的总边数和网络中总边数的比例的大小，于是模块度Q为：

其中kv表示点v的度。

在进行每次划分的时候计算Q值，Q取值最大的时候则是此网路较理想的划分。Q值的范围在0-1之间，Q值越大说明网络划分的社区结构准确度越高，在实际的网络分析中，Q值的最高点一般出现在0.3-0.7之间。

好，介绍完模块度，我们就可以开始使用Louvain算法了。首先，我们把每一个节点当作一个独立的社区，假如我们把V1和V2加入到i都会使其模块度增加， 我们比较两者的数值，选择增量较大的一个加入到i社区中。如此这般反复迭代，直到模块度Q的值不再增加为止。

3.3 LPA（Label Propagation Algorithm）

LPA算法的稳定性不是很好，但优点是可扩展性强，时间复杂度接近线性，且可以控制迭代次数来划分节点类别，不需要预先给定社区数量，适合处理大规模复杂网络。LPA的计算步骤也十分简单：

第一步：为所有节点指定一个唯一标签；

第二步：刷新标签：对于某一个节点，考察其所有邻居节点的标签，并进行统计，将出现个数最多的那个标签赋给当前节点（如果最多的标签不唯一，随机选择一个）；

第三步：重复步骤二，直到收敛为止。

3.4 SLPA （Speaker-listener Label Propagation Algorithm）

SLPA是一种改进的LPA，是一种重叠社区发现算法，其中涉及一个重要的阈值参数r。通过对r的适当选取，可将其退化为非重叠型。

SLPA算法思路

SLPA中引入了listener和speaker两个比较形象的概念。可以这么理解：在刷新节点的过程中，我们将要被刷新的节点定义为listener，其临近节点就是它的speaker，speaker通常不止一个，在众多speaker七嘴八舌时，listener该听谁的呢？这时我们就要制定一个规则。

在LPA中，我们以出险次数最多的标签来做决断，这其实就是一种规则。只不过在SLPA框架里，规则的选取方式多由用户指定（通常结合业务逻辑和场景决定）。

与LPA相比，SLPA最大的特点在于它不是仅仅的刷新替代原标签，而是记录每一个节点在刷新迭代过程中的历史标签序列（例如迭代T此，则每一个节点将保留一个长度为T的序列，见上面著名的手绘图）。当迭代停止时，对每一个节点历史标签序列中各标签出现的频率做统计，按照某一个给定的阈值过滤掉那些出现概率小的标签，剩下的标签为该节点的标签（通常有多个）。

PS: SLPA后来被作者改名为GANXiS

引申阅读，目前已有的社区发现算法及复杂度：

来源|知乎

作者|DataVisor黄姐姐

感谢作者张扬、八刀一闪、皮果提

想获知更多关于互金反欺诈的深度内容，欢迎参加黄姐姐的公开课

点击阅读原文，即可报名

更多精彩，戳这里：