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

摘要

复杂网络中的三角计数可以用于分析网络的同质性和传递性.为了提高复杂网络中三角计数的性能,提出了一种基于采样的近似三角计数方法.首先,以一定的采样概率对网络中的边进行采样从而得到一个子网络,并在该子网络中统计三角的个数.其次,依据采样的概率思想,应用子网络中的三角个数估计原网络中的三角个数.最后,对采样方法的均值和方差进行了理论分析,并给出了由采样方法得到的加速比.理论分析与实验表明,与传统的节点迭代方法相比,提出的方法在保证高准确性的前提下大大提高了算法的运行效率,因而更适用于大规模网络中基于三角计数的相关应用.