Raghavan、Albert 和 Kumara 在 2007 年提出的 LPA 思路：先给每个节点一个唯一标签，然后让节点不断采用邻居中出现次数最多的标签，最终拥有相同标签的节点被划分为同一个社区。该方法不需要预先指定社区数量，也不需要定义复杂的优化目标，论文中称其具有接近线性的运行效率。
1. LPA要解决什么问题？
给定一个图：
G=(V , E)
其中：
- V 表示节点集合（Vertices）
- E 表示边集合（Edges）
社区发现（Community Detection）的目标，是将图中的节点划分成若干个社区： C1,C2,…,Ck
使得划分结果满足以下特性：
- 同一社区内部的节点连接更紧密；
- 不同社区之间的连接相对稀疏。
LPA（Label Propagation Algorithm，标签传播算法）的核心假设是：（一个节点更可能属于其大多数邻居所在的社区）节点会根据邻居的标签不断更新自己的标签，最终形成若干个标签一致的节点群体，这些群体就对应图中的社区。
2. LPA算法的核心思想
每个节点不断观察邻居的标签，并把自己的标签更新为邻居中出现频率最高的标签。
初始状态下，每个节点都有一个独一无二的标签。例如：
节点 | 初始标签 |
A | A |
B | B |
C | C |
D | D |
随着算法迭代，节点会逐渐采用邻居中更流行的标签。经过若干轮更新后，局部连接紧密的一组节点通常会形成相同标签。最终，标签相同的节点就构成一个社区。
3. 算法流程
1. 初始化标签
对图中每个节点 v ，初始化一个唯一标签：
label(v) = v
也就是说，每个节点一开始都认为自己是一个独立社区。
2. 遍历节点并更新标签
对于每个节点 v，统计它所有邻居节点的标签出现次数，然后选择出现次数最多的标签作为自己的新标签：
表示节点
的邻居集合；
是指示函数，条件成立时为 1，否则为 0。
3. 重复迭代直到收敛
当每个节点的标签都已经是其邻居中最常见的标签之一时，算法停止。NetworkX 对异步 LPA 的说明也是这一停止条件：当每个节点都拥有其邻居中出现最频繁的标签时，算法终止。
4. 输出社区
最终，拥有相同标签的节点被划分到同一个社区。
4. 伪代码
输入： 图 G = (V, E) 输出： 社区划分 communities 算法： 1. 对每个节点 v ∈ V： label[v] = v 2. repeat: changed = false 按随机顺序遍历每个节点 v： 统计 v 的邻居标签频率 找到出现次数最多的标签集合 best_labels 如果 best_labels 中包含多个标签： 从中随机选择一个标签 new_label 如果 new_label != label[v]： label[v] = new_label changed = true until changed == false 或者达到最大迭代次数 3. 将 label 相同的节点归为同一个社区 4. 返回 communities5. LPA 优缺点
LPA优点：简单、高效。
- 它不需要预先指定社区数量。像 K-Means 这类聚类算法通常需要提前给定 K，而 LPA 会根据图结构自然形成若干社区。
- 它不需要复杂的目标函数。Louvain 等算法通常围绕模块度进行优化，而 LPA 只依赖邻居标签投票。
- 它适合大规模图。由于每轮主要是局部邻居扫描，LPA 可以较容易地扩展到大型网络。
LPA缺点
- 结果不稳定：由于节点遍历顺序和并列标签选择可能带有随机性，LPA多次运行可能得到不同结果。
- 容易出现“巨型社区”：在某些图上，一个强势标签可能不断扩张，最终吞并大量节点，形成过大的社区。这会导致社区划分粒度过粗。
- 不直接优化全局质量指标：LPA本质上是一种局部传播机制，不显式优化模块度、割边数或似然函数。因此，它的结果不一定在全局意义上最优。
- 对噪声和桥接节点敏感：如果两个社区之间存在较多桥接边，标签可能跨社区传播，导致原本应分开的社区被合并。
