社区发现之标签传播算法（LPA）

在Graph领域，社区发现（Community detection）是一个非常热门且广泛的话题，后面会写一个系列，该问题实际上是从子图分割的问题演变而来，在真实的社交网络中，有些用户之间连接非常紧密，有些用户之间的连接较为稀疏，连接紧密的用户群体可以看做一个社区，在风控问题中，可以简单的理解为团伙挖掘。

目前的社区发现问题分为两大类：非重叠社区发现和重叠社区发现。非重叠社区发现问题描述的是：一个网络中，每个节点均只能属于同一个社区，这意味这社区和社区之间是没有交集的。在非重叠社区发现算法中，有不同种类的解法：

1）基于模块度的社区发现算法：基本思想是通过定义模块度（Modularity）来衡量一个社区的划分是不是相对比较好的结果，从而将社区发现问题转化为最大化模块度的问题进行求解，后续的Louvain算法会讲到。

2）基于标签传播的社区发现算法：基本思想是通过标记节点的标签信息来更新未标记节点的标签信息，在整个网络中进行传播，直至收敛，其中最具代表性的就是标签传播算法（LPA,Label Propagation Algorithm），也是本文要讨论的算法。

注意：在团伙挖掘的实际应用的过程中，不要寄希望于优化社区发现算法提高准确性，可能永远都解决不了问题，因为关系的形成在实际中太过于复杂，我们更多的关注构图关系的筛选、清洗、提纯，以及分群后进一步加工处理

一、LPA概述