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

Complex networks community structure detection based on vector partition

作　　者：刘旭[1] 易东云[1] 

机构地区：[1]国防科学技术大学理学院数学与系统科学系,长沙410073

出　　处：《中国科学：物理学、力学、天文学》2011年第9期1063-1074,共12页Scientia Sinica Physica,Mechanica & Astronomica

基　　金：国家自然科学基金资助项目(批准号:60902089;61005003)

摘　　要：社区结构是复杂网络最重要的结构特性之一,通过优化模块度来进行社区结构发现是目前使用最为广泛的一类方法.通过将网络看做有向图,模块度矩阵可表示为顶点的有向边向量表示的交叉协方差矩阵,但是该矩阵不是正定的.现有方法通过对该矩阵的进行谱分解,提取大于零的特征根对应的成分,将社区发现问题描述为向量划分问题.本文通过修正交叉协方差矩阵的对角线,使之满足正定性条件,将其表示为顶点向量的内积矩阵.因此,无须对模块度矩阵进行谱分解,甚至无须显式计算顶点的表示向量,就可以将基于模块度的社区发现问题重构为一个向量划分问题.进一步,从向量划分的角度解释了有限分辨率现象的根源,设计了以最大化向量夹角为指导的贪婪算法,该方法比直接优化模块度的方法有更高的异质社区分辨能力.在合成网络和真实网络上分别进行了实验验证,实验结果证实了所提方法的可行性和有效性.Community structure is the most notable topological feature of complex networks and the modularity optimization is the most prevailing community detection method.By treating the network as directed graph,we reformulate the modularity matrix as cross-covariance of vertex vectors taking directed edges as their basis.However the modularity matrix is not positive defined.The existing method treated community detection as a vector partition problem by spectral decomposition of modularity matrix,using only a few leading positive eigenvalues and the corresponding vectors.In this paper the diagonal of cross-covariance matrix is modified to make the matrix positive defined,and then factored into inner product of vertex vectors.Thus transform the community detection problem as a vector partition problem.We then show that the vector partition problem can be solved without decomposing the modularity matrix or even computing the vertex vector explicitly either.From the vector partition point of view,the resolution limit of modularity is reinterpreted.A greedy algorithm based on merging vectors with least angle is designed.The proposed method is less resolution limited than modularity optimizing methods.Experiments on synthesized and real world networks verify the feasibility and validity of the proposed method.

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

分 类 号：O157.5[理学—数学]