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

doi:10.11959/j.issn.1000-0801.2016169

Abstract

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

Hongqiao JIN,Yihong DONG. Research progress of triangle counting in big data[J]. Telecommunications Science, 2016, 32(6): 153-162.

Figures/Tables 13

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

Metrics

Recommended 0

No Suggested Reading articles found!

数据集		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	考虑边的插入/删除，可设定存储大小	时间消耗较大	支持有插入或删除边的图流

Research progress of triangle counting in big data

RichHTML

PDF下载

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 13

References 22

Related Articles 15

Metrics

Recommended 0

[1]	Qiaoqiao MA, Ligang DONG, Xian JIANG. Distributed high-efficiency entropy energy-saving clustering routing algorithm for SDWSN [J]. Telecommunications Science, 2023, 39(3): 100-114.
[2]	Jun LUO, Chi LIU, Binglei WANG. Telecom-operators cryptography application system with quantum key distribution [J]. Telecommunications Science, 2023, 39(1): 136-145.
[3]	Shuai YANG, Ruiqin WANG, Hui MA. Multi-channel based edge-learning graph convolutional network [J]. Telecommunications Science, 2022, 38(9): 95-104.
[4]	Dongming ZHAO. Research and application practice of knowledge graph technology system for telecom-operators [J]. Telecommunications Science, 2022, 38(8): 151-162.
[5]	Yijiang LI, Huibiao YE, Renhua XIE, Jiali LOU, Danna ZHUANG, Chuanhuang LI. Intelligent prediction method of network performance based on graph neural network [J]. Telecommunications Science, 2022, 38(3): 143-157.
[6]	Xinyuan HU, Ruoqi DENG, Boya DI, Hongliang ZHANG, Lingyang SONG. Key technologies of satellite communications aided by reconfigurable holographic surfaces [J]. Telecommunications Science, 2022, 38(10): 46-56.
[7]	Jian HU, Lei SUN, Yiyan YIN, Xiaokang YANG, Jingui BAI, Yejiang ZHANG. Research on 4G/5G voice quality optimization based on data mining and geographic visualization [J]. Telecommunications Science, 2022, 38(10): 131-139.
[8]	Wenjun HOU, Bing BAI, Benzhi YANG. Research on the development and business trend of holographic technology under 6G network [J]. Telecommunications Science, 2021, 37(11): 1-10.
[9]	Feiyang LIU, Kun LI, Fei SONG, Huachun ZHOU. Construction of DDoS attacks malicious behavior knowledge base construction [J]. Telecommunications Science, 2021, 37(11): 17-32.
[10]	Jihua WU, Pengyu ZHU, Zichen WU, Bin GU, Tao HONG, Bo GUO, Jing WANG, Jingyu WANG. Fault diagnosis and auto dispatchin of power communication network based on unsupervised clustering and frequent subgraph mining [J]. Telecommunications Science, 2021, 37(11): 51-63.
[11]	Zhaopin SU, Chaoyong SHEN, Guofu ZHANG, Feng YUE, Donghui HU. A robust audio steganography algorithm based on differential evolution [J]. Telecommunications Science, 2021, 37(11): 64-74.
[12]	Yanshang YIN, Tongpeng SUO, Ligang DONG, Xian JIANG. SDN security prediction method based on bayesian attack graph [J]. Telecommunications Science, 2021, 37(11): 75-85.
[13]	Shaoqing WU,Yihong DONG,Xiong WANG,Yan CAO,Yu XIN. Learning attribute network algorithm based on high-order similarity [J]. Telecommunications Science, 2020, 36(12): 20-32.
[14]	Xiaozhi YUAN,Li PENG,Linfeng ZHANG. Requirement and challenge of holographic-type communication to the future network [J]. Telecommunications Science, 2020, 36(12): 59-64.
[15]	Fangmin XU,Hui QIAN,Haiyan CAO. Semi-dynamic pilot allocation based on graph coloring in massive MIMO systems [J]. Telecommunications Science, 2020, 36(11): 39-46.