Computer Science ›› 2018, Vol. 45 ›› Issue (5): 24-30.doi: 10.11896/j.issn.1002-137X.2018.05.004

Previous Articles     Next Articles

Survey of Graph Sparsification Algorithms for Complex Networks

XU Li-li, DONG Yi-hong, PAN Jian-fei and CHEN Hua-hui   

  • Online:2018-05-15 Published:2018-07-25

Abstract: 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.

Key words: Complex network,Graph structure,Graph sparsification,Edge measurement

[1] ZHENG X,CHEN J P,SHAO J L,et al.Analysis on topological properties of Beijing urban public transit based on complex network theory [J].Acta Physica Sinica,2012,61(19):95-105.(in Chinese) 郑啸,陈建平,邵佳丽,等.基于复杂网络理论的北京公交网络拓扑性质分析[J].物理学报,2012,61(19):95-105.
[2] QIAO S J,HAN N,ZHANG K F,et al.Algorithm for Detecting Overlapping Communities from Complex Network Big Data [J].Journal of Software,2017,28(3):631-647.(in Chinese) 乔少杰,韩楠,张凯峰,等.复杂网络大数据中重叠社区检测算法[J].软件学报,2017,28(3):631-647.
[3] LIU X,YI D Y.Complex Network Community Detection by Local Similarity [J].Acta Automatica Sinica,2011,37(12):1520-1529.(in Chinese) 刘旭,易东云.基于局部相似性的复杂网络社区发现方法[J].自动化学报,2011,37(12):1520-1529.
[4] ZHOU X,ZHANG F M,LI K W,et al.Finding vital node by node importance evaluation matrix in complex networks[J].Acta Physica Sinica,2012,1(5):50201.(in Chinese) 周漩,张凤鸣,李克武,等.利用重要度评价矩阵确定复杂网络关键节点[J].物理学报,2012,61(5):50201.
[5] ZHANG K,LI P P,ZHU B P,et al.Based on PageRank Weighted importance evaluation method for weighted weighted complex network nodes[J].Journal of Nanjing University of Aeronautics &Astronautics,2013,45(3):429-434.(in Chinese) 张琨,李配配,朱保平,等.基于PageRank的有向加权复杂网络节点重要性评估方法[J].南京航空航天大学学报,2013,45(3):429-434.
[6] YANG B,LIU D Y,LIU J M,et al.Complex Network Clustering Method[J].Journal of Software,2009,20(1):54-66.(in Chinese) 杨博,刘大有,LIU J M,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66.
[7] CAI Q.Structure Analytics of Big Data Complex NetworksBased on Swarm Intelligence[D].Xi’an:Xidian University,2015.(in Chinese) 蔡清.基于群体智能优化的大数据复杂网络结构分析[D].西安:西安电子科技大学,2015.
[8] LI M P,GAO H,ZOU Z N,et al.K-Reach Query Processing Based on Graph Compression[J].Journal of Software,2014,25(4):797-812.(in Chinese) 李鸣鹏,高宏,邹兆年,等.基于图压缩的k可达查询处理[J].软件学报,2014,25(4):797-812.
[9] WANG X H,YANG X Y,JIAO L C.Compression of Complex Networks Based on Multiscale Geometric Analysis[J].Journal of Electronics & Information Technology,2009,1(4):968-972.(in Chinese) 王晓华,杨新艳,焦李成.基于多尺度几何分析的复杂网络压缩策略[J].电子与信息学报,2009,31(4):968-972.
[10] ZHANG Y,LIU Y B,XIONG G,et al.Journal of Electronics & Information Technology[J].Journal of Software,2014,5(9):1937-1952.(in Chinese) 张宇,刘燕兵,熊刚,等.图数据表示与压缩技术综述[J].软件学报,2014,5(9):1937-1952.
[11] LI H B,ZHANG J P,YANG J,et al.Acta Scientiarum Natura-lium Universitatis[J].Acta Scientiarum Naturalium Universitatis Pekinesis,2013,49(1):117-125.(in Chinese) 李泓波,张健沛,杨静,等.基于社区节点重要性的社会网络压缩方法[J].北京大学学报(自然科学版),2013,49(1):117-125.
[12] YANG H L,ZHANG J P,YANG J.Compression online social networks by calibrating structure redundancy[J].Journal of Computer Research and Development,2013,50(12):2504-2519.(in Chinese) 杨海陆,张健沛,杨静.基于结构冗余性校准的在线式社会网络压缩[J].计算机研究与发展,2013,50(12):2504-2519.
[13] QIAN J B,ZHU Q,WANG Y L.Bloom Filter Based Associative Deletion[J].IEEE Transactions on Parallel and Distributed Systems(TPDS),2014,25(8):1986-1998.
[14] CHEN Y F,HUANG Z P,CAO P,et al.Subscription Aggregation Query Processing Based on Matrix Summation over DTN[J].IEICE Transactions on Communications,2016,99(4):812-819.
[15] BATSON J,SPIELMAN D A,SRIVASTAVA N,et al.Spectral sparsification of graphs:Theory and algorithms[J].Communications of the ACM,2013,56(8):87-94.
[16] COHEN E.Fast Algorithms for Constructing t-Spanners and Paths with Stretch t[C]∥Symposium on Foundations of Computer Science.IEEE,1999:648-658.
[17] FUNG W S,HARIHARAN R,HARVEY N J A,et al.A generalframework for graph sparsification[C]∥ACM Symposium on Theory of Computing.2011:71-80.
[18] AHN K J,GUHA S,MCGREGOR A.Graphsketches:sparsification,spanners,andsubgraphs[C]∥ 31st ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems.2012:5-14.
[19] ABELLO J,KORN J,FINOCCHI I.Graph Sketches[C]∥Proceedings of the ACM Symposium.2001:67-70.
[20] SPIELMAN D A,TENG S H.Smoothed analysis of termination of linear programming algorithms[J].Mathematical Programming,2003,97(1/2):375-404.
[21] BASWANA S,SEN S.A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs[J].Random Structures & Algorithms,2010,30(4):532-563.
[22] AHN K J,GUHA S,MCGREGOR A.Spectral Sparsification in Dynamic Graph Streams[J].Mathematical Programming,2013,7(11):9896-9904.
[23] MARTIN C.Spectral Sparsification: The Barrier Method and its Applications [D].Cambridge,Massachusetts,2014.
[24] LEFEVRE K,TERZI E.GraSS:Graph Structure Summarization[C]∥SIAM International Conference on Data Mining,SDM 2010).2010:454-465.
[25] SPIELMAN D A,TENG S H.Spectral Sparsification of Graphs[J].SIAM Journal of Computing,2008,40(4):981-1025.
[26] KOUTIS I,LEVIN A,PENG R.Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices[J].ACM Transactions on Algorithms,2012,12(2):17.
[27] HUANG H.Spectral Sparsification for Directed Graphs viaRandom Sampling [D].Shanghai:Fudan University,2014.(in Chinese) 黄璜.有向图的随机采样谱稀疏化方法[D].上海:复旦大学,2014.
[28] NEYLON T.Matrix Sparsification and the Sparse Null Space Problem[M].New York:Springer-Verlag,2016.
[29] SPIELMAN D A,TENG S H.Nearly-linear time algorithms for graph partitioning,graph sparsification,and solving linear systems[C]∥Proceddings of IEEE Foundations of Computer Science.New York:IEEE Press,2004:81-90.
[30] KOUTIS I,XU S C.Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification[M]∥Algorithms and Models for the Web-Graph.Spinger Berlin Heidelberg,2016:13-19.
[31] PANDURANGAN G,ROBINSON P,S CQUIZZATO M.FastDistributed Algorithms for Connectivity and MST in Large Graphs[C]∥28th ACM Symposium on Parallelism in Algorithms and Architectures.2016.
[32] SAHA T,RANGWALA H,DOMENICONI C.Sparsificationand Sampling of Networks for Collective Classification[C]∥International Conference on Social Computing,Behavioral-CulturalModelingand Prediction.2013:293-302.
[33] SATULURI V,PARTHASARATHY S,RUAN Y.Local graph sparsification for scalable clustering[C]∥ACM SIGMOD International Conference on Management of Data(SIGMOD 2011).2011:721-732.
[34] KORHONEN,JANNE H.Deterministic MST Sparsification in the Congested Clique[J].oai:arXiv.org:1605.02022.
[35] CHEN D H,ZHOU M,SUN Y Q,et al.MR-GSpar:A Distributed Large Graph Sparsification Algorithm Based on MapReduce[J].Computer Science,2013,40(10):190-193.(in Chinese) 陈德华,周蒙,孙延青,等.MR-GSpar:一基于MapReduce的大图稀疏算法[J].计算机科学,2013,40(10):190-193.
[36] BRYAN W.Sparsification of Social Networks Using RandomWalks[D].Orlando:University of Florida,2015.
[37] LINDNER G,STAUDT C L,HAMANN M,et al.Structure-Preserving Sparsification of Social Networks[C]∥IEEE/ACM International Conference on Advances in Social Networks Ana-lysis and Mining.ACM,2015:448-454.
[38] FAN C,ZHAO W.A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification[M]∥Algorithms and Models for the Web-Graph.Springer Berlin Heidelberg,2013:2-14.
[39] KAPRALOV M,LEE Y T,MUSCO C,et al.Single Pass Spectral Sparsification in Dynamic Streams[C]∥Proceedings of IEEE Foundations of Computer Science.New York:IEEE Press,2014:561-570.
[40] MCGREGOR A.Graph stream algorithms:a survey[M]∥Algorithms and Medels for the Web-Graph.Springer Berlin Heidelberg,2014:9-20.
[41] TANG N,CHEN Q,MITRA P.Graph Stream Summarization:From Big Bang to Big Crunch[C]∥International Conference on Management of Data.ACM,2016:1481-1496.
[42] MCGREGOR A.Graph Mining on Streams[M].Springer US,2009.
[43] ASSADI S,KHANNA S,LI Y,et al.Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches[J].Computer Science,2015(23):247-272.
[44] EPPSTEIN D.Sparsification-a technique for speeding up dynamicgraph algorithms[C]∥Symposium on Foundations of Computer Science.IEEE Computer Society,1992:60-69.
[45] KELNER J A.Spectral Sparsification in the Semi-streaming Setting[J].Theory of Computing Systems,2013,53(2):243-262.
[46] CALANDRIELLO D,LAZARIC A,VALKO M,et al.Incre-mental Spectral Sparsification for Large-Scale Graph-Based Semi-Supervised Learning[J].Theory of Computing Systems,2016(2):740-745.
[47] MATHIOUDAKIS M,BONCHI F,CASTILLO C,et al.Sparsification of influence networks[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2011:529-537.
[48] AHN K J,GUHA S.Graph Sparsification in the Semi-streaming Model[C]∥Internatilonal Collogquium on Automata,Languages and Programming.2009:328-338.
[49] KAPRALOV M,WOODRUFF D.Spanners and sparsifiers in dynamic streams[C]∥Proceedings of the 2014 ACM sympo-sium on Principles of Distributed Computing.ACM,2014:272-281.
[50] AHN K J,GUHA S.Linear programming in the semi-streaming model with application to the maximum matching problem[C]∥International Conference on Automata,Languages and Programming.2011:526-538.
[51] AHN K J,GUHA S,MCGREGOR A.Graph sketches:sparsification,spanners,and subgraphs[C]∥ACM Sigmod-Sigact-Sigai Symposium on Principles of Database Systems.ACM,2012:5-14.
[52] GOEL A,KAPRALOV M,POST I.Single pass sparsification in the streaming model with edge deletions[J].Computer Science,2012,3(2):740-745.
[53] WANG W W,LI X P,FENG X C,et al.A Survey on Sparse Subspace Clustering[J].Acta Automatica Sinica,2015,41(8):1373-1384.(in Chinese) 王卫卫,李小平,冯象初,等.稀疏子空间聚类综述[J].自动化学报,2015,41(8):1373-1384.
[54] GILBERT A,INDYK P.Sparse Recovery Using Sparse Matrices[J].Proceedings of the IEEE,2008,98(6):937-947.
[55] KAPRALOV M,LEE Y T,MUSCO C,et al.Single Pass Spectral Sparsification in Dynamic Streams[C]∥Proceedings of IEEE Foundtaions of Computer Sicence.New York:IEEE Prcess,2014:561-570.
[56] LAI L,QIN L,LIN X,et al.Scalablesubgraph enumeration in MapReduce[J].Proceedings of the Vldb Endowment,2015,8(10):974-985.
[57] AKIBA T,YANO Y.Compact and Scalable Graph Neighborhood Sketching[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2016:685-694.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!