论文部分内容阅读
图作为一种数据结构,由于其丰富的表达能力,常用于复杂模型建模,如生物化学、神经生物学、生态、社会科学和信息系统等领域数据建模。在图论中,团是一个无向图顶点的子集,顶点集中每两个不同的顶点都是相邻的,也就是说,顶点集的诱导子图是一个完全图。团结构是图论的基本概念之一,在许多数学问题和相关应用领域中有这广泛的应用。随着信息技术的快速发展,图数据的规模呈爆炸性增长。以Facebook为例,截至2011年,在Facebook的社交网络中有超过7.21亿活跃用户,如把每一个用户看做成一个节点,则形成一个具有690亿个边的大规模图。面向大规模图,高效地计算三角形(三顶点团)和四顶点团,解决团计数的高时间复杂度和空间复杂度问题,正成为当前图数据处理研究领域重要研究方向之一。当前主流的团数计算方法,如矩阵相乘算法、点边迭代算法、基于图划分算法、multiple-passes算法等,普遍存在准确率偏低以及时间复杂度偏高(O(n~2)~O(n~3))的问题,针对于此,本文利用采样理论,研究了三角形和四顶点团的近似计算方法,主要内容包括:(1)提出了一种优化的基于邻接边采样的图三角形近似计算方法NSAMP-TRIANGLE。NSAMP-TRIANGLE通过改进的三角形采样(Triangle-Sample)算法完成三角形抽取,并根据单次采样成功率对图中三角形总数进行估计。然后,根据切尔诺夫界的相对误差理论,在给定三角形总数误差?和置信度?的情况下,确定采样次数k。最后,求出k次试验结果的期望值,即为最终图中三角形数量的估计值。NSAMP-TRIANGLE通过水库采样正向和反向扫描两次数据集,采样的时间复杂度降低至O(2kn),空间复杂度为O(k)。(2)在NSAMP-TRIANGLE算法的基础上,提出了NSAMP-4CLIQUES算法,实现了对四顶点团的采样和数量估算方法。针对NSAMP-4CLIQUES中四顶点团的采样成功概率低的问题,提出了有偏四顶点团采样,使得采样倾向于顶点度高的三角形,进而提高四顶点团采样成功率。NSAMP-4CLIQUES算法时间复杂度为O(2kn~2),空间复杂度为O(k)。(3)在Amazon、DBLP、YouTube、LiveJournal、Orkut和Hep-th等数据集上进行了大量的实验验证。实验结果表明,同传统的三角形计算方法相比,NSAMP-TRIANGLE的时间效率提高了20%~50%,准确率提高了5%~13%。NSAMP-4CLIQUES的运行时间平均约为40秒,准确率约为80.4%。本文所提方法适用于大规模图中的三角形和四顶点团的近似计算。