社团发现算法(LPA_SLPA_BMLPA)

1、社团发现算法社团发现算法LPA SLPA BMLPALPA SLPA BMLPA20172017年年1212月月CONTENTSCONTENS一、一、LPALPA二、二、SLPASLPA三、三、BMLPABMLPA1、LPALPA(Label Propagation Algorithm)：标签传播算法给每个节点添加标签（label）以代表它所属的社团，并通过标签的“传播”形成同一标签的“社团”结构将一个节点的邻居节点的标签中数量最多的标签作为该节点自身的标签。1、LPALabel Propagation：传播过程1. 初始时，给每个节点一个唯一的标签；2. 每个节点使用其邻居节点的标签中最多的

2、标签来更新自身的标签（若都相等则随机选取一个更新自己）；3. 反复执行步骤2，直到每个节点的标签都不再发生变化为止。1、LPALPA标签更新：同步/异步1、LPALPA算法结束条件1、LPA 优点：思路简单，时间复杂度低，适合大型复杂网络； 缺点：划分结果不稳定，随机性强是这个算法致命的缺点。 LPA优缺点更新顺序随机选择2、SLPA社交网络具有重叠性(overlapping)：一个人属于多个社团2、SLPASLPA(Speaker-listener Label Propagation Algorithm)LPA要求每个节点只能拥有一个标签并通过迭代更新节点的标签，当算法收敛时发现不相交的社团

3、。该算法仅适合于非重叠社团发现。SLPA在LPA的基础上引入Speaker（标签传播节点）以及listener（标签接受节点）两个概念。2、SLPASLPA算法流程初始化每一个节点Speakers发送自身标签中最多的那个标签，Listeners接收所有发送来的标签中最多的那个标签统计每个节点各类标签数量，将个数超过要求的标签作为节点最终的社团标签算法流程1234n13322242n33443313414536785 第i次迭代，节点112435i迭代次数：2433 后处理：T次迭代结束后，根据次数阈值r，从每个节点的存储器中选出最终该节点所带有的标签集。存储器2、SLPASLPA算法总结 SL

4、PA能实现高效的重叠式社团检测； 算法过程可以很容易地进行修改，以适应不同的规则（即说话者规则，监听规则，存储器更新，停止标准和后处理）和不同类型的网络（例如k-分图）； 未来研究方向包括模糊层次检测和时间社区检测。3、BMLPABMLPA(Balanced Multi-label Propagation Algorithm)1. 使用Rough Core函数初始化整个网络，形成几个不重叠的社团，给每个节点一个平衡归属因子，初始值为1；2. 利用传播算法更新每个结点具有的社团标签及平衡归属因子，比较新旧网络状态是否一致，若不一致则重复执行该步；3. 遍历每个结点，确保每个社团不是其他社团的子集；4. 分割出每个社团。3、BMLPARough Core函数标签传播重复标签传播过程直至社团数量和各社团节点数量不变检查有没有被大的社团真包含的小社团，从社团集合中去掉这种小社团3、BMLPARough Core：初始化网络，将网络中节点划分为不相交的几个社团初始网络（节点无标签）Rough Core3、BMLPALabel Propagation：传播过程3、BMLPABMLPA算法总结 BMLPA可以实现重叠式