基于向量划分的复杂网络社区结构发现
摘要
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.