模块度 - 版本历史

Liushikang1992：/* 快速模块度优化算法 */

2020-05-06T08:59:05Z

快速模块度优化算法

Liushikang1992：/* 快速模块度优化算法 */

2020-05-06T08:58:33Z

快速模块度优化算法

Liushikang1992：/* 快速模块度优化算法 */

2020-05-06T08:57:41Z

快速模块度优化算法

思无涯咿呀咿呀：/* 起源 */

2020-04-27T07:58:17Z

起源

2020年4月27日 (一) 07:54 思无涯咿呀咿呀

2020-04-27T07:54:49Z

思无涯咿呀咿呀：思无涯咿呀咿呀移动页面模块度（在网络领域中）至模块度

2020-04-27T07:49:45Z

思无涯咿呀咿呀移动页面模块度（在网络领域中）至模块度

乐多多：/* 快速模块度优化算法 */

2020-04-25T10:02:46Z

快速模块度优化算法

乐多多：/* 经典贪婪算法 */

2020-04-25T10:02:10Z

经典贪婪算法

乐多多：/* 模块度的计算方法 */

2020-04-25T10:00:16Z

模块度的计算方法

乐多多：/* 两个节点间随机连边的概率期望求法 */

2020-04-25T04:57:52Z

两个节点间随机连边的概率期望求法

@@ 第170行： / 第170行： @@
 ===快速模块度优化算法===
-为了降低算法的时间复杂度，'''文森特·布隆代尔  Vincent Blondel'''等人提出了另一种层次贪婪算法，名为Louvain modularity。该算法包括两个阶段，第一阶段合并社团，算法将每个节点当作一个社团，基于模块度增量最大化标准决定哪些相邻的社团应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社团重新看成节点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社团划分的模块度不再增长，得到网络的社团近似最优划分。
+为了降低算法的时间复杂度，'''文森特·布隆代尔  Vincent Blondel'''等人提出了另一种层次贪婪算法，名为'''Louvain modularity'''。该算法包括两个阶段，第一阶段合并社团，算法将每个节点当作一个社团，基于模块度增量最大化标准决定哪些相邻的社团应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社团重新看成节点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社团划分的模块度不再增长，得到网络的社团近似最优划分。
 这个简单算法具有以下几个优点：
 #该算法的步骤比较直观并且易于实现；

@@ 第170行： / 第170行： @@
 ===快速模块度优化算法===
-为了降低算法的时间复杂度，'''文森特·布隆代尔  Vincent Blondel'''等人提出了另一种层次贪婪算法 (Louvain) 。该算法包括两个阶段，第一阶段合并社团，算法将每个节点当作一个社团，基于模块度增量最大化标准决定哪些相邻的社团应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社团重新看成节点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社团划分的模块度不再增长，得到网络的社团近似最优划分。
+为了降低算法的时间复杂度，'''文森特·布隆代尔  Vincent Blondel'''等人提出了另一种层次贪婪算法，名为Louvain modularity。该算法包括两个阶段，第一阶段合并社团，算法将每个节点当作一个社团，基于模块度增量最大化标准决定哪些相邻的社团应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社团重新看成节点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社团划分的模块度不再增长，得到网络的社团近似最优划分。
 这个简单算法具有以下几个优点：
 #该算法的步骤比较直观并且易于实现；

@@ 第170行： / 第170行： @@
 ===快速模块度优化算法===
-为了降低算法的时间复杂度，'''文森特·布隆代尔  Vincent Blondel'''等人提出了另一种层次贪婪算法。该算法包括两个阶段，第一阶段合并社团，算法将每个节点当作一个社团，基于模块度增量最大化标准决定哪些相邻的社团应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社团重新看成节点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社团划分的模块度不再增长，得到网络的社团近似最优划分。
+为了降低算法的时间复杂度，'''文森特·布隆代尔  Vincent Blondel'''等人提出了另一种层次贪婪算法 (Louvain) 。该算法包括两个阶段，第一阶段合并社团，算法将每个节点当作一个社团，基于模块度增量最大化标准决定哪些相邻的社团应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社团重新看成节点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社团划分的模块度不再增长，得到网络的社团近似最优划分。
 这个简单算法具有以下几个优点：
 #该算法的步骤比较直观并且易于实现；

@@ 第7行： / 第7行： @@
 ==起源==
-许多重要的科学问题可以通过网络来呈现，并进行实证研究。 生物模式和社会模式、万维网、代谢网络、食物网、神经网络和病理网络这类现实问题，都可以通过数学表示和拓扑学研究来发现一些意想不到的结构特征。 这些网络大都具有某种社团结构，这种结构能够帮助人们更加理解网络中的动态过程。 例如，与连接稀疏的社会群体相比，连接紧密的社会群体之间传播信息或谣言的速度更快。 如果一个网络由若干个单独节点组成，这些节点之间通过链接相互联系，这表示节点之间有一定程度的相互作用，故将社团定义为内部连接紧密的节点组(而组与组之间连接稀疏)。对于一般的网络而言，由于社团可能具有完全不同的属性，如节点度、集聚系数、中介性、中心性等，所以如何检测网络中的社团极为重要。 模块度就是这样一种度量，当模块度最大时，就能够检测到给定网络的社团结构。
+许多重要的科学问题可以通过网络来呈现，并进行实证研究。 生物模式和社会模式、万维网、代谢网络、食物网、神经网络和病理网络这类现实问题，都可以通过数学表示和拓扑学研究来发现一些意想不到的结构特征。 这些网络大都具有某种社团结构，这种结构能够帮助人们更加理解网络中的动态过程。 例如，与连接稀疏的社会群体相比，连接紧密的社会群体之间传播信息或谣言的速度更快。 如果一个网络由若干个单独节点组成，这些节点之间通过链接相互联系，这表示节点之间有一定程度的相互作用，故将社团定义为内部连接紧密的节点组(而组与组之间连接稀疏)。对于一般的网络而言，由于社团可能具有完全不同的属性，如节点度、[[集聚系数]]、[[介数中心性]]、度分布等，所以如何检测网络中的社团极为重要。 模块度就是这样一种度量，当模块度最大时，就能够检测到给定网络的社团结构。
 ==定义==

@@ 第3行： / 第3行： @@
 |description=模块度，集智，社团结构检测算法
 }}
-'''模块度  Modularity'''是对网络结构或图像结构的一种度量。它是一种衡量网络模板（也称为节点集或社团）划分质量的标准。如果模板度高，则说明节点集内部连接紧密，而节点集与节点集之间连接稀疏。模块度是检测'''社团结构  Community Structure'''的常用优化方法。不过，受分辨率的限制，该方法不适用于检测小社团。
+'''模块度  Modularity'''是对网络结构或图像结构的一种度量。它是一种衡量网络模板（也称为节点集或社团）划分质量的标准。如果模板度高，则说明节点集内部连接紧密，而节点集与节点集之间连接稀疏。模块度是检测'''[[社团结构]]  Community Structure'''的常用优化方法。不过，受分辨率的限制，该方法不适用于检测小社团。
@@ 第11行： / 第11行： @@
 ==定义==
-模块度 = 落在同一组的边的比例 ，即对这些边进行随机分配所得到的期望概率（将边随机分配是为了保持每个节点的节点度不变）。其中，落在同一组的边的比例=组内的总边数÷网络中的总边数。无权图和无向图的模块度取值都在<math>[-1/2,1]</math>范围内。如果节点组中的连边数量超过了随机分配时所得到的期望连边数量，模块度为正数。没有超过，则为负数。将给定网络的节点划分为若干模块，模块度反映的是模块内部连边的集中程度，而不是各模块之间所有节点链路的随机分布情况。
+模块度是指落在同一组的边的比例 ，即对这些边进行随机分配所得到的期望概率（将边随机分配是为了保持每个节点的节点度不变）。其中，落在同一组的边的比例=组内的总边数÷网络中的总边数。无权图和无向图的模块度取值都在<math>[-1/2,1]</math>范围内。如果节点组中的连边数量超过了随机分配时所得到的期望连边数量，模块度为正数。没有超过，则为负数。将给定网络的节点划分为若干模块，模块度反映的是模块内部连边的集中程度，而不是各模块之间所有节点链路的随机分布情况。
@@ 第107行： / 第107行： @@
-该函数与辛流形的'''汉密尔顿函数 Hamiltonian'''的形式相同，故可创建出简单的算法，例如使用'''模拟退火算法 Simulated Annealing'''来使模块度最大化。 模块化的一般形式等价于一个 Potts 自旋玻璃，在这种情况下也可以发展类似的算法。
+该函数与辛流形的'''汉密尔顿函数 Hamiltonian'''的形式相同，故可创建出简单的算法，例如使用'''[[模拟退火算法]] Simulated Annealing'''来使模块度最大化。 模块化的一般形式等价于一个 Potts 自旋玻璃，在这种情况下也可以发展类似的算法。
 ==多社团检测实例==
@@ 第154行： / 第154行： @@
 ==分辨率限制==
-将一个给定网络与该网络相对应的随机零模型进行对比，随机模型通常具有相同度序列、且其连边随机连接。模块度通过比较社团内部的连边数量与所期望的连边数量来判断给定网络是否具有较强的社团结构。（参考网络科学导论。）这个随机零模型隐含地假设每个节点可以连接到网络的任何其他节点。 然而，如果网络规模非常大，这种假设是不合理的。因为通过一个节点的视角看到了网络的一小部分，却忽略了网络的大部分。 这说明随着网络规模的增大，两组节点之间的期望边数会减少。 因此，如果网络足够大，模块化零模型中两组节点集之间的期望边数可能小于一条。 在该种情况下，模块度将两组节点集之间存在单边作为节点集之间强相关性的标志。若对模块度进行优化，将导致两组节点集的合并，独立于社团群众。 因此，即使是内部连边密度最高、可识别性最好的弱互联完全图，在网络规模足够大的情况下，也可以通过模块度优化进行合并。 因此，即使小型社团能够被准确定义，在大型网络中优化模块度的方法也并不适用于他们。 对于依赖全局零模型的模块度优化方法来说，这种偏差是不可避免的。
+将一个给定网络与该网络相对应的随机零模型进行对比，随机模型通常具有相同度序列、且其连边随机连接。模块度通过比较社团内部的连边数量与所期望的连边数量来判断给定网络是否具有较强的[[社团结构]]。（参见：[[网络科学导论]]。）这个随机零模型隐含地假设每个节点可以连接到网络的任何其他节点。 然而，如果网络规模非常大，这种假设是不合理的。因为通过一个节点的视角看到了网络的一小部分，却忽略了网络的大部分。 这说明随着网络规模的增大，两组节点之间的期望边数会减少。 因此，如果网络足够大，模块化零模型中两组节点集之间的期望边数可能小于一条。 在该种情况下，模块度将两组节点集之间存在单边作为节点集之间强相关性的标志。若对模块度进行优化，将导致两组节点集的合并，独立于社团群众。 因此，即使是内部连边密度最高、可识别性最好的弱互联完全图，在网络规模足够大的情况下，也可以通过模块度优化进行合并。 因此，即使小型社团能够被准确定义，在大型网络中优化模块度的方法也并不适用于他们。 对于依赖全局零模型的模块度优化方法来说，这种偏差是不可避免的。
@@ 第162行： / 第162行： @@
 ===经典贪婪算法===
-模块度最大化问题是一个经典的最优化问题，'''马克·纽曼 Mark NewMan '''基于贪婪思想提出了模块度最大化的'''贪婪算法 Fast NewMan(FN)''' 。贪婪思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题。找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。初始时，FN算法将网络中的每个节点都看成独立的小社团。然后考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪婪原则，选取使模块度增长最大或者减小最少的两个社团，将它们合并成一个社团。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社团划分就视为最优社团划分。
+模块度最大化问题是一个经典的最优化问题，'''[[马克·纽曼 Mark NewMan]] '''基于贪婪思想提出了模块度最大化的'''贪婪算法 Fast NewMan(FN)''' 。贪婪思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题。找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。初始时，FN算法将网络中的每个节点都看成独立的小社团。然后考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪婪原则，选取使模块度增长最大或者减小最少的两个社团，将它们合并成一个社团。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社团划分就视为最优社团划分。
 贪婪算法FN具体步骤：
 # 去掉网络中所有的边，网络的每个节点都单独作为一个社团；

@@ 第15行： / 第15行： @@
 ==模块度的计算方法==
-模块度的计算有很多种方法。考虑一个含有<math>n</math>个节点、<math>m</math> 条连边的图网络，这样的图网络能够用一个成员变量<math>s</math>划分为两个社团。如果节点<math>v</math>属于社团1，即设 <math>s_v = 1</math>，或节点 <math>v</math>属于社团2，即设<math>s_v = -1</math>。
+模块度的计算有很多种方法。考虑一个含有<math>n</math>个节点、<math>m</math> 条连边的网络，这样的图网络能够用一个成员变量<math>s</math>划分为两个社团。如果节点<math>v</math>属于社团1，即设 <math>s_v = 1</math>，或节点 <math>v</math>属于社团2，即设<math>s_v = -1</math>。
 将图网络的邻接矩阵表示为 <math>A</math>。

@@ 第33行： / 第33行： @@
 现考虑节点<math>v</math>和节点<math>w</math>，各自的节点度分别为 <math>k_v</math>和<math>k_w</math>，在随机重新连边的网络中，利用上述方法计算这两个节点间所期望的完整连边数量。
-其中，所有单边的数量为
+其中，所有单边的数量为：
 :<math>l = \sum_{u} k_{u} =2m</math>
@@ 第50行： / 第50行： @@
 因此，节点<math>v</math>和节点<math>w</math>之间的实际边数与它们在随机化网络下连边数的期望之差为<math>A_{vw} - \frac{k_v k_w}{2m}</math>。
 ===公式表达一===