历安毛子代枚大” 复杂网络社区检测 XIDIAN UNIVERSITY >社区检测算法的分类： (2)基于模块度优化的社区检测算法 ·在FA方法基础上进行了改进，Blondel等提出了BGLL算法，简化了社区合并 的过程，大大地降低了FA算法的时间复杂度。BGLL算法的主要步骤为： (1)将网络中的每个节点看作一个社区，节点之间的连边被看作社区间的连边 ,网络包含多少个节点，就存在多少个社区；然后计算某一社区与相连所有 社区合并时模块度函数的增加值，进而将模块度函数值增量最大的社区与该 社区合并，不断重复上一步骤，直到模块度函数值不再增加。 (2)将上一步中的每一个社区都看作新网络的一个节点。其中，两个新节点之 间的连边权重等于两个原社区之间连边的权重之和，而社区内部连边的权重 看作新节点的自环权重。这样就得到了收缩后的新网络，并可继续用上一步 描述的方式对新网络进行处理。 ● (3)重复以上两步，直到模块度不再增加为止。此时得到的社区划分即为 BGLL算法的检测结果。BGLL算法的时间复杂度为(Nlog(): 8 复杂网络社区检测 8 社区检测算法的分类： （2）基于模块度优化的社区检测算法 • 在FA方法基础上进行了改进, Blondel等提出了BGLL算法，简化了社区合并 的过程，大大地降低了FA算法的时间复杂度。BGLL算法的主要步骤为： • (1)将网络中的每个节点看作一个社区，节点之间的连边被看作社区间的连边 ，网络包含多少个节点，就存在多少个社区；然后计算某一社区与相连所有 社区合并时模块度函数的增加值，进而将模块度函数值增量最大的社区与该 社区合并，不断重复上一步骤，直到模块度函数值不再增加。 • (2)将上一步中的每一个社区都看作新网络的一个节点。其中，两个新节点之 间的连边权重等于两个原社区之间连边的权重之和，而社区内部连边的权重 看作新节点的自环权重。这样就得到了收缩后的新网络，并可继续用上一步 描述的方式对新网络进行处理。 • (3)重复以上两步，直到模块度不再增加为止。此时得到的社区划分即为 BGLL算法的检测结果。BGLL算法的时间复杂度为Ο(Nlog(N))