在这篇SynchroTrap欺诈检测算法代码实操示例文章中，我们通过 SynchroTrap思想构建了商户评价用户的同步行为关系，接下来用社区发现算法LPA对这些行为进行打标，将其划分成不同属性的社区(群体)。
一、LPA算法应用示例
1. 电商评价同步行为示例数据group
如第一行 x∩y 代表用户 BUY_01 和 BUY_02 在
同一个小时内对同一商户进行评价的情况有 2 次，即他们出现同步行为的次数为 2 。
2. 将同步行为数据转化成图
由于 LPA 的算法输入为图，需要将其转换成图形式
import matplotlib.pyplot as plt
import networkx as nx
tuples = [tuple(x) for x in group[['Buy_x','Buy_y','x∩y']].values]
G = nx.Graph()
G.add_weighted_edges_from(tuples)
pos=nx.spring_layout(G)
nx.draw_networkx(G,pos)
示例样本量太少，不易作社区划分，手工添加多个社区节点
G.add_edge('BUY_04','BUY_05',weight=2)
G.add_edge('BUY_05','BUY_06',weight=1)
G.add_edge('BUY_05','BUY_07',weight=2)
G.add_edge('BUY_06','BUY_08',weight=1)
G.add_edge('BUY_07','BUY_08',weight=3)
G.add_edge('BUY_08','BUY_09',weight=1)
G.add_edge('BUY_08','BUY_10',weight=4)
G.add_edge('BUY_09','BUY_11',weight=2)
pos=nx.spring_layout(G)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx(G,pos)
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)3. 使用 LPA 算法划分社区
使用同步行为出现的次数即 x∩y 值作为输入权重
from networkx.algorithms.community import asyn_lpa_communities as lpa
com = list(lpa(G,'weight'))
print('社区数量',len(com)) 4. 对划分的社区进行业务打标
算法将用户分成了三个社区，可以将每个社区中的用户的明细数据拉取出来，观察他们的行为特征。比如对于同一社区的用户，观察他们的评级时间密集程度如何，评价商户有没有集中性，评论相似性，所用设备环境是否正常或者有共性等，基于业务考虑对社区进行打标，如人肉刷评群体。
二、LPA算法介绍
LPA全称Label Propagation Algorithm，即标签传递算法，属于图聚类算法，社区发现算法中比较简单易懂的一种。
1. 核心思想
近朱者赤，节点属于哪个社区由它的邻居节点投票决定。邻居节点属于哪个社区的投票数目最多，它就属于哪个社区，如果最大票数中多个社区持平，则随机选择一个，达到物以类聚的效果。
2. 计算流程
标签初始化：初始状态下，每个节点将自己的编号作为标签（标签就是指节点所在社区的编号）。
标签传播：每个节点向其邻居（图中边另一头的节点）传播自己的标签，即告诉邻居自己是属于哪个社区的。
标签更新：每个节点根据其邻居的标签，选择重复数最多的那个标签作为自己的标签，即哪个社区包含其最多的邻居，它也算到该社区。如果多个社区包含的邻居数相同且最高，则随机选取其中一个社区。
- 如果节点更新后的标签发生了变化则回到第2步，否则该节点进入非激活状态，即收敛状态。循环该过程，直到图中所有节点都进入收敛状态。需要注意的是，进入非激活状态的节点，如果在收到其邻居的消息后，标签发生了变化，其将再次进入激活状态，重新开始标签传播。
3. 算法优化
随机性的问题很容易导致算法不收敛，对于同一个数据集可能每次跑的解决都不太一样。一方面更新顺序是随机的（中心节点不好找），另外选择节点所属社区也是可能是随机的。比如在如下图中算法可能会将1、4、5、8分在一个社区，2、3、6、7分在另一个社区，显示不符合直观预期。
改善的方式比如当有多个标签出现次数相同且最高时，将收敛条件改为只要节点所属的社区是邻居节点最大数目之一的就行，就认为迭代完成。
再比如将随机选取调整为取标签的最小值作为所在社区（当然选择最大的也可以），如某个节点多次循环标签为“1,2,1,1,2,1…”，我们就选择1作为它的社区，从而停止对它的迭代。
4. 相关论文
Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks
题图来源：网站Pexels
THE END
阅读原文
声明：文中观点不代表本站立场。本文传送门：https://eyangzhen.com/239526.html
