面向复杂网络的图稀疏算法综述

摘要：

大规模数据下复杂网络的算法分析面临复杂度高的挑战,为此引入图稀疏的思想,在保持原始图性质的情况下以一定的精度在稀疏图上实现了高效的算法分析.图稀疏算法是一种保留顶点、对边稀疏采样的方法.按照相应算法分析所需要的原始图性质,提出图稀疏的边度量方式.文中系统回顾了4种边度量下的图稀疏采样方法:生成图稀疏、边连通图稀疏、聚类图稀疏、边传播性图稀疏,归纳了不同边度量方式下图稀疏的优缺点和适应性,并进一步讨论了动态图流稀疏化的最新研究进展.最后,总结了图稀疏领域有待解决的问题并展望了未来的研究方向.

关键词：复杂网络、图结构、图稀疏、边的度量

所属期刊栏目：45

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

资助基金：国家自然科学基金61572266;宁波市自然科学基金2017A610114;浙江省自然科学基金LY16F020003

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

页数：共8页

页码：24-30,43