标籤传播算法（LPA）是由Zhu等人于2002年提出，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标籤信息去预测未标记节点的标籤信息。利用样本间的关係建立关係完全图模型，在完全图中，节点包括已标注和未标注数据，其边表示两个节点的相似度，节点的标籤按相似度传递给其他节点。标籤数据就像是一个源头，可以对无标籤数据进行标注，节点的相似度越大，标籤越容易传播。由于该算法简单易实现，算法执行时间短，複杂度低且分类效果好，引起了国内外学者的关注，并将其广泛地套用到多媒体信息分类、虚拟社区挖掘等领域中。本文利用关键字labelpropagation、标籤传播、标籤传递、标记传播、标记传递等词作为关键字，对国内外资料库及网路资源进行了检索，结果发现，目前国内外相关文献期刊论文约有90篇，其中国外82篇，国内8篇，国内外硕博论文3篇。

令( x₁，y₁) …( x_l，y_l) 是已标注数据，Y_L={ y₁…y_l} ∈{ 1…C} 是类别标籤，类别数 C 已知，且均存在于标籤数据中。令( x_{l + 1}，y_{l + 1}) …( x_{l + u}，y_{l + u}) 为未标注数据，Y_U={ y_{l + 1}…y_{l + u}} 不可观测，l << u，令数据集 X = { x₁…x_{l + u}} ∈R。问题转换为: 从数据集 X 中，利用Y_L的学习，为未标注数据集Y_U的每个数据找到对应的标籤。

将所有数据作为节点( 包括已标注和未标注数据) ，创建一个完全连线图，其边的权重计算式如下:

其中: d_ij表示任意两个节点的欧氏距离，权重 w_ij受控于参数 σ。

为衡量一个节点的标注通过边传播到其他节点的机率，在此定义一个( l + u) × ( l + u) 机率传递矩阵 T 如下所示:

其中: T_ij是节点 j 到 i 的传播机率。

算法描述如下：

1. 所有节点传播标籤一步： Y← TY；

2. 行标準化矩阵 Y 来维持类别的机率；

3. 夹逼标注数据，重複步骤 2 直到 Y 收敛。

步骤 3 可以使得节点标籤的类别分布集中在给定的类别。该算法的缺点在于需要预先标注数据，而且需要预先知识知道分类的类别个数。

根据LPA算法基本理论，每个节点的标籤按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标籤来更新自己的标籤，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标籤越趋于一致，其标籤就越容易传播。在标籤传播过程中，保持已标注数据的标籤不变，使其像一个源头把标籤传向未标注数据。最终，当叠代过程结束时，相似节点的机率分布也趋于相似，可以划分到同一个类别中，从而完成标籤传播过程。

优缺点：LPA算法的优点是简单、高效、快速；缺点是每次叠代结果不稳定，準确率不高。

在LPA算法中节点的Label有同步更新与异步更新2种更新方法。同步更新方法在二分图中可能出现产生震荡情况。为了避免循环和保证收敛，LPA算法採用异步的策略更新节点的标籤，并在每次叠代前对节点重新进行随机排序。