763
个编辑
更改
跳到导航
跳到搜索
第25行：
第25行： − 模块度Q可定义为：在具有与给定网络相同度序列的随机化网络中，模板度等于在落在社团1或社团2中连边的比例—在社团1和社团2中将连边随机分布后所得到的概率期望。+ 第32行：
第32行： − 现考虑节点v和节点w，各自的节点度分别为 <math>k_v</math>和<math>k_w</math>，在随机重新连边的网络中，利用上述方法计算这两个节点间所期望的完整连边数量。+ − + 第46行：
第46行： − 对于有着大量连边的随机化网络，我们进行以下处理：当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>。 + − <br>+ − 第65行：
第64行： − + − 其中：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，则有:+ − + − 第80行：
第78行： − + − + + 第91行：
第90行： − + − + 第98行：
第97行： − + − + + + + − 其中S是包含元素Svr 的矩阵（非方阵），而B是包含元素<math>B_{vw} = A_{vw} - \frac{k_v k_w}{2m}</math>的模块化矩阵。由于模块化矩阵的所有行和列都为0，因此也可以说不可分割的网络模块度为0。利用sv = ±1代表节点v所属于哪个节点组，我们有:<br>+ − + − 其中，s为包含s<sub>v</sub>的列向量。+
→模块度的计算方法
模块度<math>Q</math>可定义为：在具有与给定网络相同度序列的随机化网络中，模板度等于在落在社团1或社团2中连边的比例—在社团1和社团2中将连边随机分布后所得到的概率期望。
现考虑节点<math>v</math>和节点<math>w</math>，各自的节点度分别为 <math>k_v</math>和<math>k_w</math>，在随机重新连边的网络中，利用上述方法计算这两个节点间所期望的完整连边数量。
其中，所有单边的数量为
其中，所有单边的数量为
:<math>l = \sum_{u} k_{u} =2m</math>
:<math>l = \sum_{u} k_{u} =2m</math>
我们考虑有<math>k_v</math> 条半边的节点<math>v</math> ，并设一个相关指示变量<math>I_i</math>，其中。在给定<math>i = 1, \ldots, k_v</math>的随机化网络中，节点<math>v</math>的第<math>i</math>条半边恰好连接到节点<math>w</math>（具有<math>k_w</math>条半边）的某条半边，此时<math>I_i = 1</math>。如果没有连接到，则<math>I_i = 0</math>。因为节点v的第i条半边可以等概率连接到剩下的任何 <math>2m-1</math>条半边，且<math>k_w</math>条半边也可以自我连接到节点w。
我们考虑有<math>k_v</math> 条半边的节点<math>v</math> ，并设一个相关指示变量<math>I_i</math>，其中。在给定<math>i = 1, \ldots, k_v</math>的随机化网络中，节点<math>v</math>的第<math>i</math>条半边恰好连接到节点<math>w</math>（具有<math>k_w</math>条半边）的某条半边，此时<math>I_i = 1</math>。如果没有连接到，则<math>I_i = 0</math>。因为节点v的第i条半边可以等概率连接到剩下的任何 <math>2m-1</math>条半边，且<math>k_w</math>条半边也可以自我连接到节点<math>w</math>。
故可用公式：
故可用公式：
:<math>p(I_i = 1) = E[I_i] = \frac{k_w}{2m-1}</math>
:<math>p(I_i = 1) = E[I_i] = \frac{k_w}{2m-1}</math>
对于有着大量连边的随机化网络，我们进行以下处理：当<math>m</math>很大时，我们将分母''<math>2m-1</math>''化简为''<math>2m</math>''，即利用 <math>\frac{k_v k_w}{2m}</math> 近似计算两个节点之间所期望的连边数量。此外，如果随机化网络的规模十分大，忽略发生同一节点自我相连成环、两个节点间存在多条连边的情况。我们设两个节点之间最多只有一条连边，此时 <math>J_{vw}</math> 变成二进制指示符变量，其期望值为 <math>J_{vw}=1</math>的概率。这意味着，在节点v和节点w之间存在连边的期望概率为<math>\frac{k_v k_w}{2m}</math>。
因此，节点<math>v</math>和节点<math>w</math>之间的实际边数与它们在随机化网络下连边数的期望之差为<math>A_{vw} - \frac{k_v k_w}{2m}</math>。
因此，节点<math>v</math>和节点<math>w</math>之间的实际边数与它们在随机化网络下连边数的期望之差为<math>A_{vw} - \frac{k_v k_w}{2m}</math>。
===公式表达一===
===公式表达一===
按照模块度的定义，对于所有的节点对进行求和，即得模块度的计算公式为：
按照模块度的定义，对于所有的节点对进行求和，即得模块度的计算公式为：
:<math>
<math>
Q = \frac{1}{2m} \sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{2m} \right] \frac{s_{v} s_{w}+1}{2}
Q = \frac{1}{2m} \sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{2m} \right] \frac{s_{v} s_{w}+1}{2}
</math>
</math>
===公式表达二===
===公式表达二===
模块度可以表示为:<br>
模块度可以表示为:<br>
<math>Q = \frac{1}{2m} \sum_{vw} \left[ A_{vw} - γ\frac{k_v k_w}{2m}\right] \delta(c_{v}, c_{w})
:<math>Q = \frac{1}{2m} \sum_{vw} \left[ A_{vw} - \gamma\frac{k_v k_w}{2m}\right] \delta(c_{v}, c_{w})
</math>
</math>
其中：<math>Avw</math>为共引网络相邻矩阵的一个元素；<math>k_v</math>为节点<math>v </math>的度；<math>m</math>为网络中的连边总数；<math>c_v</math>为节点<math>v</math>被分配到的社团，如果<math>c_v=c_w</math>，则函数<math>（c_v，c_w）</math>为1，否则为0。函数<math>Q</math>最大化即可得到最优社团划分。注意：<math>\gamma</math>是<math>Q</math>中的分辨率参数，标准模块函数中的<math>\gamma=1</math>。较大的<math>\gamma</math>参数可检测出较小但较多的社团，较小的<math>\gamma</math>参数可检测出较大但较少的社团。需要说明的是，虽然社团数量的分布受到参数<math>\gamma</math>的影响，但动力学特性的显示几乎与社团分辨率无关。（摘自集智俱乐部微信公众号文章《[https://mp.weixin.qq.com/s/ZOI-ItIstrqTCHs1QKWUUg Nature通讯：科学家兴趣转移愈发频繁，但对科研生涯可能不利]》）
在标准模块函数中，<math>γ=1</math>，则有:
<br>
:<math>
<math>
Q = \frac{1}{(2m)}\sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{(2m)} \right] \delta(c_{v}, c_{w})
Q = \frac{1}{(2m)}\sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{(2m)} \right] \delta(c_{v}, c_{w})
=\sum_{i=1}^{c} (e_{ij}-a_{i}^2)
=\sum_{i=1}^{c} (e_{ij}-a_{i}^2)
定义 <math>e_{ij}</math>为连接社团 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>
<math>a_i</math>表示连接到社区i的连边总数，则有
:<math>
a_i=\frac{k_i}{2m}= \sum_{j} e_{ij}
a_i=\frac{k_i}{2m}= \sum_{j} e_{ij}
</math>
</math>
===公式表达三===
===公式表达三===
模块度的另一种计算公式为:<br>
模块度的另一种计算公式为:
<math>
:<math>
Q = \frac{1}{2m} \sum_{vw} \sum_r \left[ A_{vw} - \frac{k_v k_w}{2m} \right] S_{vr} S_{wr}
Q = \frac{1}{2m} \sum_{vw} \sum_r \left[ A_{vw} - \frac{k_v k_w}{2m} \right] S_{vr} S_{wr}
= \frac{1}{2m} \mathrm{Tr}(\mathbf{S}^\mathrm{T}\mathbf{BS}),
= \frac{1}{2m} \mathrm{Tr}(\mathbf{S}^\mathrm{T}\mathbf{BS}),
在光谱优化算法中常被用到。如果节点 v属于节点组r 则定义Svr=1，若不属于则为0。之后利用该公式进行代换计算: <br>
在光谱优化算法中常被用到。如果节点<math>v</math>属于节点组<math>r</math> 则定义<math>Svr=1</math>，若不属于则为0。之后利用该公式进行代换计算:
<math>\delta(c_v,c_w) = \sum_r S_{vr} S_{wr}</math>
:<math>\delta(c_v,c_w) = \sum_r S_{vr} S_{wr}</math>
其中<math>S</math>是包含元素<math>Svr</math>的矩阵（非方阵），而<math>B</math>是包含元素<math>B_{vw} = A_{vw} - \frac{k_v k_w}{2m}</math>的模块化矩阵。
由于模块化矩阵的所有行和列都为0，因此也可以说不可分割的网络模块度为0。利用<math>sv = ±1</math>代表节点<math>v</math>所属于哪个节点组，我们有:
<math>Q = {1\over 4m} \sum_{vw} B_{vw} s_v s_w = {1\over 4m} \mathbf{s}^\mathrm{T}\mathbf{Bs}</math>
:<math>Q = {1\over 4m} \sum_{vw} B_{vw} s_v s_w = {1\over 4m} \mathbf{s}^\mathrm{T}\mathbf{Bs}</math>
其中，<math>s</math>为包含</math>s_v</math>的列向量。