用R语言和python进行社交网络中的社区检测

模块度定义其实很好理解，我们可以根据一个网络的空模型去进行理解。网络的空模型可以理解为只有节点的而没有连边，这时候一个节点可以和图中的任意其他节点相连，并且节点 i $i$和 j $j$相连的概率可以通过计算得到。随机选择一个节点与节点 i $i$相连的概率为 kj/2m $k_j/2m$，随机选择一个节点与节点 j $j$相连的概率为 kj/2m $k_j/2m$，那么节点 i $i$和节点 j $j$相连的概率为 pipj=kikj/(4m2) $p_i{p}_j=k_i{k}_j/(4m^2)$，边数的期望值 Pij=2mpipj=kikj/(2m) $P_{ij}=2m{p}_i{p}_j=k_i{k}_j/(2m)$。所以模块度其实就是指一个网络在某种社区划分下与随机网络的差异，因为随机网络并不具有社区结构，对应的差异越大说明该社区划分越好。

　　Newman提出的模块度具有两方面的意义：

　　（1）模块度的提出成为了社区检测评价一种常用指标，它是度量网络社区划分优劣的量化指标；

　　（2）模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。在模块度的基础之上，许多优化算法以模块度为优化的目标方程进行优化，从而使得目标函数达到最大时得到不错的社区划分结果。

　　当然，模块度的概念不是绝对合理的，它也有弊端，比如分辨率限制问题等，后期国内学者在模块度的基础上提出了模块度密度的概念，可以很好的解决模块度的弊端，这里就不详细介绍了。

　　常用的社区检测方法主要有如下几种：

　　（1）基于图分割的方法，如Kernighan-Lin算法，谱平分法等；

　　（2）基于层次聚类的方法，如GN算法、Newman快速算法等；

　　（3）基于模块度优化的方法，如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等。