版权归原作者所有,如有侵权,请联系我们

[科普中国]-基于标签传播的社团发现算法(LPA)

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

LPA1算法的基本思想是为网络中所有的节点赋予不同的标签,设计一个传播规则,标签根据这个规则在网络上迭代传播,直到所有节点的标签传播达到稳定,最后将具有相同标签的节点划分到一个社区中。在每次迭代传播时,每个节点的标签都更新为最多数量的邻居节点拥有的标签。这个传播规则定义了网络的社区结构,即网络中每个节点选择加入的社区是它最多数量的邻居节点属于的社区。

该算法具体的步骤如下:

(1)开始时,所有节点使用独一无二的标签初始化;

(2)按照随机的顺序扫描所有的节点,每个节点的标签被更新为其最大数量的邻居所具有的标签。如果同时有多个标签被最多的邻居节点使用,则随机的选择一个标签;

(3)当所有节点的标签与其最大数量的邻居拥有的标签相同时,进行步骤(4),否则返回步骤 (2);

(4)最后,将网络中每一个具有相同标签的连通部分作为一个社区。