关键词: 代数连通性, 谱优化, 拉普拉斯矩阵, 割边

Abstract: The GN algorithm removes one edge with the highest betweenness at each iteration. It has relatively high time complexity. Although the time complexity of variations on GN is reduced, the calculation accuracy needs to be improved. In complex network graph, the second smallest eigenvalue of Laplacian matrix is the?algebraic connectivity. It presents greedy spectral optimal cut model by minimizing the algebraic connectivity of complex network. The model cuts k edges at an iteration based on GN algorithm. To avoid edges overcutting, the weight is set up for each edge. It proposes edge centrality cut model in order to reduce the time complexity further, which is different from the shortest distance and random walking methods. The model calculates edge centrality by the spectral analysis and can be used in medium-size networks with higher efficiency and accuracy.

Key words: algebraic connectivity, spectrum optimization, Laplascian matrix, cut edge