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

doi:10.11959/j.issn.1000-0801.2016169

摘要/Abstract

摘要：

图三角数量的计算是计算网络聚集系数和传递性的重要步骤，广泛应用于重要角色识别、垃圾邮件检测、社区发现、生物检测等。在大数据背景下，计算图中三角形算法主要面临时空消耗和计算准确性两大难题。介绍了代表性的大图中计算三角形的算法，主要存在准确计算和近似计算两大类。准确计算算法又分为内存算法、外存算法和分布式算法，时空消耗或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.

Key words: exact counting, approximate counting, triangle, graph

金宏桥,董一鸿. 大数据下图三角计算的研究进展[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.

图/表 13

表1

图1

图2

图3

图4

图5

图6

图7

表2

图8

表3

表4

表5

参考文献 22

[1]	THOMAS S ， . Algorithmic aspects of triangle-based network analysis[J]. Phd in Computer Science， 2007： 26-29.
[2]	COPPERSMITH D ， WINOGRAD S . Matrix multiplication viaarithmetic progressions[J]. Journal of Symbolic Computation， 1990，9（3）： 251-280.
[3]	ALON N ， YUSTER R ， ZWICK U . Finding and counting given length cycles[J]. Algorithmica， 1997，17（3）： 209-223.
[4]	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.
[5]	CHIBA N ， NISHIZEKI T . Arboricity and subgraph listing algorithms[J]. Siam Journal on Computing， 1985，14（1）： 210-223.
[6]	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.
[7]	LATAP M . Theory and practice of triangle problems in very large（sparse（power-law）） graphs[EB/OL].[2006-09-20]. .
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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
[14]	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.
[15]	PAGH R ， TSOURAKAKIS C E . Colorful triangle counting and Mapreduce implementation[J]. Information Processing Letters， 2011，112（7）： 277-281.
[16]	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.
[17]	AVRON H ， . Counting triangles in large graphs using randomized matrix trace estimation[J]. In Large-Scale Data Mining：Theory and Applications（KDD Workshop）， 2010.
[18]	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.
[19]	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.
[20]	BULTEAU L ， FROESE V ， KUTZKOV K ，et al. Triangle counting in dynamic graph streams[EB/OL].[2015-07-14]. .
[21]	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] .
[22]	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.

数据集		I/O操作数			运行时间/s
数据集	DGP	RGP	MGT	DGP	RGP	MGT
LJ	1 053 594	1 257 411	307 893	109.562	156.757	19.053 35
BTC	12 683 280	16 539 188	4 192 628	1 009.11	1 500.01	111.044 9
USRD	831 306	2 141 150	414 240	62.207 3	189.318	6.688 45

数据集	时间/min			每轮MapReduce中数据shuffle的大小/GB
数据集	GP	TTP	CTTP	GP	TTP	CTTP
LJ	1	1	1	24.4	4.6	4.5
PhoneCall	11	6	6	104	79	69.5
Twitter	302	162	92	2 140	1 300	31.5
SubDomain	1 496	455	218	4 038.4	2 280.6	56.8

数据集	A.Pavany	Laurent Bulteau	TRIEST
DBLP	0.19	2.3	5.3
YouTube	4.42	1.7	7.8

类别	算法	优点	缺点	适用范围
内存算法	FCNI	时间效率高	空间消耗大	内存大，静态图
外存算法	Chu and Cheng	简单易实现	时空消耗大	静态图
	MGT	I/O效率高	冗余	静态图
分布式算法	GP	简单易实现	冗余	分布式，静态图
	TTP	时间效率高	没有考虑负载均衡	分布式，静态图
	GTTP	考虑负载均衡	时间复杂度高	分布式，静态图

类别	算法	优点	缺点	适用范围
静态算法	Kolountzakis N	时间复杂度低	空间消耗大	静态图
	Avron H	时间复杂度低	空间消耗大	静态图
流式算法	Pavany A	空间消耗小	只考虑边插入的情况	支持仅有插入边的图流
	Bulteau L	考虑边的插入/删除	空间消耗较大	支持有插入或删除边的图流
	TRIEST	考虑边的插入/删除，可设定存储大小	时间消耗较大	支持有插入或删除边的图流