更改

|description=模块度，集智，社团结构检测算法

|description=模块度，集智，社团结构检测算法

}}

}}

'''模块度  Modularity'''是对网络结构或图像结构的一种度量。它是一种衡量网络模板（也称为节点集或社团）划分质量的标准。如果模板度高，则说明节点集内部连接紧密，而节点集与节点集之间连接稀疏。模块度是检测'''社团结构  Community Structure'''的常用优化方法。不过，受分辨率的限制，该方法不适用于检测小社团。

'''模块度  Modularity'''是对网络结构或图像结构的一种度量。它是一种衡量网络模板（也称为节点集或社团）划分质量的标准。如果模板度高，则说明节点集内部连接紧密，而节点集与节点集之间连接稀疏。模块度是检测'''[[社团结构]] Community Structure'''的常用优化方法。不过，受分辨率的限制，该方法不适用于检测小社团。

==定义==

==定义==

模块度 = 落在同一组的边的比例 ，即对这些边进行随机分配所得到的期望概率（将边随机分配是为了保持每个节点的节点度不变）。其中，落在同一组的边的比例=组内的总边数÷网络中的总边数。无权图和无向图的模块度取值都在<math>[-1/2,1]</math>范围内。如果节点组中的连边数量超过了随机分配时所得到的期望连边数量，模块度为正数。没有超过，则为负数。将给定网络的节点划分为若干模块，模块度反映的是模块内部连边的集中程度，而不是各模块之间所有节点链路的随机分布情况。

模块度是指落在同一组的边的比例 ，即对这些边进行随机分配所得到的期望概率（将边随机分配是为了保持每个节点的节点度不变）。其中，落在同一组的边的比例=组内的总边数÷网络中的总边数。无权图和无向图的模块度取值都在<math>[-1/2,1]</math>范围内。如果节点组中的连边数量超过了随机分配时所得到的期望连边数量，模块度为正数。没有超过，则为负数。将给定网络的节点划分为若干模块，模块度反映的是模块内部连边的集中程度，而不是各模块之间所有节点链路的随机分布情况。

该函数与辛流形的'''汉密尔顿函数 Hamiltonian'''的形式相同，故可创建出简单的算法，例如使用'''模拟退火算法 Simulated Annealing'''来使模块度最大化。 模块化的一般形式等价于一个 Potts 自旋玻璃，在这种情况下也可以发展类似的算法。

该函数与辛流形的'''汉密尔顿函数 Hamiltonian'''的形式相同，故可创建出简单的算法，例如使用'''[[模拟退火算法]] Simulated Annealing'''来使模块度最大化。 模块化的一般形式等价于一个 Potts 自旋玻璃，在这种情况下也可以发展类似的算法。

==多社团检测实例==

==多社团检测实例==

==分辨率限制==

==分辨率限制==

将一个给定网络与该网络相对应的随机零模型进行对比，随机模型通常具有相同度序列、且其连边随机连接。模块度通过比较社团内部的连边数量与所期望的连边数量来判断给定网络是否具有较强的社团结构。（参考网络科学导论。）这个随机零模型隐含地假设每个节点可以连接到网络的任何其他节点。 然而，如果网络规模非常大，这种假设是不合理的。因为通过一个节点的视角看到了网络的一小部分，却忽略了网络的大部分。 这说明随着网络规模的增大，两组节点之间的期望边数会减少。 因此，如果网络足够大，模块化零模型中两组节点集之间的期望边数可能小于一条。 在该种情况下，模块度将两组节点集之间存在单边作为节点集之间强相关性的标志。若对模块度进行优化，将导致两组节点集的合并，独立于社团群众。 因此，即使是内部连边密度最高、可识别性最好的弱互联完全图，在网络规模足够大的情况下，也可以通过模块度优化进行合并。 因此，即使小型社团能够被准确定义，在大型网络中优化模块度的方法也并不适用于他们。 对于依赖全局零模型的模块度优化方法来说，这种偏差是不可避免的。

将一个给定网络与该网络相对应的随机零模型进行对比，随机模型通常具有相同度序列、且其连边随机连接。模块度通过比较社团内部的连边数量与所期望的连边数量来判断给定网络是否具有较强的[[社团结构]]。（参见：[[网络科学导论]]。）这个随机零模型隐含地假设每个节点可以连接到网络的任何其他节点。 然而，如果网络规模非常大，这种假设是不合理的。因为通过一个节点的视角看到了网络的一小部分，却忽略了网络的大部分。 这说明随着网络规模的增大，两组节点之间的期望边数会减少。 因此，如果网络足够大，模块化零模型中两组节点集之间的期望边数可能小于一条。 在该种情况下，模块度将两组节点集之间存在单边作为节点集之间强相关性的标志。若对模块度进行优化，将导致两组节点集的合并，独立于社团群众。 因此，即使是内部连边密度最高、可识别性最好的弱互联完全图，在网络规模足够大的情况下，也可以通过模块度优化进行合并。 因此，即使小型社团能够被准确定义，在大型网络中优化模块度的方法也并不适用于他们。 对于依赖全局零模型的模块度优化方法来说，这种偏差是不可避免的。

===经典贪婪算法===

===经典贪婪算法===

模块度最大化问题是一个经典的最优化问题，'''马克·纽曼 Mark NewMan '''基于贪婪思想提出了模块度最大化的'''贪婪算法 Fast NewMan(FN)''' 。贪婪思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题。找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。初始时，FN算法将网络中的每个节点都看成独立的小社团。然后考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪婪原则，选取使模块度增长最大或者减小最少的两个社团，将它们合并成一个社团。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社团划分就视为最优社团划分。

模块度最大化问题是一个经典的最优化问题，'''[[马克·纽曼 Mark NewMan]] '''基于贪婪思想提出了模块度最大化的'''贪婪算法 Fast NewMan(FN)''' 。贪婪思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题。找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。初始时，FN算法将网络中的每个节点都看成独立的小社团。然后考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪婪原则，选取使模块度增长最大或者减小最少的两个社团，将它们合并成一个社团。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社团划分就视为最优社团划分。

贪婪算法FN具体步骤：

贪婪算法FN具体步骤：

# 去掉网络中所有的边，网络的每个节点都单独作为一个社团；

# 去掉网络中所有的边，网络的每个节点都单独作为一个社团；