摘要
复杂网络中的三角计数可以用于分析网络的同质性和传递性。为了提高复杂网络中三角计数的性能,提出了一种基于采样的近似三角计数方法。首先,以一定的采样概率对网络中的边进行采样从而得到一个子网络,并在该子网络中统计三角的个数。其次,依据采样的概率思想,应用子网络中的三角个数估计原网络中的三角个数。最后,对采样方法的均值和方差进行了理论分析,并给出了由采样方法得到的加速比。理论分析与实验表明,与传统的节点迭代方法相比,提出的方法在保证高准确性的前提下大大提高了算法的运行效率,因而更适用于大规模网络中基于三角计数的相关应用。
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.
出处
《计算机科学》
CSCD
北大核心
2015年第11期188-190,227,共4页
Computer Science
基金
国家自然科学基金(60443004)资助
关键词
复杂网络
采样
三角计数
同质性
近似算法
Complex networks, Sampling, Triangle counting, Homophily, Approximation algorithm
