基于向量划分的复杂网络社区结构发现

摘要：

社区结构是复杂网络最重要的结构特性之一,通过优化模块度来进行社区结构发现是目前使用最为广泛的一类方法.通过将网络看做有向图,模块度矩阵可表示为顶点的有向边向量表示的交叉协方差矩阵,但是该矩阵不是正定的.现有方法通过对该矩阵的进行谱分解,提取大于零的特征根对应的成分,将社区发现问题描述为向量划分问题.本文通过修正交叉协方差矩阵的对角线,使之满足正定性条件,将其表示为顶点向量的内积矩阵.因此,无须对模块度矩阵进行谱分解,甚至无须显式计算顶点的表示向量,就可以将基于模块度的社区发现问题重构为一个向量划分问题.进一步,从向量划分的角度解释了有限分辨率现象的根源,设计了以最大化向量夹角为指导的贪婪算法,该方法比直接优化模块度的方法有更高的异质社区分辨能力.在合成网络和真实网络上分别进行了实验验证,实验结果证实了所提方法的可行性和有效性.

关键词：复杂网络、社区发现、有限分辨率现象、向量划分、聚类分析

所属期刊栏目：41

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2012-02-21（万方平台首次上网日期，不代表论文的发表时间）

页码：1063-1074