标签传播算法

标签传播是一种半监督机器学习算法，它将标签分配给以前未标记的数据点。在算法开始时，数据点的子集（通常只占很小一部分）有标签（或分类）。在整个算法过程中，这些标签会传播到未标记的点。^[1]

在复杂的网络中，真实的网络往往具有社区结构。标签传播是寻找社区的一种算法。与其他算法相比，^[2] 标签传播在运行时间和关于网络结构所需的先验信息量方面具有优势（不需要预先知道参数）。缺点是它不会产生唯一的解决方案，而是产生许多解决方案的集合。

目录编辑

1 算法的机理编辑

在初始条件下，节点带有一个标签，表示它们所属的社区。社区成员节点的标签会根据相邻节点拥有的标签而变化。此更改受度数为1的节点的标签最大数量的限制。每个节点都用一个唯一的标签初始化，然后标签在网络中扩散。因此，紧密相连的群体很快就会形成一个共同的标签。当许多这样密集（一致）的群体在整个网络中被创建时，他们继续向外扩展，直到不能再扩散。^[3]

该过程有5个步骤：^[3]

1.初始化网络中所有节点的标签。对于给定的节点x，Cx （0） = x。

2.设置t = 1。

3.以随机顺序排列网络中的节点，并将其设置为x

4.对于以特定顺序选择的每个x ∈ X，让Cx（t） = f（Cxi1（t），...、Cxim（t）、Cxi（m+1）（t1）。...，Cxik（t1））。f这里返回相邻标签中出现频率最高的标签。如果有多个最高频率标签，就随机选择一个标签。

5.如果每个节点都有其邻居节点中数量最多的标签，则停止算法。否则，设置t = t + 1并转到（3）。

2 多重社区结构编辑

与其他算法相比，标签传播可以在相同的初始条件下产生不同的社区结构。如果一些节点被给予初步标签，而另一些节点保持未标签，则解决方案的范围可以缩小。因此，未标记的节点将更有可能适应标记的节点。为了更准确地找到社区，雅克卡的索引被用来聚合多个社区结构，包含所有重要信息。^[3]

参考文献

[1]
^Zhu, Xiaojin. "Learning From Labeled and Unlabeled Data With Label Propagation"..
[2]
^M. E. J. Newman, "Detecting community structure in networks", 2004.
[3]
^U.N.Raghavan – R. Albert – S. Kumara "Near linear time algorithm to detect community structures in large-scale networks", 2007.

阅读 242