LPA社区发现算法介绍和代码示例
在这篇SynchroTrap欺诈检测算法代码实操示例文章中，我们通过 SynchroTrap思想构建了商户评价用户的同步行为关系，接下来用社区发现算法LPA对这些行为进行打标，将其划分成不同属性的社区(群体)。
一、LPA算法应用示例
这里同步行为次数是基于商户（约束条件）去重作统计的，即A和B对同一个商家Y在不同时间段有多次匹配行为时，只算作一次。我们也可以考虑不对商家作去重处理，不过需要注意的是在杰斯卡相似度计算过程用到的x_cnt等指标逻辑也要保持一致，要么都去重，要么都不去重，我在这块处理上也搞错过。如果采用不去重法得到的应是：
由于 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))
二、LPA算法介绍
LPA全称Label Propagation Algorithm，即标签传递算法，属于图聚类算法，社区发现算法中比较简单易懂的一种。
标签初始化：初始状态下，每个节点将自己的编号作为标签（标签就是指节点所在社区的编号）。
标签传播：每个节点向其邻居（图中边另一头的节点）传播自己的标签，即告诉邻居自己是属于哪个社区的。
标签更新：每个节点根据其邻居的标签，选择重复数最多的那个标签作为自己的标签，即哪个社区包含其最多的邻居，它也算到该社区。如果多个社区包含的邻居数相同且最高，则随机选取其中一个社区。
如果节点更新后的标签发生了变化则回到第2步，否则该节点进入非激活状态，即收敛状态。循环该过程，直到图中所有节点都进入收敛状态。需要注意的是，进入非激活状态的节点，如果在收到其邻居的消息后，标签发生了变化，其将再次进入激活状态，重新开始标签传播。
Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks
题图来源：网站Pexels
THE END