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

• 作者: 何丽 张烁 赵富强 邢恩军
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 代数连通性 谱优化 拉普拉斯矩阵 割边
• 年，卷（期）: 2014,（11）
• 所属期刊栏目: 网络、通信、安全
• 页码范围: 135-138
• 页数: 4页
• 分类号: TP393
• 字数: 3485字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1301-0292

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何丽	天津财经大学理工学院信息科学与技术系	25	161	7.0	12.0
2	邢恩军	天津财经大学理工学院信息科学与技术系	4	17	2.0	4.0
3	赵富强	天津财经大学理工学院信息科学与技术系	18	159	6.0	12.0
4	张烁	天津财经大学理工学院信息科学与技术系	1	2	1.0	1.0