历安毛子枚大兽 第五讲：复杂网络社区检测 XIDIAN UNIVERSITY (1)复杂网络社区检测简介 (2)社区检测方法 2
（1）复杂网络社区检测简介 （2）社区检测方法 第五讲：复杂网络社区检测 2
历些毛子代枝大兽 复杂网络社区检测 XIDIAN UNIVERSITY >社区检测： 在具有社区结构的网络中，节点呈社区分布，同一社区内部节点连边密集 ,不同社区之间节点连边稀疏。 社区检测，就是将网络中的社区找出来，也称社区发现、社区挖掘。 >社区检测算法的分类： (1)层次聚类算法：包括凝聚算法和分裂算法 (2)基于模块度优化的社区检测算法 (3)基于网络动力学的社区检测算法 (4)谱聚类法 (5)基于学习的方法：图神经网络 3
复杂网络社区检测 3 社区检测： 在具有社区结构的网络中，节点呈社区分布，同一社区内部节点连边密集 ，不同社区之间节点连边稀疏。 社区检测，就是将网络中的社区找出来，也称社区发现、社区挖掘。 社区检测算法的分类： （1）层次聚类算法：包括凝聚算法和分裂算法 （2）基于模块度优化的社区检测算法 （3）基于网络动力学的社区检测算法 （4）谱聚类法 （5）基于学习的方法：图神经网络
历柴毛子代枚大学 复杂网络社区检测 XIDIAN UNIVERSITY >社区检测算法的分类： (1)层次聚类算法：包括凝聚算法和分裂算法 Girvan和Newman于2002年提出了GN算法是典型的分裂算法。该算法提 出了边介数的概念，用于衡量网络中某条边的重要程度。边介数定义为经过该 边的最短路径数目。GN算法通过不断删除边介数最大的连边来划分社区。 缺点： 1.不容易确定从哪里停止删边；即不容易 确定最终的社区划分： 2.由于删除边介数最大的连边后需要重新 计算网络中所有节点的边介数，且GN算法 不断删除连边，直到所有网络节点都各自成 为一个社区时才能得到树状图，因此该算法 的时间复杂度较高，为OW3)。 层次聚类算法中的树状图
复杂网络社区检测 4 社区检测算法的分类： （1）层次聚类算法：包括凝聚算法和分裂算法 Girvan和Newman于2002年提出了GN算法是典型的分裂算法。该算法提 出了边介数的概念，用于衡量网络中某条边的重要程度。边介数定义为经过该 边的最短路径数目。GN算法通过不断删除边介数最大的连边来划分社区。 缺点： 1. 不容易确定从哪里停止删边；即不容易 确定最终的社区划分； 2. 由于删除边介数最大的连边后需要重新 计算网络中所有节点的边介数，且GN算法 不断删除连边，直到所有网络节点都各自成 为一个社区时才能得到树状图，因此该算法 的时间复杂度较高，为 Ο(N 3 )。 层次聚类算法中的树状图
历安毛子代枚大等 复杂网络社区检测 XIDIAN UNIVERSITY >社区检测算法的分类： (1)层次聚类算法：包括凝聚算法和分裂算法 Girvan和Newman于2002年提出了GN算法是典型的分裂算法。该算法提 出了边介数的概念，用于衡量网络中某条边的重要程度。边介数定义为经过该 边的最短路径数目。GN算法通过不断删除边介数最大的连边来划分社区。 改进： Fortunato等提出了信息中心度指标，以及 Zhou等定义的网络中连边的相异性参数。 用这些评价指标取代边介数进行社区检测， 大大缩短了GN算法的运行时间 层次聚类算法中的树状图
复杂网络社区检测 5 社区检测算法的分类： （1）层次聚类算法：包括凝聚算法和分裂算法 Girvan和Newman于2002年提出了GN算法是典型的分裂算法。该算法提 出了边介数的概念，用于衡量网络中某条边的重要程度。边介数定义为经过该 边的最短路径数目。GN算法通过不断删除边介数最大的连边来划分社区。 改进： Fortunato等提出了信息中心度指标，以及 Zhou等定义的网络中连边的相异性参数。 用这些评价指标取代边介数进行社区检测， 大大缩短了GN算法的运行时间 层次聚类算法中的树状图
历柴毛子代枚大学 复杂网络社区检测 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 表示随机网络中，社区内连边概率的期望值