分布式环境下基于马尔科夫链的图流三角近似计算

doi:10.3969/j.issn.0372-2112.2018.09.014

电子学报 ›› 2018, Vol. 46 ›› Issue (9): 2139-2148.DOI: 10.3969/j.issn.0372-2112.2018.09.014

分布式环境下基于马尔科夫链的图流三角近似计算

金宏桥, 董一鸿, 陈华辉, 钱江波

宁波大学信息科学与工程学院, 浙江宁波 315211

收稿日期:2016-10-25 修回日期:2017-09-22 出版日期:2018-09-25
- 通讯作者:
- 董一鸿
- 作者简介:
- 金宏桥 女,1993年10月出生,安徽六安人.现为宁波大学信息科学与工程学院硕士研究生.主要研究方向为大数据、数据挖掘.E-mail:nbjhqiao@163.com;陈华辉 男,博士,1964年出身于浙江鄞州.宁波大学教授,主要研究方向为数据库技术、流数据处理等.E-mail:chenhuahui@nbu.edu.cn;钱江波 男,博士,1974年出生于浙江宁波.宁波大学教授,主要研究方向为数据库技术、流数据处理、多维数据索引技术等.E-mail:qianjiangbo@nbu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61472194，No.61572266）; 浙江省自然科学基金 (No.Y16F020003）; 宁波市自然科学基金资助项目 (No.2017A610114）

DATC-MC: Distributed Approximate Triangle Counting Based on Markov Chain in Graph Streaming

JIN Hong-qiao, DONG Yi-hong, CHEN Hua-hui, QIAN Jiang-bo

Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo, Zhejiang 315100, China

Received:2016-10-25 Revised:2017-09-22 Online:2018-09-25 Published:2018-09-25
- Corresponding author:
- DONG Yi-hong

摘要/Abstract

摘要： 图三角数量的计算是计算网络聚集系数和传递性的重要步骤.大数据背景下，以采样为策略的近似计算成为图三角计算的主要方法，然而此类方法面临时空消耗和计算错误性两大难题.本文提出了一种针对图流的基于马尔科夫链的图三角近似计算算法，该算法以窗口作为图流处理单位，将马尔科夫链与采样相结合，保证降低错误率的同时实现动态适应内存空间的变化.实验显示，相较其他三角形近似计算算法，该算法在错误率上降低2~4倍，时间消耗上也有很大改进.

关键词: 图三角, 图流, 马尔科夫链, 大数据, Spark

Abstract: Counting triangles in a graph is an important step to calculate the clustering coefficient and the transitivity ratio of the network. Under the background of big data, the sampling method is the main method used in triangle counting. However, two problems of spatiotemporal costs and computing errors are very difficult. An approximate triangle counting algorithm based on Markov chain in the graph stream is proposed. Treating the window as processing unit of graph stream, it uses Markov chain to implement dynamic adaptation of memory and to reduce error ratio while sampling. Compared with other algorithms, the proposed algorithm can drop the error rate by 2~4 times, and the time consumption has a great improvement.

Key words: triangle, graph streaming, Markov chain, big data, spark

中图分类号:

TP391

金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.

JIN Hong-qiao, DONG Yi-hong, CHEN Hua-hui, QIAN Jiang-bo. DATC-MC: Distributed Approximate Triangle Counting Based on Markov Chain in Graph Streaming[J]. Acta Electronica Sinica, 2018, 46(9): 2139-2148.

参考文献

[1] Alon N,Yuster R,Zwick U.Finding and counting given length cycles[J].Algorithmica,1997,17(3):209-223.
[2] Schank T,Wagner D.Finding,counting and listing all triangles in large graphs,an experimental study[J].Lecture Notes in Computer Science,2005,3503:606-609.
[3] Chiba N,Nishizeki T.Arboricity and subgraph listing algorithms[J].Siam Journal on Computing,1985,14(1):210-223.
[4] Latapy M.Main-memory triangle computations for very large (sparse (power-law)) graphs[J].Theoretical Computer Science,2008,407(1-3):458-473.
[5] Chu S,Cheng J.Triangle listing in massive networks and its applications[A].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Diego,California,USA:ACM,2011.672-680.
[6] Suri S,Vassilvitskii S.Counting triangles and the curse of the last reducer[A].International Conference on World Wide Web[C].Hyderabad,India:ACM,2011.607-614.
[7] Park H M,Chung C W.An efficient MapReduce algorithm for counting triangles in a very large graph[A].ACM Conference of Information and Knowledge Management[C].San Francisco,CA,USA:ACM,2013.539-548.
[8] Park H M,Silvestri F,Kang U,et al.MapReduce triangle enumeration with guarantees[A].ACM International Conference on Conference on Information and Knowledge Management[C].Shanghai,China:ACM,2014.1739-1748.
[9] Hu X,Tao Y,Chung C W.I/O-efficient algorithms on triangle listing and counting[J].Acm Transactions on Database Systems,2014,39(4):1-30.
[10] Jowhari H,Ghodsi M.New streaming algorithms for counting triangles in graphs[J].Lecture Notes in Computer Science,2005,3595:710-716.
[11] Buriol L S,Frahling G,Leonardi S,et al.Counting triangles in data streams[A].PODS'06 Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database[C].Chicago,Illinois,USA:ACM,2006.253-262.
[12] Pavan A,Tangwongsan K,Tirthapura S,et al.Counting and sampling triangles from a graph stream[J].Proceedings of the Vldb Endowment,2013,6(14):1870-1881.
[13] Lim Y,Kang U.MASCOT:memory-efficient and accurate sampling for counting local triangles in graph streams[A].21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD[C].Sydney,NSW,Australia:ACM Press,2015.685-694.
[14] Tsourakakis C E,Kang U,Miller G L,et al.DOULION:counting triangles in massive graphs with a coin[A].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Paris,France:DBLP,2009.837-846.
[15] Bulteau L,Froese V,Kutzkov K,et al.Triangle counting in dynamic graph streams[J].Algorithmica,2016,8503(1):1-20.
[16] 姚苏,关建峰,潘华,张宏科.基于APT潜伏攻击的网络可生存性模型与分析[J].电子学报,2016,44(10):2415-2422. YAO Su,GUAN Jian-feng,Pan Hua,Zhang Hong-ke.Modeling and Analysis for Network Survivability of APT Latent Attack[J].Acta Electronica Sinica,2016,44(10):2415-2422.(in Chinese)

分布式环境下基于马尔科夫链的图流三角近似计算

DATC-MC: Distributed Approximate Triangle Counting Based on Markov Chain in Graph Streaming

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	廖彬, 黄静莱, 王鑫, 孙瑞娜, 葛晓燕, 国冰磊. SCEA:一种适应高维海量数据的并行聚类集成算法[J]. 电子学报, 2021, 49(6): 1077-1087.
[2]	侯秀聪, 赖晓平, 曹九稳. 正则化超限学习机的最大分划广义交替方向乘子法[J]. 电子学报, 2021, 49(4): 625-630.
[3]	张孟健, 龙道银, 王霄, 杨靖. 基于马尔科夫链的灰狼优化算法收敛性研究[J]. 电子学报, 2020, 48(8): 1587-1595.
[4]	杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212.
[5]	陆佳炜, 吴涵, 陈烘, 张元鸣, 梁倩卉, 肖刚. 一种基于动态拓扑的流计算性能优化方法及其在Storm中的实现[J]. 电子学报, 2020, 48(5): 878-890.
[6]	徐超, 陈勇, 葛红美, 何炎祥. 基于大数据的审计技术研究[J]. 电子学报, 2020, 48(5): 1003-1017.
[7]	江小玉, 李贵洋, 周悦, 胡金平, 李慧. 基于负载均衡的纠删码修复流水线[J]. 电子学报, 2020, 48(5): 930-936.
[8]	晋云霞, 杨贺昆, 冯朝胜, 刘帅南, 李航, 邹莉萍, 万国根. 一种支持解密外包的KP-ABE方案[J]. 电子学报, 2020, 48(3): 561-567.
[9]	张鹏, 叶剑, 张鹏. 基于概念漂移检测的大数据交易过程模型优化方法[J]. 电子学报, 2019, 47(7): 1465-1474.
[10]	魏波, 吴瑞峰, 张文生, 吕敬钦, 王莹莹, 夏学文. 具有双重稀疏机制的在线学习算法[J]. 电子学报, 2019, 47(10): 2202-2210.
[11]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[12]	郭艺, 叶剑, 张鹏. 基于偏差约减的大数据交易模型分析与修复方法[J]. 电子学报, 2018, 46(7): 1754-1761.
[13]	尹鑫, 田有亮, 王海龙. 面向大数据定价的委托拍卖方案[J]. 电子学报, 2018, 46(5): 1113-1120.
[14]	丁琳琳, 崔子强, 尹显坤, 王俊陆, 宋宝燕. 基于MapReduce的增广动态Skyline查询处理方法[J]. 电子学报, 2018, 46(5): 1062-1070.
[15]	赵海军, 崔梦天, 李明东, 何先波. 基于CTMC和状态空间模型的宽带无线接入网的QoS性能研究[J]. 电子学报, 2018, 46(4): 783-790.