基于代数连通性的复杂网络割边模型研究

Research of complex network cut edge model based on algebraic connectivity

传统的GN算法每次迭代删除一条边,时间复杂度高,其变种时间复杂度有所下降,但分割精度也有待于提高;在复杂网络图中,图的连通性是由拉普拉斯矩阵的第二小特征值决定的,通过最小化网络连通性,提出了贪婪谱优化割边模型,该模型在GN算法基础上,一次删除多条边,为避免出现边过度分割,每条边设置了权重;为了进一步降低时间复杂度,选择网络代数连通性下降最快的边进行删除,提出了基于边中心性测度的割边模型,与传统的利用最短距离和随机游走不同,模型采取谱分析方法对每条边定义边中心性测度,速度更快,分割精度能到达要求,适合处理中规模社区结构。

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.