您的位置: 首页  >  文章  >  社区发现算法LPA

社区发现算法LPA

分类: 文章 • 2025-02-19 08:55:28

什么是社区发现

  • 现实中存在着各种网络：社交网络，交通网络，交易网络，食物链。将这些行为转化为图的网络形式
  • 社区发现是一种聚类算法
  • 作用：精准定位群体，方便进行商品推荐，好友推荐，广告投放

社区的种类：

  • 非重叠社区：任意两个社区的顶点之间没有交集
  • 重叠社区，在社区内部存在顶点之间的交集

社区发现的常用算法

  • LPA：Label Propagation Algorithm
    基于标签传播的非重叠社区发现算法
  • COPRA：Community Overlap PRopagation Algorithm
    基于LPA的扩展算法，用于重叠社区发现算法

LPA

LPA标签传播算法是社区发现算法中最简单易懂的一种，核心思想是近朱者赤。通过图中一个点所在的圈子来判断该点的特征性质，连接紧密的点​被划分到同一个社区中，达到物以类聚的效果。

大体流程：在一个由点和边组成的图结构中，通过一个点V的所有邻居对V进行投票，每个邻居把自己社区标签投给V，票数占多数的标签作为V的社区标签（如果最大票数中多个标签持平，则随机选择一个）。使用上述方法对所有的点迭代一轮，则每个点都会被分配到一个社区中（打上了标签）。迭代多轮后、或者在某一轮迭代后社区保持稳定时，连接紧密的点将有共同的社区标签，算法结束。

LPA算法示意

社区发现算法LPA

  • 使用加权和更新节点标签
    圆形标签权重=0.2+0.8+0.1=1.1
    三角形标签权重=0.4+0.6=1，所以节点标签更新为圆形
  • 使用加权平均更新节点标签
    圆形标签权重=(0.2+0.8+0.1)/3=0.367
    三角形标签权重=(0.4+0.6)/2=0.5，节点标签更新为三角形

相关推荐