王学凯 马英红

山东师范大学管理科学与工程学院 山东 250014

0 引言

复杂网络的特征和性质在近些年来已经成为研究的热点。对社团结构的研究对于理解和分析网络结构及其功能有着至关重要的作用已广泛应用到生物学、计算机科学、社会学等领域中。社团结构是指其社团内部节点连接紧密，社团之间连接相对稀疏的一种结构。许多研究人员从不同角度出发提出了划分社团算法，例如Kernighan-Lin算法，Kernighan算法是一种基于贪婪算法原理将网络分割为两个大小已知的社团的二分法，但该算法必须已知网络社团的确切规模才能得以应用；基于Laplace图特征值的谱平分法，利用网络结构的Laplace矩阵中不为零的特征值所对应的特征向量，和同一个社团内的节点对应的元素近似相等的原理对网络社团进行划分，在规模为n个节点的网络中，该算法的复杂度为O(n3)；GN算法通过从网络中移除介数最大的边将整个网络分成越来越小的部分，其不足在于对网络社团划分优劣没有一个定量描述。Newman等人经过研究提出了一种度量网络社团划分质量的标准，成功地解决了这个问题。Wu和Huberman提出了基于电阻网络电压谱的快速分割算法，该方法须已知分属于不同社团的两个节点。Newman义了模块度Q，用来衡量网络划分质量，Q值越大，说明划分结果越好。Clauset等通过节点的局部信息，提出局部模块度，该方法的优点是计算量比较小。在很多情况下，研究人员关注的是网络的局部社团结构。……