图算法练手 by networkx part1
- 2020 年 5 月 11 日
- AI
下面提到的图算法除了一般意义上的算法，还包括了基于图数据的一些统计指标，例如度，中心性等等。
才疏学浅，关于图算法的高级应用，比如用图神经网络来做欺诈检测这类的应用没怎么接触过，目前接触过的，所了解的，主要是以规则为主，图算法在其中扮演的角色偏辅助，通过节点的pagerank值来查找活跃用户，或者使用社区发现来找到关联紧密，并且关联用户很大的社区等等，通过这些方式首先找到非正常的用户（在金融领域中，异常活跃往往意味着风险；在金融领域中，较少存在非常大的社区结构等），然后对这些用户进行一些eda，比如在薅羊毛的问题中，看看这类用户的平均获取的羊毛数量，例如用户获得的积分总额，用户获取的红包总额等等。 简而言之，目前所接触到的所谓的反欺诈比较初阶，图算法只是作为业务的辅助应用。
下面介绍的算法主要来自于：
1、《智能风控》；
2、《Network Science with Python and NetworkX Quick Start Guide 》；
3、O’Reilly 系列的《Graph Algorithms》
然后算法的分类，感觉按照networkx的官方文档的分类方法还是比较准确全面的。注意，networkx2.X和1.X版本的差异蛮多的，所以还是看2.0的官方文档吧：
networkx.algorithms.community.kclique.k_clique_communities – NetworkX 2.4 documentation
当然，不可能一个一个去研究所有的图算法，只会挑其中比较热门的、常提到的、业务中可能会用到的一些算法进行学习或分享，而这个挑选的过程就是参照上面给的三份材料来的。
pandas的格式要处理成这样的，左边是source节点右边是target节点，value是权重，其它的属性可以以列的形式添加，这是以edge形式存储的图数据的表格形式，其实通过join或者merge的方法很容易构造出这样的数据集。这也给普通的表格数据转图数据提供了一个较好的范例；
首先，最基本的，计算节点的度：
nx.degree(G) 
如果是有向图，则：
G=nx.from_pandas_edgelist(edge_list,edge_attr='weight',create_using=nx.DiGraph)
plt.figure(figsize=(15,10))
nx.draw(G,with_labels=True,
edge_color='grey',
node_color='pink',
node_size = 50,
font_size = 14,
pos=nx.spring_layout(G,k=0.2))
如果要计算其出度于入度则：
所有的度：
可以发现有向图的nodes的degree都增加了一倍，因为把出入都算进去了，如果是无向图则出入度不重复计算（也就没有出入度的概念了）
如果要实现带权则：
计算degree的时候把nodes的属性中的某个属性指定为weight，带权图的权重作为nodes的属性之一进行设计。
有向带权图也是一样的，非常简单；
这样我们就能很方便的得到每一个样本的度了，然后我们将其转化为dict：
dict(G.out_degree())
再使用map就可以直接将每个样本的度对应到原始的dataframe里去了：
对于中小型数据来说，这种处理方式非常的简单容易上手了。
前面提到了图数据的特征抽取方法之一——度，这种方法的问题在于没有考虑到节点的领节点的具体信息，举个例子，例如微博，我们如果简单的通过明星-粉丝的网络结构，计算明星的degree，则显然计算结果会受到“买粉”问题影响严重，明星的粉丝水分非常严重，但是degree的计算方式并不考虑明星的粉丝号的具体的数据情况，单纯的根据连接明星的边来计算其度，那么如何处理，明星的机器人粉一般都是非常不活跃的用户，永远都是给明星点赞转发，除此之外再也没有任何的其它的社交行为发生，因此，这类僵尸粉的活跃度是非常低的，这也意味着僵尸粉本身可能基本上没什么粉丝或者粉丝数量稀少，那么这种情况下，我们可以通过改进的eigenvector。
eigenvector的思路很简单，一个活跃的用户（中心度强），不仅仅体现在其朋友多，他的朋友也应该是活跃的，因此节点B的中心都定义为：
B=Wa*A+Wc*C+beta
这里我们假设B的邻节点只有A和C，W对应的连接的边的权重，如果无权则默认为1，beta是随机初始化的值。max_iter是迭代次数，tol是收敛的判断标准，nstart可用于自定义初始权重，weight用于指定边的权重。
然后和上述操作一样可以合并到原始的特征矩阵中。
不过eigenvector也存在问题，比如卖粉公司，这些垃圾公司有几百万个虚拟的微博账户，专门给买粉的人点赞，虽然eigenvector计算出来这些买粉的人的中心都都会较低，但是架不住人多，这个时候我们就可以用上pagerank了。
pagerank的原理可见上，这里举个例子很好理解：
pagerank和eigenvector一样随机为每个node初始化一个值，然后迭代到收敛，以上图这个有向图为例，B仅仅指向C节点，而A指向B和C节点，因此：
pagerank（C）=alpha * （1/2*pagerank(A)+1*pagerank(B)）+beta
其中beta是随机初始化的值，pagerank()表示这个节点的pagerank值用于衡量nodes的热门程度，alpha表示整个迭代过程中的所谓阻尼系数；
因为A指向了2个节点，所以A的贡献度应该是减半的。当然，以上面的偶像微博的例子为例，一个僵尸粉给一大堆明星点赞的话，那么使用pagerank可以较好的得到明星的真实的热门程度，说老实话，如果微博公开了它的原始的数据，明星的真实热门水平甚至是真实的粉丝数会被扒得一干二净。
谷歌当初发明pagerank主要是针对有向图的，但是networkx也可以针对无向图，具体的做法就是把无向图当作双向图，从而进行计算，以上面的A、B、C为例，假设上图为无向图，则计算公式为：
pagerank（C）=alpha * （1/2*pagerank(A)+1/2*pagerank(B)）+beta
把无向当双向，则适用于有向图的算法可以非常简单迅速的移植到无向图上来。
import networkx as nx
nx.pagerank(G,alpha=0.9) 
上述三种方法都是从近邻节点的角度来描述节点的中心度的，除此之外还可以通过最短路径的方式来定义节点的中心度：
已经有大佬解释过了~，
如何简单地理解中心度，什么是closeness、betweenness和degree？
这里直接用代码验证一下：
G = nx.Graph() # 创建无(双)向图
edges=[('A','B'),('B','C'),('C','D')]
G.add_edges_from(edges)
plt.figure(figsize=(15,15))
pos=nx.shell_layout(G)
nx.draw(G,pos,with_labels=True)
所以原理很简单，就是计算图G上的所有路径的数量之和，然后某个节点的betweeness中心度就是经过G的路径的数量除以总的路径数量，至于路径总数的计算可以使用深度或者广度优先的方式来计算得到，至于networkx是如何计算的不太清楚，也不重要，不复杂，数据结构与算法得复习复习了。。。//www.cnblogs.com/DWVictor/p/10048554.html
补充，betweeness意味着在中间，也就是节点必须在至少两个节点之间才算是这个节点的路径，例如上图的A不再任意两个节点之间，因此其betweeness的计算结果为0，因为没有最短路径；
原理也很简单，以A为例，A和B、C、D都通过不同长度的路径建立了连接，则A的closeness为 （连接节点数）/连接路径长度之和。
关于上述算法在有无向、有无权的不同类型的图上的计算差异其实是非常好理解的，感兴趣的可以用demo自己跑一下就知道结果了，这里就不废话了。
除此之外，还可以通过jaccard相似性来度量节点的一度关联的相似性，公式也很简单
jaccard(a,b)=U(a)交U(b)/U(a)并U(b)，U表示取节点的一阶邻节点，交表示交集，并表示并集：
还是以上面的demo为例：
a和c节点的共同邻节是B，数量为1，A和B的所有邻节点的交集为(B,D)，因此其jaccard相似性为1/2=0.5.
这里主要介绍了一些比较常用且简单的计算中心度和相似性的图算法，注意，上述介绍的算法主要的作用常作为特征的抽取工具，不直接支持决策，也可以作为一种辅助分析的手段。
后面继续介绍更复杂一些的图算法，例如经典的社区发现 标签传播 等，至于一些相对新的反欺诈类型的算法，不知道有没有demo。。。图神经网络等这两个月忙好了慢慢整理应用代码。
补充：
G = nx.Graph() # 创建无(双)向图
edges=[('A','B'),('B','C'),('C','D'),('A','C')]
G.add_edges_from(edges)
plt.figure(figsize=(15,15))
pos=nx.shell_layout(G)
nx.draw(G,pos,with_labels=True)
triangles = nx.triangles(G)
sorted(triangles.items(), key=lambda x:x[1], reverse=True)[0:10]
节点所在三角形的数量，也是一个常看到的基于图数据的统计特征；
还有一个是聚类系数
三角计数（Triangle Count）和聚类系数（Clustering Coefficient）经常被一起使用。三角计数计算图中由节点组成的三角形的数量，要求任意两个节点间有边（关系）连接。聚类系数算法的目标是测量一个组的聚类紧密程度。该算法计算网络中三角形的数量，与可能的关系的比率。聚类系数为 1 表示这个组内任意两个节点之间有边相连。
有两种聚类系数：局部聚类系数（Local Clustering Coefficient）和全局聚类系数（Global Clustering Coefficient）。
局部聚类系数计算一个节点的邻居之间的紧密程度，计算时需要三角计数。计算公式：
其中，
u代表我们需要计算聚类系数的节点，R(u)代表经过节点u和它的邻居的三角形个数，k(u)代表节点u的度。下图是三三角计数聚类系数计算示意图：
clustering = nx.clustering(G)
clustering
以点A为例，点A所在三角形个数为1，点A的度为2（和B、C互相连接），因此按照公式点A的局部聚类系数为 1，其它点计算结果也是一样一样的。
全局聚类系数是局部聚类系数的归一化求和。我们计算出所有nodes的局部聚类系数之后做归一化即可。
当需要计算一个组的稳定性或者聚类系数时，我们可以使用三角计数。三角计数在社交网络分析中有广泛的应用，通航被用来检测社区。聚类系数可以快速评估特定组或整个网络的内聚性。这些算法可以共同用于特定网络结构的寻找。例如，探索网页的主题结构，基于网页之间的相互联系，检测拥有共同主题的 “网页社群”。
