历柴毛子代枚大学 复杂网络社区检测 XIDIAN UNIVERSITY >社区检测算法的分类： (2)基于模块度优化的社区检测算法 Newman于2004年提出了纽曼快速算法FA。FA算法是基于凝聚的算法， 属于模块度优化算法的一种。FA算法不断合并模块度函数值增加最多的两个社 区。该社区合并的过程可表示为一个树状图，树状图中使得模块度函数Q最大的 层次被用来划分社区。FA算法的时间复杂度为O(MW。 模块度函数Q还可以用公式表示为： --( (4-9) L:社区内的连边总数，M:网络中的连边总数。表示社区而非节点，d;表示 社区内所有节点的度的总和。公式的第一项L/M表示社区内连边数与网络总 6 边数的比值；第二项d山/2M表示随机网络中，社区内连边概率的期望值。 复杂网络社区检测 6 社区检测算法的分类： （2）基于模块度优化的社区检测算法 Newman于2004年提出了纽曼快速算法FA。FA算法是基于凝聚的算法， 属于模块度优化算法的一种。FA算法不断合并模块度函数值增加最多的两个社 区。该社区合并的过程可表示为一个树状图，树状图中使得模块度函数Q最大的 层次被用来划分社区。FA算法的时间复杂度为 Ο(MN)。 模块度函数Q还可以用公式表示为： 𝑄 = Li M − di 2M 2 C i=1 , (4-9) Li ∶ 社区内的连边总数，M: 网络中的连边总数。i表示社区而非节点，di 表示 社区i内所有节点的度的总和。公式的第一项 Li M 表示社区内连边数与网络总 边数的比值；第二项 di 2M 表示随机网络中，社区内连边概率的期望值