金宏桥，董一鸿

（宁波大学信息科学与工程学院，浙江 宁波 315211）

综述

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

金宏桥，董一鸿

（宁波大学信息科学与工程学院，浙江 宁波 315211）

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

准确计算；近似计算；三角形；图

1 引言

随着网络技术和社会网络服务的发展，网络中的数据量和信息量越来越大。在这种大数据的环境下，对数据的分析和挖掘显得尤为重要。近年来，对有大规模数据的网络的分析得到越来越多的关注。计算机学科的数据结构图可以作为很多种网络的模型，如万维网、P2P 网络和社交网络等都可以用含有特定信息的图作为它们的模型。对网络的分析逐渐转化为对保存网络重要信息的图的分析。由于网络中的关系和个体数量非常多，所以作为其模型的图的规模也很大。

社会网络的同质性和传递性产生了对图中三角形的研究。图中的三角形是复杂网络分析的重要角色，不论是来自社会交互、计算机交流、金融交易、蛋白质还是生态学网络，其中三角形的数量都是巨大的，它在这些领域中有着非常广泛的应用。……