55、网络算法：标签传播、Kruskal 算法与加权网络模型

网络算法：标签传播、Kruskal 算法与加权网络模型

标签传播算法

标签传播算法是一种直观且高效的网络社区发现方法。其核心假设是：若图按社区组织，节点 $i$ 所属社区为 $C(i)$，那么 $i$ 的大多数邻居大概率也属于 $C(i)$。基于此，初始为各节点分配不同标签，随后反复更新节点标签，使其与多数邻居的标签一致，最终同一社区的节点标签会相同。

该算法按轮次进行，每轮中每个节点的标签仅更新一次。实现时需考虑两个关键方面：更新策略和停止准则。

更新策略有同步更新和异步更新两种。同步更新是先计算所有节点的新标签，再在每轮结束时统一更新。此策略实现简单，但效率低，常产生周期性轨道，使算法陷入模块化值较小的配置。异步更新则逐个处理节点，计算并立即更新其标签，有效降低算法陷入循环的概率。

以下是异步更新的标签传播算法伪代码：

Algorithm 51 label_propagation() Input: j, r, N Output: labels {vector of node labels} 1: for i = 0 to N-1 do 2: labels[i] ←i 3: ids[i] ←i 4: end for 5: continue ←TRUE 6: while continue is not FALSE do 7: shuffle_array(ids) 8: continue ←FALSE 9: for i = 0 to N -1 do 10: neigh_label ←get_most_frequent_l