大数据下图三角计算的研究进展

金宏桥; 董一鸿

doi:10.11959/j.issn.1000-0801.2016169

您当前的位置：

首页 >

文章列表页 >

大数据下图三角计算的研究进展

综述 | 更新时间：2024-06-05

- 大数据下图三角计算的研究进展
- Research progress of triangle counting in big data
- 电信科学 2016年32卷第6期页码：153-162
- 作者机构：
- 作者简介：
  
  [ "金宏桥（1993-），女，宁波大学信息科学与工程学院硕士生，主要研究方向为大数据、数据挖掘。" ]
  [ "董一鸿（1969-），男，博士，宁波大学教授，主要研究方向为大数据、数据挖掘和人工智能。" ]
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2016169
  中图分类号： TP391
- 网络出版日期：2016-06，
  
  纸质出版日期：2016-06-20
- 稿件说明：
移动端阅览
金宏桥, 董一鸿. 大数据下图三角计算的研究进展[J]. 电信科学, 2016,32(6):153-162.

Hongqiao JIN, Yihong DONG. Research progress of triangle counting in big data[J]. Telecommunications science, 2016, 32(6): 153-162.
金宏桥, 董一鸿. 大数据下图三角计算的研究进展[J]. 电信科学, 2016,32(6):153-162. DOI： 10.11959/j.issn.1000-0801.2016169.

Hongqiao JIN, Yihong DONG. Research progress of triangle counting in big data[J]. Telecommunications science, 2016, 32(6): 153-162. DOI： 10.11959/j.issn.1000-0801.2016169.

摘要

图三角数量的计算是计算网络聚集系数和传递性的重要步骤，广泛应用于重要角色识别、垃圾邮件检测、社区发现、生物检测等。在大数据背景下，计算图中三角形算法主要面临时空消耗和计算准确性两大难题。介绍了代表性的大图中计算三角形的算法，主要存在准确计算和近似计算两大类。准确计算算法又分为内存算法、外存算法和分布式算法，时空消耗或I/O消耗很大。近似计算算法中，有辅助算法、非流式算法和流式算法之分。最后对计算三角形算法进行了归纳总结。

Abstract

Counting triangles in a graph is an important step to calculate the clustering coefficient and the transitivity ratio of the network，which is widely used in important role identification，spam detection，community discovery，biological detection etc.Counting triangles algorithm is mainly faced with two major problems of space-time consumption and accuracy.The representative algorithm of the counting triangles in the big graph was introduced.There existed two kinds of algorithms，which were exact counting algorithm and approximate counting algorithm.Exact counting algorithms were divided into internal memory algorithm，external memory algorithm and distributed algorithm.The space-time consumption or I/O consumption of exact counting algorithm was very large.Approximate counting algorithms were divided into auxiliary algorithm，static algorithm and streaming algorithm.In the end，the counting triangles algorithms were summarized.

关键词

Keywords

references

THOMAS S ， . Algorithmic aspects of triangle-based network analysis [J ] . Phd in Computer Science ， 2007 ： 26 - 29 .

COPPERSMITH D ， WINOGRAD S . Matrix multiplication viaarithmetic progressions [J ] . Journal of Symbolic Computation ， 1990 ， 9 （ 3 ）： 251 - 280 .

ALON N ， YUSTER R ， ZWICK U . Finding and counting given length cycles [J ] . Algorithmica ， 1997 ， 17 （ 3 ）： 209 - 223 .

THOMAS S ， WAGNER D . Finding，counting and listing all triangles in large graphs，an experimental study [C ] // The 4th International Workshop，May 10-13，2005，Santorini Island，Greece . New Jersey ： IEEE Press ， 2005 .

CHIBA N ， NISHIZEKI T . Arboricity and subgraph listing algorithms [J ] . Siam Journal on Computing ， 1985 ， 14 （ 1 ）： 210 - 223 .

KUMAR R ， RAGHAVAN P ， RAJAGOPALAN S ， et al . The web as a graph：measurements，models，and methods [C ] // The 5th Annual International Conference，July 26-28，1999，Tokyo，Japan . New Jersey ： IEEE Press ， 2000 ： 1 - 17 .

LATAP M . Theory and practice of triangle problems in very large（sparse（power-law）） graphs [EB/OL ] .[2006-09-20 ] . http://arxiv.org/pdf/cs/0609116.pdf http://arxiv.org/pdf/cs/0609116.pdf .

SEVENICH M ， HONG S ， WELC A ， et al . Fast in-memory triangle listing for large real-world graphs [C ] // The 8th Workshop on Social Network Mining and Analysis SNAKDD，August 24-27，2008，Las Vegas，NV，USA . New York ： ACM Press ， 2010 ： 1 - 5 .

CHU S ， CHENG J . Triangle listing in massive networks and its applications [C ] // The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，August 21-24，2011，San Diego，CA，USA . New York ： ACM Press ， 2011 ： 672 - 680 .

HU X C ， TAO Y F . I/O efficient algorithms on triangle listing and counting [J ] . ACM Transactions on Database System ， 2014 ， 39 （ 4 ）： 1 - 30 .

SURI S ， VASSILVITSKII S . Counting triangles and the curse of the last reducer [C ] // The 20th International Conference on World Wide Web，March 28-April 1，2011，Hyderabad，India . New York ： ACM Press ， 2011 ： 607 - 614 .

PARK H M ， CHUNG C W . An efficient MapReduce algorithm for counting triangles in avery large graph [C ] // ACM Conference of Information and Knowledge Management，October 27-November 1，2013，San Francisco，CA，USA . New York ： ACM Press ， 2013 ： 539 - 548 .

PARK H M ， SILVESTRI F ， KANG U ， et al . MapReduce triangle enumeration with guarantees [C ] // ACM Conference of Information and Knowledge Management，November 3-7，2014，Shanghai，China . New York ： ACM Press ， 2014

TSOURAKAKIS C E ， KANG U ， MILLER G L ， et al . DOULIN：counting triangles in massive graphs with acoin [C ] // The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，June 28-July 1，2009，Paris，France . New York ： ACM Press ， 2009 ： 837 - 846 .

PAGH R ， TSOURAKAKIS C E . Colorful triangle counting and Mapreduce implementation [J ] . Information Processing Letters ， 2011 ， 112 （ 7 ）： 277 - 281 .

KOLOUNTZAKIS M N ， MILLER G L ， PENG R ， et al . Efficient triangle counting in large graphs via degree-based vertex partitioning [J ] . Internet Mathematics ， 2010 ， 8 （ 1-2 ）： 15 - 24 .

AVRON H ， . Counting triangles in large graphs using randomized matrix trace estimation [J ] . In Large-Scale Data Mining：Theory and Applications（KDD Workshop）， 2010 .

BURIOL L S ， FRAHLING G ， LEONARDI S ， et al . Counting triangles in data streams [C ] // The 25th ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems，June 26-28，2006，Chicago，Illinois，USA . New York ： ACM Press ， 2006 ： 253 - 262 .

PAVANY A ， TANGWONGSAN K ， TIRTHAPURAZ S ， et al . Counting and sampling triangles from a graph stream [J ] . Proceedings of the Vldb Endowment ， 2013 ， 6 （ 14 ）： 1870 - 1881 .

BULTEAU L ， FROESE V ， KUTZKOV K ， et al . Triangle counting in dynamic graph streams [EB/OL ] .[2015-07-14 ] . http://itu.dk/people/konk/papers/dtc_full.pdf http://itu.dk/people/konk/papers/dtc_full.pdf .

STEFANI L D ， EPASTO A ， RIONDATO M ， et al . TRIEST：counting local and global triangles in fully-dynamic streams with fixed memory size [EB/OL ] .[2016-02-24 ] http://arxiv.org/abs/1602.07424 http://arxiv.org/abs/1602.07424 .

LIM Y ， KANG U . MASCOT：memory-efficient and accurate sampling for counting local triangles in graph streams [C ] // The 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD，August 10-13，2015，Hilton，Sydney . New Yor ： ACM Press ， 2015 ： 685 - 694 .

浏览量

1086

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据