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

摘要：

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

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

分类号：TP393(计算技术、计算机技术)

资助基金：天津财经大学科研发展基金项目No.Y1211；天津市高等学校科技发展基金计划项目No.20120817。

在线出版日期：2014-06-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：135-138