计算机应用与软件2013，Vol.30Issue(2)：141-143,167,4.DOI:10.3969/j.issn.1000-386x.2013.02.036
基于代数连通性的复杂网络社区发现研究
ON COMMUNITY DETECTION OF COMPLEX NETWORKS BASED ON ALGEBRAIC CONNECTIVITY
摘要
Abstract
The algebraic connectivity of networks is the second smallest eigenvalue of Laplacian matrix and can be used to measure to which extent the network is connected. To meliorate the time complexity of complex network segmentation algorithm, we present a spectrum optimisation model based on algebraic connectivity and apply it in small community detection of complex networks. The model chooses the edges set to be deleted from candidate edges sets by minimizing the networks connectivity function. Though this convex optimisation problem can be solved by semi-definite program, but its high time complicity can only deal with the complex networks in moderate size. We use greedy policy optimisation approach for solving this model optimisation issue, and enable the algorithm to be able to apply to large scale complex network. On the other hand, the edges of community boundary have bad influence upon optimised result of algebraic connectivity function, so we add a weight on each edge based on Fielder vector, thus this problem is solved effectively. In test part, the model is applied to simulated complex network and real complex network for verification. The results show that the model effectively reduces the iteration times of GN algorithm, and thereby reduces its time complex as well and keeps the segmentation results effectively too.关键词
矩阵的谱/拉普拉斯矩阵/费德勒向量/边中心性/社区模块系数Key words
Spectrum of a matrix/Laplace matrix/Fielder vector/Edge centrality/Modularity parameter of communication分类
信息技术与安全科学引用本文复制引用
张烁,赵福强,阮兴茂,李竞飞..基于代数连通性的复杂网络社区发现研究[J].计算机应用与软件,2013,30(2):141-143,167,4.基金项目
国家教育部人文社科青年基金项目(08JC870008). （08JC870008）
