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

• 学术论文 • 上一篇    下一篇

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

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

  1. 宁波大学信息科学与工程学院, 浙江宁波 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   

  1. 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

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

中图分类号: