跨域环境下图流三角计数算法GTC

doi:10.11772/j.issn.1001-9081.2022071130

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (7): 2040-2048.DOI: 10.11772/j.issn.1001-9081.2022071130

所属专题：第39届CCF中国数据库学术会议(NDBC 2022)

• 第39届CCF中国数据库学术会议(NDBC 2022) • 上一篇下一篇

跨域环境下图流三角计数算法GTC

曹春泽¹, 马德龙¹, 袁野²()

^1.东北大学计算机科学与工程学院, 沈阳 110169
^2.北京理工大学计算机学院, 北京 100081

收稿日期:2022-07-12 修回日期:2022-08-28 接受日期:2022-09-05 发布日期:2023-07-20 出版日期:2023-07-10
通讯作者: 袁野
作者简介:曹春泽（1997—），男，安徽合肥人，硕士研究生，主要研究方向：跨域计算、三角计数；
马德龙（1990—），男，辽宁沈阳人，博士研究生，主要研究方向：大图数据的跨域处理与分析；
袁野（1981—），男，辽宁沈阳人，教授，博士，CCF高级会员，主要研究方向：大数据管理、数据库理论与系统。
基金资助:
国家自然科学基金资助项目(61932004)

GTC： geo-distributed triangle counting algorithm in graph streams

Chunze CAO¹, Delong MA¹, Ye YUAN²()

^1.School of Computer Science and Engineering，Northeastern University，Shenyang Liaoning 110169，China
^2.School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China

Received:2022-07-12 Revised:2022-08-28 Accepted:2022-09-05 Online:2023-07-20 Published:2023-07-10
Contact: Ye YUAN
About author:CAO Chunze， born in 1997， M. S. candidate. His research interests include geo-distributed computing， triangle counting.
MA Delong， born in 1990， Ph. D. candidate. His research interests include geo-distributed processing and analysis of large graph data.
YUAN Ye， born in 1981， Ph. D.， professor. His research interests include big data management， database theory and system.
Supported by:
National Natural Science Foundation of China(61932004)

摘要/Abstract

摘要：

现有的分布式三角计数算法假设所有计算节点位于同一地理位置，然而现实中它们可能位于跨洲际的多个数据中心中。跨域分布的数据中心使用广域网连接，具有网络带宽异质、通信费用高昂、分布不均等特点，而现有分布式算法无法适用于跨域环境。同时，现有研究较多采用随机采样、淘汰边等策略，忽略了三角形的形成具有时间局部性的特点。因此，研究了跨域环境中真实图流的三角计数问题并提出跨域三角计数（GTC）算法。首先针对现有边分发策略导致数据传输量过高的问题，提出一种跨域边分发策略，以结合通信的时间收益和数据收益建立收益公式，并使用点对点通信代替广播边；然后对于点对点通信在跨域环境中导致的三角形重复计数问题，提出终边计算规则，以确保无重复计数；最后基于时间加权采样算法提出时间加权三角计数算法，以利用三角形的时间局部性特点采样。在5个图流上把GTC与CoCoS （Conditional Counting and Sampling）、Tri-Fly进行对比的结果表明：GTC在通信数据量上比CoCoS减少了17%，比Tri-Fly减少了44%；在误差率上GTC比Tri-Fly减小了53%，略低于CoCoS；在算法运行时间上GTC比Tri-Fly减少了34%，略高于CoCoS。可见，GTC在保证较高准确率与较短算法运行时间的情况下，能有效减少通信数据量。

关键词: 跨域, 图流, 三角计数, 近似计算, 采样

Abstract:

The existing distributed triangle counting algorithms assume that all computing nodes are in the same location， while in reality， the nodes may be located in multiple data centers across continents. Geo-distributed data centers which are connected with wide area networks have characteristics of heterogeneous network bandwidth， high communication cost and uneven distribution， and the existing distributed algorithms cannot be applied to geo-distributed environment. At the same time， the existing research which ignores the temporal locality of the formation of triangles mostly adopts strategies such as random sampling and elimination of edges. Therefore， the triangle counting problem of real graph streams in geo-distributed environment was studied， and a Geo-distributed Triangle Counting （GTC） algorithm was proposed. Firstly， aiming at the problem of too high data transmission caused by the existing edge distribution strategy， a geo-distributed edge distribution strategy was proposed to build a benefit formula combining the time benefit and data benefit of communication and use point-to-point communication to replace broadcast edges. Then， for the triangle repeated counting problem caused by point-to-point communication in geo-distributed environment， a final edge calculation rule was proposed to ensure no counting repetition. Finally， based on the time weighted sampling algorithm， a time-weighted triangle counting algorithm was proposed to use the time locality of the triangle to sample. The GTC was compared with Conditional Counting and Sampling （CoCoS） and Tri-Fly on five real graph streams. The results show that GTC has the communication data size decreased by 17% compared to CoCoS and decreased by 44% compared to Tri-Fly， GTC has the error rate decreased by 53% compared to Tri-Fly and slightly less than CoCoS， and GTC has the running time decreased by 34% compared to Tri-Fly and slightly more than CoCoS. It can be seen that the GTC can reduce the size of communication data effectively while ensuring high accuracy and short algorithm running time.

Key words: geo-distributed, graph stream, triangle counting, approximate computing, sampling

中图分类号:

TP391

曹春泽, 马德龙, 袁野. 跨域环境下图流三角计数算法GTC[J]. 计算机应用, 2023, 43(7): 2040-2048.

Chunze CAO, Delong MA, Ye YUAN. GTC： geo-distributed triangle counting algorithm in graph streams[J]. Journal of Computer Applications, 2023, 43(7): 2040-2048.

图/表 13

图1 传统分布式图流三角计数算法架构

Fig. 1 Architecture of traditional distributed triangle counting algorithm in graph stream

表1 符号表

Tab. 1 Symbol table

符号	描述
$G S$	图流
$e i$	索引为 $i$ 的边（图流的第 $i$ 条边）
$(u, v)$	顶点 $u$ $v$ 组成的边
$(u, v, w)$	顶点 $u$ $v$ $w$ 组成的三角形
$i (u, v)$	$(u, v)$ 的索引
$f (u)$	顶点 $u$ 点被划分的Worker编号
$k$	Worker数量
$Г$	图流中三角形数量的估计值
$Г j$	Worker $j$ 计算的三角形数量估计值
$L$	水库容量
$N u$	顶点 $u$ 的邻居集合
$N u$	顶点 $u$ 的邻居数量
$U j$	Worker $j$ 的上行带宽
$D j$	Worker $j$ 的下行带宽

表1 符号表

Tab. 1 Symbol table

符号	描述
$G S$	图流
$e i$	索引为 $i$ 的边（图流的第 $i$ 条边）
$(u, v)$	顶点 $u$ $v$ 组成的边
$(u, v, w)$	顶点 $u$ $v$ $w$ 组成的三角形
$i (u, v)$	$(u, v)$ 的索引
$f (u)$	顶点 $u$ 点被划分的Worker编号
$k$	Worker数量
$Г$	图流中三角形数量的估计值
$Г j$	Worker $j$ 计算的三角形数量估计值
$L$	水库容量
$N u$	顶点 $u$ 的邻居集合
$N u$	顶点 $u$ 的邻居数量
$U j$	Worker $j$ 的上行带宽
$D j$	Worker $j$ 的下行带宽

图2 三角形边的分布

Fig. 2 Distribution of triangle edges

图3 边分发策略时间对比

Fig. 3 Time comparison of edge distribution strategy

表2 计算节点带宽

Tab. 2 Bandwidths of computing nodes

计算节点	上行带宽	下行带宽
Master	10	10
Worker $m$	5	5
Worker $n$	1	5

表2 计算节点带宽

Tab. 2 Bandwidths of computing nodes

计算节点	上行带宽	下行带宽
Master	10	10
Worker $m$	5	5
Worker $n$	1	5

图4 边乱序到达

Fig. 4 Edges arriving disorderly

表3 不同算法的时间和空间复杂度

Tab. 3 Time complexities and space complexities of different algorithms

算法	时间复杂度		空间复杂度
算法	Master	Worker（全部）	Master	Worker（全部）
Tri-Fly	$O (I k)$	$O (I ⋅ m i n (I k, L k))$	$O (k)$	$O (m i n (I k, L k))$
$C o C o S S I M P L E$	$O (I k)$	$O (I ⋅ m i n (I, L k))$	$O (k)$	$O (m i n (I, L k))$
$C o C o S O P T$	$O (I k)$	$O (I ⋅ m i n (I, L k))$	$O (V I + k)$	$O (m i n (I, L k))$
GTC	$O (I k)$	$O (I ⋅ m i n (I, L k))$	$O (V I + k)$	$O (m i n (I, L k))$

表3 不同算法的时间和空间复杂度

Tab. 3 Time complexities and space complexities of different algorithms

算法	时间复杂度		空间复杂度
算法	Master	Worker（全部）	Master	Worker（全部）
Tri-Fly	$O (I k)$	$O (I ⋅ m i n (I k, L k))$	$O (k)$	$O (m i n (I k, L k))$
$C o C o S S I M P L E$	$O (I k)$	$O (I ⋅ m i n (I, L k))$	$O (k)$	$O (m i n (I, L k))$
$C o C o S O P T$	$O (I k)$	$O (I ⋅ m i n (I, L k))$	$O (V I + k)$	$O (m i n (I, L k))$
GTC	$O (I k)$	$O (I ⋅ m i n (I, L k))$	$O (V I + k)$	$O (m i n (I, L k))$

表4 实验数据集属性

Tab. 4 Properties of experimental datasets

名称	顶点数	边数	三角形数
ArXiv	30 565	346 849	988 009
Facebook	61 096	614 797	1 756 259
Email	86 978	297 456	1 180 387
YouTube	3 181 831	7 505 218	7 766 821
LiveJournal	4 847 571	68 993 773	285 730 264

图5 不同算法的通信数据量

Fig. 5 Communication data sizes of different algorithms

表5 不同算法的误差率 ( %)

Tab. 5 Error rates of different algorithms

数据集	Tri-Fly	SIMPLE	OPT	GTC
ArXiv	0.573	0.542	0.310	0.302
Facebook	0.551	0.476	0.273	0.269
Email	0.549	0.539	0.263	0.253
YouTube	0.578	0.495	0.255	0.251
LiveJournal	0.612	0.513	0.254	0.281

表6 不同算法的运行时间 ( s)

Tab. 6 Running time of different algorithms

数据集	Tri-Fly	SIMPLE	OPT	GTC
ArXiv	3.10	2.63	2.23	2.36
Facebook	17.38	14.23	10.27	11.54
Email	16.58	13.03	9.87	10.34
YouTube	223.81	193.77	137.43	145.87
LiveJournal	1 420.82	1 232.47	819.61	854.46

图6 不同θ的GTC通信时间

Fig. 6 Communication time of GTC under different θ

图7 不同L下的算法的误差率

Fig. 7 Error rate of algorithms under different?L

参考文献 25

1	WASSERMAN S， FAUST K. Social Network Analysis： Methods and Applications［M］. Cambridge： Cambridge University Press， 1994： 108-109. 10.1017/s0048840200023959
2	BECCHETTI L， BOLDI P， CASTILLO C， et al. Efficient algorithms for large-scale local triangle counting［J］. ACM Transactions on Knowledge Discovery from Data， 2010， 4（3）： No.13. 10.1145/1839490.1839494
3	金宏桥，董一鸿，陈华辉，等.分布式环境下基于马尔科夫链的图流三角近似计算［J］.电子学报， 2018， 46（9）： 2139-2148. 10.3969/j.issn.0372-2112.2018.09.014
	JIN H Q， DONG Y H， CHEN H H， et al. DATC-MC： Distributed approximate triangle counting based on Markov chain in graph streaming［J］. Acta Electronica Sinica， 2018， 46（9）： 2139-2148. 10.3969/j.issn.0372-2112.2018.09.014
4	KUTZKOV K， PAGH R. On the streaming complexity of computing local clustering coefficients ［C］// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York： ACM， 2013： 677-686. 10.1145/2433396.2433480
5	SHIN K， LEE E， OH J， et al. CoCoS： fast and accurate distributed triangle counting in graph streams［J］. ACM Transactions on Knowledge Discovery from Data， 2021， 15（3）： No.38. 10.1145/3441487
6	SHIN K， HAMMOUD M， LEE E， et al. Tri-Fly： distributed estimation of global and local triangle counts in graph streams ［C］// Proceedings of the 2018 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 10939. Cham： Springer， 2018： 651-663.
7	PU Q F， ANANTHANARAYANAN G， BODIK P， et al. Low latency geo-distributed data analytics［J］. ACM SIGCOMM Computer Communication Review， 2015， 45（4）： 421-434. 10.1145/2829988.2787505
8	NAWAB F， AGRAWAL D， ABBADI A EL. The challenges of global-scale data management ［C］// Proceedings of the 2016 International Conference on Management of Data. New York： ACM， 2016： 2223-2227. 10.1145/2882903.2912571
9	ZHOU A C， SHEN B K， XIAO Y， et al. Cost-aware partitioning for efficient large graph processing in geo-distributed datacenters［J］. IEEE Transactions on Parallel and Distributed Systems， 2020， 31（7）： 1707-1723. 10.1109/tpds.2019.2955494
10	SHIN K. WRS： waiting room sampling for accurate triangle counting in real graph streams ［C］// Proceedings of the 2017 IEEE International Conference on Data Mining. Piscataway： IEEE， 2017： 1087-1092. 10.1109/icdm.2017.143
11	VITTER J S. Random sampling with a reservoir［J］. ACM Transactions on Mathematical Software， 1985， 11（1）： 37-57. 10.1145/3147.3165
12	LIM Y， KANG U. MASCOT： memory-efficient and accurate sampling for counting local triangles in graph streams ［C］// Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2015： 685-694. 10.1145/2783258.2783285
13	TSOURAKAKIS C E， KANG U， MILLER G L， et al. DOULION： counting triangles in massive graphs with a coin ［C］// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 837-846. 10.1145/1557019.1557111
14	DE STEFANI L， EPASTO A， RIONDATO M， et al. TRIÈST： counting local and global triangles in fully dynamic streams with fixed memory size［J］. ACM Transactions on Knowledge Discovery from Data， 2017， 11（4）： No.43. 10.1145/3059194
15	GEMULLA R， LEHNER W， HAAS P J. Maintaining bounded-size sample synopses of evolving datasets［J］. The VLDB Journal， 2008， 17（2）： 173-201. 10.1007/s00778-007-0065-y
16	WANG P H， JIA P， QI Y Y， et al. REPT： a streaming algorithm of approximating global and local triangle counts in parallel ［C］// Proceedings of the IEEE 35th International Conference on Data Engineering. Piscataway： IEEE， 2019： 758-769. 10.1109/icde.2019.00073
17	ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： cluster computing with working sets ［C］// Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing. Berkeley： USENIX Association， 2010： 1-7.
18	GONZALEZ J E， LOW Y C， GU H J， et al. PowerGraph： distributed graph-parallel computation on natural graphs ［C］// Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation. Berkeley： USENIX Association， 2012： 17-30.
19	ABOU-RJEILI A， KARYPIS G. Multilevel algorithms for partitioning power-law graphs ［C］// Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium. Piscataway： IEEE， 2006： 1-10. 10.1109/ipdps.2006.1639360
20	AHMED N K， DUFFIELD N， WILLKE T L， et al. On sampling from massive graph streams［J］. Proceedings of the VLDB Endowment， 2017， 10（11）： 1430-1441. 10.14778/3137628.3137651
21	GEHRKE J， GINSPARG P， KLEINBERG J. Overview of the 2003 KDD Cup［J］. ACM SIGKDD Explorations Newsletter， 2003， 5（2）： 149-151. 10.1145/980972.980992
22	VISWANATH B， MISLOVE A， CHA M， et al. On the evolution of user interaction in Facebook ［C］// Proceedings of the 2nd ACM Workshop on Online Social Networks. New York： ACM， 2009： 37-42. 10.1145/1592665.1592675
23	KLIMT B， YANG Y M. Introducing the Enron corpus［C/OL］// Proceedings of 1st Conference on Email and Anti-Spam ［2022-05-23］. . 10.1007/978-3-540-30115-8_22
24	MISLOVE A E. Online social networks： measurement， analysis， and applications to distributed information systems［R］. Houston， TX： Rice University， 2009： 66-66.
25	BACKSTROM L， HUTTENLOCHER D， KLEINBERG J， et al. Group formation in large social networks： membership， growth， and evolution ［C］// Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2006： 44-54. 10.1145/1150402.1150412

[1]	王熙源, 张战成, 徐少康, 张宝成, 罗晓清, 胡伏原. 面向手术导航3D/2D配准的无监督跨域迁移网络[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2911-2918.
[2]	帅奇, 王海瑞, 朱贵富. 基于双向对比训练的中文故事结尾生成模型[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2683-2688.
[3]	冷强奎, 孙薛梓, 孟祥福. 基于样本势和噪声进化的不平衡数据过采样方法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2466-2475.
[4]	雷明珠, 王浩, 贾蓉, 白琳, 潘晓英. 基于特征间关系合成少数类样本的过采样算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1428-1436.
[5]	郑文萍, 葛慧琳, 刘美麟, 杨贵. 融合二连通模体结构信息的节点分类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1464-1470.
[6]	赵奎, 仇慧琪, 李旭, 徐知非. 结合注意力和多路径融合的实时肺结节检测算法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 945-952.
[7]	邱华禄, 蔺素珍, 王彦博, 刘峰, 李大威. 基于复卷积双域级联网络的欠采样磁共振图像重建算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 580-587.
[8]	李忠雨, 孙浩东, 李娇. 轻量化篮球裁判手势识别算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2173-2181.
[9]	蒋溢, 伍书平, 胡昆, 龙林波. 基于Lasso和构造性覆盖算法的不均衡数据分类方法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1086-1093.
[10]	高健, 李智, 樊缤, 姜传贤. 基于光线投射采样和四元数正交矩的高效三维医学影像鲁棒零水印算法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1191-1197.
[11]	樊小宇, 蔺素珍, 王彦博, 刘峰, 李大威. 基于残差图卷积神经网络的高倍欠采样核磁共振图像重建算法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1261-1268.
[12]	钟新成, 刘昶, 赵秀梅. 基于马尔可夫优化的高效用项集挖掘算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3764-3771.
[13]	虞资兴, 瞿绍军, 何鑫, 王卓. 高低维特征引导的实时语义分割网络[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3077-3085.
[14]	李传彪, 毕远伟. 基于跨域自适应的立体匹配算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3230-3235.
[15]	卢小燕, 徐杨, 袁文昊. 用于肺部病灶图像分割的多尺度稠密融合网络[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3282-3289.

跨域环境下图流三角计数算法GTC

GTC： geo-distributed triangle counting algorithm in graph streams

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 25

相关文章 15

编辑推荐

Metrics