763
个编辑
更改
无编辑摘要
|description=模块度，集智，社团结构检测算法
|description=模块度，集智，社团结构检测算法
}}
}}
'''模块度 Modularity'''是对网络结构或图像结构的一种度量。它是一种衡量网络模板（也称为节点集或社团）划分质量的标准。如果模板度高，则说明节点集内部连接紧密，而节点集与节点集之间连接稀疏。模块度是检测[[社团结构 Community Structure]]的常用优化方法。不过，受分辨率的限制，该方法不适用于检测小社团。
'''模块度 Modularity'''是对网络结构或图像结构的一种度量。它是一种衡量网络模板（也称为节点集或社团）划分质量的标准。如果模板度高，则说明节点集内部连接紧密，而节点集与节点集之间连接稀疏。模块度是检测[[社团结构 Community Structure]]的常用优化方法。不过，受分辨率的限制，该方法不适用于检测小社团。
==起源==
==起源==
模块度 = 落在同一组的边的比例 —对这些边进行随机分配所得到的期望概率（将边随机分配是为了保持每个节点的节点度不变）。其中，落在同一组的边的比例=组内的总边数÷网络中的总边数。无权图和无向图的模块度取值都在<math>[-1/2,1]</math>范围内。如果节点组中的连边数量超过了随机分配时所得到的期望连边数量，模块度为正数。没有超过，则为负数。将给定网络的节点划分为若干模块，模块度反映的是模块内部连边的集中程度，而不是各模块之间所有节点链路的随机分布情况。
模块度 = 落在同一组的边的比例 ，即对这些边进行随机分配所得到的期望概率（将边随机分配是为了保持每个节点的节点度不变）。其中，落在同一组的边的比例=组内的总边数÷网络中的总边数。无权图和无向图的模块度取值都在<math>[-1/2,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>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>.
将图网络的邻接矩阵表示为 <math>A</math>.
<math>A_{{vw}}=0</math>意味着节点<math>v</math> 和<math>w</math> 之间没有连边；<math>A_{vw} = 1</math>则意味着节点v和节点w之间存在连边。
<math>A_{{vw}}=0</math>意味着节点<math>v</math> 和<math>w</math> 之间没有连边；<math>A_{vw} = 1</math>则意味着节点v和节点w之间存在连边。
模块度Q可定义为：在具有与给定网络相同度序列的随机化网络中，模板度等于在落在社团1或社团2中连边的比例—在社团1和社团2中将连边随机分布后所得到的概率期望。
===两个节点间随机连边的概率期望求法===
===两个节点间随机连边的概率期望求法===
配置模型是一个特定网络的随机实现，我们利用配置模型的相关定义来计算连边随机分布后的概率期望。给定一个具有 <math>n</math>个节点的网络，其中设每个节点<math>v</math>的节点度为 <math>k_v</math>，配置模型将每个连边切断并一分为二，切断的点称为末梢点。然后每一条半边（称为存根）随机与其他半边（除了自身）随机相连变成一条完整连边，并允许出现同一节点自我相连成环、两个节点间存在多条连边的情况。因此，即使网络的节点度序列保持不变，配置模型仍然是一个完全随机的网络。
配置模型是一个特定网络的随机实现，我们利用配置模型的相关定义来计算连边随机分布后的概率期望。给定一个具有 <math>n</math>个节点的网络，其中设每个节点<math>v</math>的节点度为 <math>k_v</math>，配置模型将每个连边切断并一分为二，切断的点称为末梢点。然后每一条半边（称为存根）随机与其他半边（除了自身）随机相连变成一条完整连边，并允许出现同一节点自我相连成环、两个节点间存在多条连边的情况。因此，即使网络的节点度序列保持不变，配置模型仍然是一个完全随机的网络。
现考虑节点v和节点w，各自的节点度分别为 <math>k_v</math>和<math>k_w</math>，在随机重新连边的网络中，利用上述方法计算这两个节点间所期望的完整连边数量。
现考虑节点v和节点w，各自的节点度分别为 <math>k_v</math>和<math>k_w</math>，在随机重新连边的网络中，利用上述方法计算这两个节点间所期望的完整连边数量。
其中，所有单边的数量为
其中，所有单边的数量为<math>l = \sum_{u} k_{u} =2m</math>
<math>
l = \sum_{u} k_{u} =2m</math>
对于有着大量连边的随机化网络，我们进行以下处理：当m很大时，我们将分母''2m-1''化简为''2m''，即利用 <math>\frac{k_v k_w}{2m}</math> 近似计算两个节点之间所期望的连边数量。此外，如果随机化网络的规模十分大，忽略发生同一节点自我相连成环、两个节点间存在多条连边的情况。我们设两个节点之间最多只有一条连边，此时 <math>J_{vw}</math> 变成二进制指示符变量，其期望值为 <math>J_{vw}=1</math>的概率。<br>
对于有着大量连边的随机化网络，我们进行以下处理：当m很大时，我们将分母''2m-1''化简为''2m''，即利用 <math>\frac{k_v k_w}{2m}</math> 近似计算两个节点之间所期望的连边数量。此外，如果随机化网络的规模十分大，忽略发生同一节点自我相连成环、两个节点间存在多条连边的情况。我们设两个节点之间最多只有一条连边，此时 <math>J_{vw}</math> 变成二进制指示符变量，其期望值为 <math>J_{vw}=1</math>的概率。<br>
这意味着，在节点v和节点w之间存在连边的期望概率为<math>\frac{k_v k_w}{2m}</math>。
这意味着，在节点v和节点w之间存在连边的期望概率为<math>\frac{k_v k_w}{2m}</math>。
因此，节点<math>v</math>和节点<math>w</math>之间的实际边数与它们在随机化网络下连边数的期望之差为<br>
因此，节点<math>v</math>和节点<math>w</math>之间的实际边数与它们在随机化网络下连边数的期望之差为<br>
<math>A_{vw} - \frac{k_v k_w}{2m}</math>
<math>A_{vw} - \frac{k_v k_w}{2m}</math>
===公式表达一===
===公式表达一===
按照模块度的定义，对于所有的节点对进行求和，即得模块度的计算公式为：
按照模块度的定义，对于所有的节点对进行求和，即得模块度的计算公式为：
<br>
<br>
<math>Q = \frac{1}{2m} \sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{2m} \right] \frac{s_{v} s_{w}+1}{2}
<math>Q = \frac{1}{2m} \sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{2m} \right] \frac{s_{v} s_{w}+1}{2}
</math>只适用于将网络划分为两个社团的情况。将网络划分为两个社团，再将每个子社团进一步划分为两个较小的子社团，使得模块度达到最大化的划分方法称为层次划分。层次划分是一个能够识别网络中多个社团的可行方法。通常设将网络划分为c个社团。
</math>只适用于将网络划分为两个社团的情况。将网络划分为两个社团，再将每个子社团进一步划分为两个较小的子社团，使得模块度达到最大化的划分方法称为层次划分。层次划分是一个能够识别网络中多个社团的可行方法。通常设将网络划分为c个社团。
===公式表达二===
===公式表达二===
模块度可以表示为
模块度可以表示为
[[File:EF[@C1SZ(8R)_T_K_VM%T`2.png|200px|left]]
[[File:EF[@C1SZ(8R)_T_K_VM%T`2.png|200px|left]]
其中：Avw为共引网络相邻矩阵的一个元素；k<sub>v</sub>为节点v 的度；m为网络中的连边总数；c<sub>v</sub>为节点<math>v</math>被分配到的社团，如果c<sub>v</sub>=c<sub>w</sub>，则函数（c<sub>v</sub>，c<sub>w</sub>）为1，否则为0。函数Q最大化即可得到最优社团划分。注意：γ是Q中的分辨率参数，标准模块函数中的γ=1。较大的γ参数可检测出较小但较多的社团，较小的γ参数可检测出较大但较少的社团。需要说明的是，虽然社团数量的分布受到参数γ的影响，但动力学特性的显示几乎与社团分辨率无关。（摘自集智俱乐部微信公众号文章《[https://mp.weixin.qq.com/s/ZOI-ItIstrqTCHs1QKWUUg Nature通讯：科学家兴趣转移愈发频繁，但对科研生涯可能不利]》）
其中：Avw为共引网络相邻矩阵的一个元素；k<sub>v</sub>为节点v 的度；m为网络中的连边总数；c<sub>v</sub>为节点<math>v</math>被分配到的社团，如果c<sub>v</sub>=c<sub>w</sub>，则函数（c<sub>v</sub>，c<sub>w</sub>）为1，否则为0。函数Q最大化即可得到最优社团划分。注意：γ是Q中的分辨率参数，标准模块函数中的γ=1。较大的γ参数可检测出较小但较多的社团，较小的γ参数可检测出较大但较少的社团。需要说明的是，虽然社团数量的分布受到参数γ的影响，但动力学特性的显示几乎与社团分辨率无关。（摘自集智俱乐部微信公众号文章《[https://mp.weixin.qq.com/s/ZOI-ItIstrqTCHs1QKWUUg Nature通讯：科学家兴趣转移愈发频繁，但对科研生涯可能不利]》）
在标准模块函数中，γ=1，则有
在标准模块函数中，γ=1，则有
<br>
<br>
<math>
<math>
定义 eij为连接社团 i 和 社团j 的连边总数，则有<br>
定义 <math>e_{ij}</math>为连接社团 i 和 社团j 的连边总数，则有<br>
<math>
<math>
e_{ij}= \sum_{vw} \frac{A_{vw}}{2m} 1_{v\in c_i} 1_{w\in c_j}
e_{ij}= \sum_{vw} \frac{A_{vw}}{2m} 1_{v\in c_i} 1_{w\in c_j}
</math>
</math>
<math>a_i</math>表示连接到社区i的连边总数，则有<math>
a_i=\frac{k_i}{2m}
a_i=\frac{k_i}{2m}
= \sum_{j} e_{ij}
= \sum_{j} e_{ij}
===公式表达三===
===公式表达三===
模块度的另一种计算公式为<br>
模块度的另一种计算公式为<br>
<math>
<math>
= \frac{1}{2m} \mathrm{Tr}(\mathbf{S}^\mathrm{T}\mathbf{BS}),
= \frac{1}{2m} \mathrm{Tr}(\mathbf{S}^\mathrm{T}\mathbf{BS}),
</math>
</math>
在光谱优化算法中常被用到。如果节点 v属于节点组r 则定义Svr=1，若不属于则为0。之后利用该公式进行代换计算 <br>
在光谱优化算法中常被用到。如果节点 v属于节点组r 则定义Svr=1，若不属于则为0。之后利用该公式进行代换计算 <br>
<math>
<math>
</math>
</math>
其中，s为包含s<sub>v</sub>的列向量。
其中，s为包含s<sub>v</sub>的列向量。
该函数与辛流形的'''汉密尔顿函数 Hamiltonian'''的形式相同，故可创建出简单的算法，例如使用'''模拟退火算法 Simulated Annealing'''来使模块度最大化。 模块化的一般形式等价于一个 Potts 自旋玻璃，在这种情况下也可以发展类似的算法。
该函数与辛流形的'''汉密尔顿函数 Hamiltonian'''的形式相同，故可创建出简单的算法，例如使用'''模拟退火算法 Simulated Annealing'''来使模块度最大化。 模块化的一般形式等价于一个 Potts 自旋玻璃，在这种情况下也可以发展类似的算法。
==多社团检测实例==
==多社团检测实例==
我们考虑一个有10个节点和12条边的无向网络，下面是'''邻接矩阵 Adjacency Matrix'''。
我们考虑一个有10个节点和12条边的无向网络，下面是'''邻接矩阵 Adjacency Matrix'''。
[[File:QQ图片20200324150722.png|400px|left]]
[[File:QQ图片20200324150722.png|400px|left]]
[[File:Partitioned_network.jpg|200px|thumb|upright=3|图1. 对应于10个节点，12条边的邻接矩阵网络示意图|right]]
[[File:Partitioned_network.jpg|200px|thumb|upright=3|图1. 对应于10个节点，12条边的邻接矩阵网络示意图|right]]
[[File:Sample_Network.jpg|200px|thumb|upright=3|图2. 将模块度Q最大化的网络分区（其中Q=0.4896） |right]]
[[File:Sample_Network.jpg|200px|thumb|upright=3|图2. 将模块度Q最大化的网络分区（其中Q=0.4896） |right]]
==多分辨率算法==
==多分辨率算法==
在利用模块度衡量社团划分质量的过程中，有两种主要的解决分辨率限制的方法: 在每个节点上以自循环的形式增加一个阻力 r，通过增加或减少坏节点形成社团; 或在模块化定义的空格项前加上一个参数γ>0，该参数控制社区内部链接与零模型之间的相对重要性。 将这些参数值的模块度优化到适当的范围内，就有可能恢复整个网络的中尺度，从宏观尺度上所有节点属于同一个社团,从微观尺度上每个节点都形成自己的社团,因而将其命名为多分辨率算法。 然而，当社团之间的规模差异很大时，这些算法也有局限性。
==分辨率限制==
==分辨率限制==
将一个给定网络与该网络相对应的随机零模型进行对比，随机模型通常具有相同度序列、且其连边随机连接。模块度通过比较社团内部的连边数量与所期望的连边数量来判断给定网络是否具有较强的社团结构。（参考网络科学导论。）这个随机零模型隐含地假设每个节点可以连接到网络的任何其他节点。 然而，如果网络规模非常大，这种假设是不合理的。因为通过一个节点的视角看到了网络的一小部分，却忽略了网络的大部分。 这说明随着网络规模的增大，两组节点之间的期望边数会减少。 因此，如果网络足够大，模块化零模型中两组节点集之间的期望边数可能小于一条。 在该种情况下，模块度将两组节点集之间存在单边作为节点集之间强相关性的标志。若对模块度进行优化，将导致两组节点集的合并，独立于社团群众。 因此，即使是内部连边密度最高、可识别性最好的弱互联完全图，在网络规模足够大的情况下，也可以通过模块度优化进行合并。 因此，即使小型社团能够被准确定义，在大型网络中优化模块度的方法也并不适用于他们。 对于依赖全局零模型的模块度优化方法来说，这种偏差是不可避免的。
==模块度最大化算法==
==模块度最大化算法==
由于网络所有可能的社团划分方法十分多，假设网络的节点数和边数分别为n和m，则所有可能的社团划分数是一个以n为指数的数。因此，'''NP-hard问题'''被提出，其研究如何在所有可能的划分中找出最优划分。针对这一问题，目前一些相应算法已被提出，其可以在合理的时间内找出模块度最大化的近似最优划分。
===经典贪婪算法===
===经典贪婪算法===
模块度最大化问题是一个经典的最优化问题，'''马克·纽曼 Mark NewMan '''基于贪婪思想提出了模块度最大化的贪心算法FN 。贪婪思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题。找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。初始时，FN算法将网络中的每个节点都看成独立的小社团。然后考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪婪原则，选取使模块度增长最大或者减小最少的两个社团，将它们合并成一个社团。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社团划分就视为最优社团划分。
模块度最大化问题是一个经典的最优化问题，'''马克·纽曼 Mark NewMan '''基于贪婪思想提出了模块度最大化的贪心算法FN 。贪婪思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题。找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。初始时，FN算法将网络中的每个节点都看成独立的小社团。然后考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪婪原则，选取使模块度增长最大或者减小最少的两个社团，将它们合并成一个社团。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社团划分就视为最优社团划分。
贪婪算法FN具体步骤：
贪婪算法FN具体步骤：
#遍历每种社区划分对应的模块度值，选取模块度最大的社区划分作为网络的最优划分。
#遍历每种社区划分对应的模块度值，选取模块度最大的社区划分作为网络的最优划分。
该算法中，需要注意的是，每次加入的边只是影响网络的社团划分。而每次计算网络划分的模块度时，都是在网络完整的拓扑结构上进行的，即网络所有的边都存在的拓扑结构上。
该算法中，需要注意的是，每次加入的边只是影响网络的社团划分。而每次计算网络划分的模块度时，都是在网络完整的拓扑结构上进行的，即网络所有的边都存在的拓扑结构上。
===快速模块度优化算法===
===快速模块度优化算法===
*[http://arxiv.org/abs/1908.04653 使用多层网络上的模块化 信念传播检测显著的社区结构]
*[http://arxiv.org/abs/1908.04653 使用多层网络上的模块化 信念传播检测显著的社区结构]
'''''本中文词条由[[趣木木]]用户参与编译，[[刘佩佩]]用户审校，欢迎在讨论页面留言'''''
----
'''''本中文词条由[[趣木木]]用户参与编译，[[刘佩佩]]用户审校，[[用户:乐多多|乐多多]]编辑，欢迎在讨论页面留言'''''
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[Category:网络]]
[[Category:社团结构]]