graph

先介绍下金融借贷业务流程：用户前来申请借贷，会先经过欺诈识别，把欺诈团伙和主观欺诈的个人拒绝掉，然后对通过的人做信用评估，最后根据额度模型，算出利润最大化时放款金额。

刚才提到了团队欺诈，举个真实的例子。某头部互金公司在他们的财报中公布的，他们被一个团伙成功撸走了2000多单，当时这个公司的件均4w， 一下损失了8000w！！

那么如何防范这种风险呢。这就是今天要分享的图算法。图可以将这些一个个有良好记录的个体关联起来,一网打尽。

再举一些团伙欺诈的行为。比如一个团伙，注册真实的淘宝商家，然后刷出良好的淘宝购物记录。或者来回转账，刷出良好的银行流水。

Graph简介

$G = (V, E)$

• V:vertex set

• E:edge set (有向，无向，有权重和没有权重)

• 度中心性（Degree Centrality） - 表示连接到某节点的边数。在有向图中，我们可以有2个度中心性度量：流入和流出。一个节点的节点度越大就意味着该节点在网络中就越重要。

• 接近中心性（Closeness Centrality） - 从某节点到所有其他节点的最短路径的平均长度。反映在网络中某一节点与其他节点之间的接近程度。

• 介中心性（Betweenness Centrality） - 某节点在多少对节点的最短路径上。介数中心性是比较能体现节点在图中桥梁作用的中心性度量方法。介数反映了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。例如，在交通网络中，介数较高的道路拥挤的概率很大；在电力网络中，介数较高的输电线路和节点容易发生危险。

社团发现算法一般有：

• 最小割， 正则化割:通过计算图的最小割，即将网络划分为预定的分组数，并使连接各分组的边的条数最少。

• 非负矩阵分解:基本原理是将原始矩阵分解得到社区指示矩阵和基矩阵

• 基于模块度的社区划分

• 基于节点相似性的社区划分

https://github.com/benedekrozemberczki/awesome-community-detection

最小割算法广泛应用在分布式计算的负载均衡中，对集群节点的分组有利于减少不相关节点之间的通信。然而由于该算法限定了网络最终分组的个数，而不能通过算法“发现”节点间的内在联系并自然地构成若干个社区，因此最小割算法应用较为局限。

本文主要分享这两类的主要算法，基于模块度的 louvain和基于信息熵infomap，基于相似度的node2vec

模块度(Modularity)公式及简化

它的取值范围是 [−1/2,1)

优化目标：一般认为社团内部的点之间的连接相对稠密，而不同社团的点之间的连接相对稀疏。

所以模块度也可以理解是社区内部边的权重减去所有与社区节点相连的边的权重和，对无向图更好理解，即社区内部边的度数（内部的连线数）减去社区内节点的总度数。

\begin{align} Q &= \frac { 1 } { 2 m } \sum _ { i , j } \left[ A _ { i j } - \frac { k _ { i } k _ { j } } { 2 m } \right] \delta \left( c _ { i } , c _ { j } \right) \\ &= \frac { 1 } { 2 m } \left[ \sum _ { i , j } A _ { i j } - \frac { \sum _ { i } k _ { i } \sum _ { j } k _ { j } k _ { j } } { 2 m } \right] \delta \left( c _ { i } , c _ { j } \right) \\ &= \frac { 1 } { 2 m } \sum _ { c } \left[ \sum_{in} - \frac { ( \sum_{tot}) ^ { 2 } } { 2 m } \right] \\ &= \sum _ { c } \left[ \frac { \sum_{in} } { 2 m } - \left( \frac { \sum_{tot} } { 2 m } \right) ^ { 2 } \right] \\ &= \sum _ { a } \left[ e _ { c } - a _ { c } ^ { 2 } \right] \end{align}

$\delta ( u , v ) = \left\{ \begin{array} { l } { \text { 1when } u = = v } \\ { 0 \text { else } } \end{array} \right.$

模块度公式的解释

$A_{ij}$节点i和节点j之间边的权重，网络不是带权图时，所有边的权重可以看做是1；

$k_i = \sum A_{ ij}$表示所有与节点i相连的边的权重之和（度数）；

$c_i$表示节点i所属的社区；

$m=\frac{1}{2} \sum_{ i , j } A_{ ij }$表示所有边的权重之和（边的数目）。

其中$\Sigma in$表示社区c内的边的权重之和，$\Sigma tot$表示与社区c内的节点相连的边的权重之和，即社区c节点的度之和（包含与其他社区相连边的度）。

从概率的角度去看：

$e_{c}$表示实际情况下，c社区内产生边的概率。

$a_{c} ^ {2}$表示在一种理想情况下，给定任意节点i的的度ki，对节点i和节点j进行随机连边，边属于社区c的概率期望。

于是上式就表示了社区内连边数与随机期望的一个差值。连边数比随机期望值越高，表明社区划分的越好。

一般使用后面简化的公式，简化后的公式删除了判断两个节点是否划为同一个社区的函数，所以在一定程度上大大减少了Q值计算量。

Louvain

Louvain算法的思想很简单：

1. 将图中的每个节点看成一个独立的社区，此时社区的数目与节点个数相同；

2. 对每个节点i，依次尝试把节点i分配到其每个邻居节点所在的社区，计算分配前与分配后的模块度变化$\Delta Q$，并记录$\Delta Q$最大的那个邻居节点，如果$\max \Delta Q > 0$，则把节点i分配$\Delta Q$最大的那个邻居节点所在的社区，否则保持不变；
3. 重复2，直到所有节点的所属社区不再变化；

4. 对图进行压缩，将所有在同一个社区的节点压缩成一个新节点，社区内节点之间的边的权重转化为新节点的环的权重，社区间的边权重转化为新节点间的边权重，然后重复2，3；

5. 重复2~4，直到整个图的模块度不再发生变化。

第一阶段称为Modularity Optimization，主要是将每个节点划分到与其邻接的节点所在的社区中，以使得模块度的值不断变大；

第二阶段称为Community Aggregation，主要是将第一步划分出来的社区聚合成为一个点，即根据上一步生成的社区结构重新构造网络。重复以上的过程，直到网络中的结构不再改变为止。

移动

$Q _ { 1 } = \left[ \frac { E _ { c } } { m } - \left( \frac { \sum t o t } { 2 m } \right) ^ { 2 } \right] + \left[ \frac { o } { m } - \left( \frac { k _ { i } } { 2 m } \right) ^ { 2 } \right]$

$Q_{ 2 } = \frac { E _ { c } + E _ { i , c } } { m } - \left( \frac { \sum t o t + k _ { i } } { 2 m } \right) ^ { 2 }$

\begin{align} \Delta Q &= Q_{2} - Q_{1} \\ &= \left[ \frac { \sum _ { i n } + k _ { i , i n } } { 2 m } - \left( \frac { \sum _ { t o t } + k _ { i } } { 2 m } \right) ^ { 2 } \right] - \left[ \frac { \sum _ { i n } } { 2 m } - \left( \frac { \sum _ { t o t } } { 2 m } \right) ^ { 2 } - \left( \frac { k _ { i } } { 2 m } \right) ^ { 2 } \right] \\ & = \left[ \frac { k _ { i , i n } } { 2 m } - \frac { \sum _ { t o t } k _ { i } } { 2 m ^ { 2 } } \right] \end{align}

$k_{i,in}$是社区c内节点与节点i的边权重之和，再乘以2

前面部分表示把节点i加入到社区c后的模块度，后一部分是节点i作为一个独立社区和社区c的模块度

模块度与Louvain社区发现算法

Spark GraphX分布式图计算实战

实时的louvain

louvain算法是一个处理静态数据的算法，需要图已经生成好了， 但是一般业务中，不断的会有新的订单、新的用户、新的数据进来，对应到图就是不断的增加新的节点和边。

那么每次图新加入顶点或者边，都重新计算louvain算法的话需要巨大的计算量，于是我们根据局部模块度的思路，获取局部相关的顶点和边，顶点的社区和各个社区成员信息，来计算优化模块度的值。

基于个体稳定度博弈的动态社区发现算法研究

http://www.doc88.com/p-6991331093268.html 基于spark streaming的动态社区发现及其在个性化推荐应用中的研究

http://www.doc88.com/p-9146960189736.html 一种基于局部模块度的增量式动态社区发现算法

http://www.doc88.com/p-1055432963471.html 基于标签传播的实时社区发现算法研究

https://wenku.baidu.com/view/fa65268159eef8c75fbfb3a6.html?re=view 图流合璧——基于Spark Streaming和GraphX的动态图计算

infomap

从信息论的角度出发，假设一个random worker 在图上进行随机游走，那么怎么用最少的编码长度来表示其路径呢？

如果节点存在社区结构，那么社区内的节点就可以共享社区的bit位码，可以得到更小的平均比特, 所以社区划分的越好，那么表示任意一条随机游走的路径所需的平均比特就越小。

如果我们能够计算出每个节点的到达概率，就可以依据信息熵的公式来量化平均比特了： $L ( P ) = H ( P ) \equiv - \sum _ { \alpha } p _ { \alpha } \log p _ { \alpha }$

怎么计算每个点的到达概率呢？

一个暴力的办法是在图上进行长时间的随机游走，最后统计每个节点的出现概率。?? 太暴力了。

利用pagerank思路，初始化了每个节点的到达概率之后，就可以不断地迭代更新每个节点的到达概率，这个结果会很快趋于收敛。

其实这过程就是一个马尔科夫随机过程，随机初始化起始值，然后随机游走就相当于不停地用概率转移矩阵相乘，最后就可以达到马尔科夫稳态。

把随机游走事件归为三类：进入某个社团，离开某个社团，再社团内部游走。

定义清楚各类事件的发生概率，依据信息熵公式，就可以得到此时编码所需的平均比特了,其本质就是从信息论的角度出发。

$L(\mathrm{M})=q_{\curvearrowright} H(\mathcal{Q})+\sum_{i=1}^{m} p_{\circlearrowright}^{i} H\left(\mathcal{P}^{i}\right)$

Infomap算法的迭代过程

1. 初始化，对每个节点都视作独立的社区；

2. while 平均比特的值不再下降；

3. 对图里的节点随机采样出一个序列，按顺序依次尝试将每个节点赋给邻居节点所在的社区，取平均比特下降最大时的社区赋给该节点，如果没有下降，该节点的社区不变。

参考链接

The map equation

https://mp.weixin.qq.com/s/qUxMesQA-edSyHeudQRRGA

DEEP GRAPH INFOMAX 阅读笔记

Graph embeddings

Deepwalk

1. 使用随机游走(RandomWalk)的方式在图中进行节点采样获得节点共关系，

2. 使用skip-gram，根据步骤1中生成的节点序列学习每个节点的向量表示。skip-gram就是根据给定输入的节点，预测上下文节点。

Deepwalk有多不足，比如泛化能力，有新节点加入时，它必须重新训练模型以表示该节点。

其中一个就是采样，从其邻居中随机采样节点作为下一个访问节点，是一种可重复访问已访问节点的深度优先遍历算法。

node2vec是一种综合考虑DFS邻域和BFS邻域的graph embedding方法

node2vec

优化目标：$\max \limits_{f} \sum_{u\in{V}}{\log{Pr(N_S(u)|f(u))}}$

条件独立假设： $Pr(N_S(u)|f(u)) = \prod_{n_i\in{N_S(u)}}{Pr(n_i|f(u))}$

特征空间的对称性：$Pr(n_i|f(u)) = \frac{\exp(f(n_i)\cdot{f(u)})}{\sum_{v\in{V}}{\exp(f(v)\cdot{f(u)})}}$

优化目标：$\max \limits_{f} \sum_{u\in{V]}}{[-\log{Z_u+\sum_{n_i\in{N_S(u)}}{f(n_i)\cdot{f(u)}}]}}$

$Z_u=\sum_{u\in{V}}{\exp(f(u)\cdot{f(v)})}$ 计算量非常大，所以论文采用负采样(negative sample)进行近似计算。

这个node2vec优化目标函数，因为它跟大名鼎鼎的word2vec是一样。

我们最初是用一个Python写的包，跑一遍算需要一周。后来想，既然优化目标是一样的，那能不能用word2vec包，因为word2vec用c写的，而且还采用了 Hierarchical Softmax，negative sampling加速。

然后在网上找到了一个套用word2vec实现的node2vec包，速度快很多。

随机游走的方式

复杂网络处理的任务其实离不开两种特性，前面也提到过：一种是同质性，就是之前所说的社区。一种就是结构相似性，值得注意的是，结构相似的两个点未必相连，可以是相距很远的两个节点。

能不能改进DeepWalk中随机游走的方式，使它综合DFS和BFS的特性呢？所以本文引入了两个参数用来控制随机游走产生的方式。

$P(c_i=x|c_{i-1}=v) = \begin{cases} \frac{\alpha_{pq}(t,x)\cdot{w_{vx}}}{Z}& \text{if(v,x)}\in{E} \\ 0& \text{otherwise} \end{cases}$

$\alpha_{pq}(t,x) = \begin{cases} \frac{1}{p}& \text{if } d_{tx}=0 \\ 1& \text{if } d_{tx}=1\\ \frac{1}{q}& \text{if } d_{tx}=2 \end{cases}$

Z是分子的归一化常数

如果已经采样了 (t,v) ，也就是说现在停留在节点v上，那么下一个要采样的节点x是哪个？作者定义了一个概率分布，也就是一个节点到它的不同邻居的转移概率：

直观的解释一下这个分布：

• 如果t与x相等，那么采样x的概率为 $\frac{1}{p}$ ；
• 如果t与x相连，那么采样x的概率1；

• 如果t与x不相连，那么采样x概率为 $\frac{1}{q}$

参数p、q的意义分别如下：

返回概率p：

• 如果 p>max(q,1) ，那么采样会尽量不往回走，对应上图的情况，就是下一个节点不太可能是上一个访问的节点t。

• 如果 p<min(q,1) ，那么采样会更倾向于返回上一个节点，这样就会一直在起始点周围某些节点来回转来转去。

出入参数q：

• 如果 q>1 ，那么游走会倾向于在起始点周围的节点之间跑，可以反映出一个节点的BFS特性。

• 如果 q<1 ，那么游走会倾向于往远处跑，反映出DFS特性。

• 当p=1，q=1时，游走方式就等同于DeepWalk中的随机游走。

简而言之：

参数p控制重复访问刚刚访问过的顶点的概率，

参数q控制着游走是向外还是向内，若q>1，随机游走倾向于访问和t接近的顶点(偏向BFS)。若q<1，倾向于访问远离t的顶点(偏向DFS)。

缺点

1. 慢

2. 先embedding再聚类，感觉这两个过程很割裂！！ 融合一下

3. 它是对采出很多序列，并不是真正的在图上建模

node2vec是根据图的关系进行采样后，所以它只学习了图的结构信息。但是正常业务中会拥有很多节点的特征信息，比如用户的标签，那么怎么融合到学习过程中，最后embedding出更好的结果。

可以用GCN。

comE

Graph Embedding 得到向量后，可以做很多事情，在我们这个主题可以简单的通过聚类来讲节点分组。

但是这个过程比较割裂，先优化node2vec，然后再优化聚类。能不能整体上一次性优化完呢。

comE这个算法优化目标中加入了社区的检测和嵌入。我们可以借鉴它的思路。

它通过一个混合高斯模型将节点划分开。

优化目标中前面两项跟LINE定义的相似度相似：

https://blog.csdn.net/u012151283/article/details/87013915

Learning Community Embedding with Community Detection and Node Embedding on Graphs

https://github.com/vwz/ComE Learning Community Embedding with Community Detection and Node Embedding on Graphs

http://sentic.net/community-embedding.pdf

其他评价指标

标准化互信息NMI(Normalized Mutual Information)

$\mathrm { NMI } ( U , V ) = \frac { \operatorname { MI } [ U , V ) } { \sqrt { H ( U ) H ( V ) } }$

\begin{align} \operatorname { MI } ( U , V ) &= \sum _ { i = 1 } ^ { | U | } \sum _ { j = 1 } ^ { | V | } P ( i , j ) \log \left( \frac { P ( i , j ) } { P ( i ) P ^ { \prime } ( j ) } \right) \\ &= \sum _ { i = 1 } ^ { | U | } \sum _ { j = 1 } ^ { | V | } \frac { \left| U _ { i } \cap V _ { j } \right| } { N } \log \left( \frac { N \left| U _ { i } \cap V _ { j } \right| } { \left| U _ { i } \right| \left| V _ { j } \right| } \right) \end{align}

假设对于N个样本点的两种标签划分为U 和 V. 熵为划分集的不准确性

$H ( U ) = - \sum _ { i = 1 } ^ { | U | } P ( i ) \log ( P ( i ) )$

$H ( V ) = - \sum _ { j = 1 } ^ { | V | } P ^ { \prime } ( j ) \log \left( P ^ { \prime } ( j ) \right)$

$P ( i ) = \left| U _ { i } \right| / N$ 表示任取一个样本划分为$U_i$的概率

$P ^ { \prime } ( j ) = \left| V _ { j } \right| / N$

参考佳文

图模型在欺诈检测应用一点看法

深度学习时代的图模型，清华发文综述图网络

社区发现(Community Detection)算法

社区发现算法FastUnfolding的GraphX实现

重叠社区发现 LFM simrank ， COPRA算法 FRAUDAR算法

谱聚类（spectral clustering）原理总结

https://blog.csdn.net/DreamHome_S/article/details/78167267 社团划分结果评估指标：Q、ARI、NMI

https://mp.weixin.qq.com/s/XkGJhQ5nRda4ruV7DtdJpw 论文解读：从乌合之众到群体智慧的一步之遥

https://yq.aliyun.com/articles/294450 2017CIKM－Network Embedding专题论文分享

https://www.jianshu.com/p/a9a2ed8b98be

https://arxiv.org/pdf/1607.00653.pdf

https://zhuanlan.zhihu.com/p/30599602 node2vec

基于PageRank的复杂网络社区发现

Modularity的计算方法——社团检测中模块度计算公式详解

社区发现算法 - Fast Unfolding（Louvian）算法初探

论文 | 蚂蚁金服亮相数据挖掘顶会KDD 2018，这些你不可错过！

图中节点的介数中心性算法

[Graph] 图节点的重要性 ( Network Centrality ) 分析

基于社区的动态网络节点介数中心度更新算法