
SLPA
SLPA算法是一种社区监测算法,它是对LPA算法(标籤传播算法)的拓展。
基本介绍
- 中文名:SLPA算法
- 外文名:SLPA
SLPA分为以下三个阶段:SLPA(T,r)
T:用户定义的做大叠代数
r:处理后的阈值
1)首先,每一个节点的存储器中初始化一个唯一的标籤。
2)然后,重複进行以下步骤,直到达到最大叠代T:
a. 选择一个节点作为监听器。
b. 所选节点的每个邻居随机选择机率正比于该标籤在其存储器中的出现频率的标籤,把所选择的标籤传送到听众。
c. 监听器增加接收到的最流行的标籤到记忆体。
3)最后,根据在存储器里的标籤和阈值r,后处理被用于输出社区。
算法实现的步骤如下:
(1)初始化所有节点的标籤信息,使得每个节点拥有唯一的标籤。
(2)最为主要的是标籤传播过程。
1.当前节点作为一个listener。
2.当前节点的每一个邻居节点根据一定的speaking策略传递标籤信息。
3.当前节点从邻居节点传播的标籤信息集中根据一定的listener策略选择一个
标籤作为本次叠代中的新标籤。
4.算法收敛或遍历达到指定的次数,算法结束。否则,标籤在不断的遍历过程
中传播。
(3)标籤分类过程。后处理阶段根据节点的标籤信息进行社区发现。
(2)最为主要的是标籤传播过程。
1.当前节点作为一个listener。
2.当前节点的每一个邻居节点根据一定的speaking策略传递标籤信息。
3.当前节点从邻居节点传播的标籤信息集中根据一定的listener策略选择一个
标籤作为本次叠代中的新标籤。
4.算法收敛或遍历达到指定的次数,算法结束。否则,标籤在不断的遍历过程
中传播。
(3)标籤分类过程。后处理阶段根据节点的标籤信息进行社区发现。
SLPA算法优点:
不像其它算法,算法SLPA 不会像其它算法一样忘记上一次叠代中节点所更新的标籤信息,它给每个节点设定了一个标籤存储列表来存储每次叠代所更新的标籤。最终的节点社区从属关係将由标籤存储列表中所观察到的标籤的机率决定,当一个节点观察到有非常多一样的标籤时,那幺,很有可能这个节点属于这个社区,而且在传播过程中也很有可能将这个标籤传播给别的节点。更有益处的是,这种标籤存储列表的设计可以使得算法可以支持划分重叠社区。