复杂网络中基于采样的近似三角计数方法研究  

Approximating Triangle Counting Based on Sampling in Complex Networks

作　　者：黄取治[1] 张军朝[2] 

机构地区：[1]福建师范大学信息技术学院,福州350007 [2]太原理工大学计算机科学与技术学院,太原030024

出　　处：《计算机科学》2015年第11期188-190,227,共4页Computer Science

基　　金：国家自然科学基金(60443004)资助

摘　　要：复杂网络中的三角计数可以用于分析网络的同质性和传递性。为了提高复杂网络中三角计数的性能,提出了一种基于采样的近似三角计数方法。首先,以一定的采样概率对网络中的边进行采样从而得到一个子网络,并在该子网络中统计三角的个数。其次,依据采样的概率思想,应用子网络中的三角个数估计原网络中的三角个数。最后,对采样方法的均值和方差进行了理论分析,并给出了由采样方法得到的加速比。理论分析与实验表明,与传统的节点迭代方法相比,提出的方法在保证高准确性的前提下大大提高了算法的运行效率,因而更适用于大规模网络中基于三角计数的相关应用。Counting of triangles in complex networks is the basis for research on homophily and transitivity. In order to improve the performance of triangles counting, this paper proposed a sampling based approximating triangle counting al- gorithm. Firstly, we sampled every edge in a graph with constant probability,and counted the number of triangles in the sub-graph. Secondly, based on probability theory of sampling, we approximated the number of triangles in the original graph with the induced sub-graph. Finally, we analyzed the mean and variance of our proposed sampling method, and gave its corresponding speedup. Theoretical analysis and experiments show that, compared with the classic node itera- tion approach, the proposed algorithm improves the execution time a lot while keeping high accuracy, and thus is more suitable for triangle counting based applications in large scale networks.

关 键 词：复杂网络 采样 三角计数 同质性 近似算法 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]