什么是社区发现

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

社区的种类：

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

社区发现的常用算法

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

LPA

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

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

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，节点标签更新为三角形