社区发现(四)：模块度

而非重叠社区发现中的另一种经典的算法就是基于模块度的社区发现算法。
接下来，我们将首先介绍模块度的概念，为基于模块度的社区发现算法打好基础。

模块度：
    我们可以发现，在标签传播算法中，即使社区找到了，但是没有指标能够衡量社区发现的好坏，
    仅仅是根据一定的更新原则更新到网络收敛为止。由于该算法随机性强，很容易出现执行多次的结果各不相同，难以收敛稳定。
    为了评价社区发现的优劣，Newman等人提出了模块度的概念，用模块度来衡量社区划分的好坏。
    一个相对好的结果，就是社区内部节点连接更为稠密，社区间连接更为稀疏，此时的模块度会更大。
    这样就将社区发现问题转换为最大化网络模块度问题。

模块度公式： 社区内边数的比例（各个社区内边数累计求和/整个网络的总边数）- 社区内节点产生边数的期望（随机网络下同样的社区的期望边数）。
该公式分为2部分：
     第一部分：社区内边数的比例：各个社区内边数累计求和/整个网络总边数
     第二部分：社区内节点产生边数的期望
     
模块度第一版定义：
复制代码

从上图中总结出来的模块度的公式为：
     Q = (各个社区内的边累计求和*2 / 整个网络的边*2) - [ (各个社区内的边*2+与其他社区的边*1)/整个网络的边*2 ]的平方
     
模块度的第二版定义：
复制代码

     惊喜的是，虽然初始的定义不同，但是通过推导，我们发现版本一和版本二的结果完全一致。仔细一想，我们可以发现社区内的边数之和其实就是社区矩阵的迹，而随机网络下的同社区中总的期望边数也等价于该社区内的总度数的平方（为保证网络结构稳定，节点的度数必须要有边承载，而一条边必须要承接两个节点的度数，所以是平方）。

模块度的值域
    模块度的值域是一个左闭右开的区间：[-1/2,1) 
    
模块度的用处
    模块度的定义既然可以用来评价社区划分的好坏，那么就可以用作优化函数。
    当某个节点加入一个社区时，整个网络的模块度提升了，说明此次划分是有效的。这一点很像机器学习中的损失函数和熵增益。一旦这个指标能够作为优化函数进行衡量结果的好坏，那么围绕着最大化这个优化函数就会出现各式各样的算法。
复制代码