徐丽丽,董一鸿,潘剑飞,陈华辉.面向复杂网络的图稀疏算法综述[J].计算机科学,2018,45(5):24-30, 43
面向复杂网络的图稀疏算法综述
Survey of Graph Sparsification Algorithms for Complex Networks
投稿时间:2017-08-16  修订日期:2017-11-13
DOI:10.11896/j.issn.1002-137X.2018.05.004
中文关键词:  复杂网络,图结构,图稀疏,边的度量
英文关键词:Complex network,Graph structure,Graph sparsification,Edge measurement
基金项目:本文受国家自然科学基金(61572266),宁波市自然科学基金(2017A610114),浙江省自然科学基金(LY16F020003)资助
作者单位E-mail
徐丽丽 宁波大学信息科学与工程学院 浙江 宁波315211  
董一鸿 宁波大学信息科学与工程学院 浙江 宁波315211 dongyihong@nbu.edu.cn 
潘剑飞 宁波大学信息科学与工程学院 浙江 宁波315211  
陈华辉 宁波大学信息科学与工程学院 浙江 宁波315211  
摘要点击次数: 444
全文下载次数: 320
中文摘要:
      大规模数据下复杂网络的算法分析面临复杂度高的挑战,为此引入图稀疏的思想,在保持原始图性质的情况下以一定的精度在稀疏图上实现了高效的算法分析。图稀疏算法是一种保留顶点、对边稀疏采样的方法。按照相应算法分析所需要的原始图性质,提出图稀疏的边度量方式。文中系统回顾了4种边度量下的图稀疏采样方法:生成图稀疏、边连通图稀疏、聚类图稀疏、边传播性图稀疏,归纳了不同边度量方式下图稀疏的优缺点和适应性,并进一步讨论了动态图流稀疏化的最新研究进展。最后,总结了图稀疏领域有待解决的问题并展望了未来的研究方向。
英文摘要:
      With the increasing of data scale,traditional graph algorithms confront the challenge of excessive complexity.The idea of graph sparse was introduced into algorithm,and analytical algorithm was realized efficiently on the sparse graph while preserving the original property with certain accuracy precision.Graph sparsity algorithm is a sampling method which preserves the original vertexes and sparses the edges.In this paper,the latest progresses of graph sparse algorithm were reviewed from four aspects,such as sparse spanning algorithm,edge connectivity sparse,clustering sparse and influence propagation sparse.The advantages and disadvantages of the graph sparse algorithms and the adaptability were summarized in different edge metrics.In addition,dynamic graph streaming sparse methods were analyzed.Finally,several important problems were outlined and future research directions in the field of sparse complex network were prospected.
查看全文  查看/发表评论  下载PDF阅读器