LPA社区发现算法介绍和代码示例

在这篇SynchroTrap欺诈检测算法代码实操示例文章中,我们通过 SynchroTrap思想构建了商户评价用户的同步行为关系,接下来用社区发现算法LPA对这些行为进行打标,将其划分成不同属性的社区(群体)。

一、LPA算法应用示例1. 电商评价同步行为示例数据group如第一行 x∩y 代表用户 BUY_01 和 BUY_02 在同一个小时内对同一商户进行评价的情况有 2 次,即他们出现同步行为的次数为 2 。

图片

这里同步行为次数是基于商户(约束条件)去重作统计的,即A和B对同一个商家Y在不同时间段有多次匹配行为时,只算作一次。我们也可以考虑不对商家作去重处理,不过需要注意的是在杰斯卡相似度计算过程用到的x_cnt等指标逻辑也要保持一致,要么都去重,要么都不去重,我在这块处理上也搞错过。如果采用不去重法得到的应是:

图片

2. 将同步行为数据转化成图

  • 由于 LPA 的算法输入为图,需要将其转换成图形式
import matplotlib.pyplot as pltimport networkx as nxtuples = [tuple(x) for x in group[['Buy_x','Buy_y','x∩y']].values] ##x∩y为weightG = nx.Graph() ##本次采用无向图,对应有DiGraph, MultiGraph, MultiDiGraph等画图选项G.add_weighted_edges_from(tuples) ##如果是二元组,使用add_edges_from;weight另外定义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# LPA本身不稳定,会存在波动com = list(lpa(G,'weight')) #seedprint('社区数量',len(com))
图片
图片

4. 对划分的社区进行业务打标算法将用户分成了三个社区,可以将每个社区中的用户的明细数据拉取出来,观察他们的行为特征。比如对于同一社区的用户,观察他们的评级时间密集程度如何,评价商户有没有集中性,评论相似性,所用设备环境是否正常或者有共性等,基于业务考虑对社区进行打标,如人肉刷评群体。

二、LPA算法介绍

LPA全称Label Propagation Algorithm,即标签传递算法,属于图聚类算法,社区发现算法中比较简单易懂的一种。

1. 核心思想近朱者赤,节点属于哪个社区由它的邻居节点投票决定。邻居节点属于哪个社区的投票数目最多,它就属于哪个社区,如果最大票数中多个社区持平,则随机选择一个,达到物以类聚的效果。

2. 计算流程

  1. 标签初始化:初始状态下,每个节点将自己的编号作为标签(标签就是指节点所在社区的编号)。
  2. 标签传播:每个节点向其邻居(图中边另一头的节点)传播自己的标签,即告诉邻居自己是属于哪个社区的。
  3. 标签更新:每个节点根据其邻居的标签,选择重复数最多的那个标签作为自己的标签,即哪个社区包含其最多的邻居,它也算到该社区。如果多个社区包含的邻居数相同且最高,则随机选取其中一个社区。
  4. 如果节点更新后的标签发生了变化则回到第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

阅读原文

简介:FRM持证人|传播分享反欺诈风控知识。欢迎关注微信公众号:反欺诈攻防战
(0)
打赏 喜欢就点个赞支持下吧 喜欢就点个赞支持下吧

声明:本文来自“反欺诈攻防战”,分享链接:https://www.zyxiao.com/p/302012    侵权投诉

网站客服
网站客服
内容投稿 侵权处理
分享本页
返回顶部