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

doi:10.11896/j.issn.1002-137X.2015.11.039

摘要/Abstract

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

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

Abstract: 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 algorithm.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 iteration 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.

Key words: Complex networks,Sampling,Triangle counting,Homophily,Approximation algorithm

黄取治,张军朝. 复杂网络中基于采样的近似三角计数方法研究[J]. 计算机科学, 2015, 42(11): 188-190. https://doi.org/10.11896/j.issn.1002-137X.2015.11.039

HUANG Qu-zhi and ZHANG Jun-chao. Approximating Triangle Counting Based on Sampling in Complex Networks[J]. Computer Science, 2015, 42(11): 188-190. https://doi.org/10.11896/j.issn.1002-137X.2015.11.039

参考文献

[1] 张建明,林亚平,周四望,等.传感器网络中误差有界的小波数据压缩算法[J].软件学报,2010,21(6):1364-1377 Zhang Jian-ming,Lin Ya-ping,Zhou Si-wang,et al.Haar Wavelet Data Compression Algorithm with Error Bound for Wireless Sensor Networks[J].Journal of Software,2010,1(6):1364-1377
[2] 张聪,沈惠璋.基于谱方法的复杂网络中社团结构的模块度[J].系统工程理论与实践,2013,33(5):1231-1239 Zhang Cong,Shen Hui-zhang.Modularity for community structure in complex networks based on spectral method[J].Systems Engineering-Theory & Practice ,2013,3(5):1231-1239
[3] 黄萍,张许杰,刘刚.小世界网络的研究现状与展望[J].情报杂志,2011,26(4):66-68Huang Ping,Zhang Xu-jie,Liu Gang.The Present Research Si-tuation and Forecast of the Small World Network[J].Journal of Information,2011,6(4):66-68
[4] Tsourakakis C E.Fast counting of triangles in large real net-works without counting:Algorithms and laws[C]∥ The Eighth IEEE International Conference on Data Mining,2008.IEEE,2008:608-617
[5] Centola D.An experimental study of homophily in the adoption of health behavior[J].Science,2011,334(6060):1269-1272
[6] Wittkop T,Rahmann S,Rttger R,et al.Extension and robustness of transitivity clustering for protein-protein interaction network analysis[J].Internet Mathematics,2011,7(4):255-273
[7] Becchetti L,Boldi P,Castillo C,et al.Efficient semi-streaming algorithms for local triangle counting in massive graphs[C]∥Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2008:16-24
[8] Eckmann J P,Moses E.Curvature of co-links uncovers hiddenthematic layers in the world wide Web[J].Proceedings of the National Academy of Sciences,2012,99(9):5825-5829
[9] Bar-Yossef Z,Kumar R,Sivakumar D.Reductions in streaming algorithms,with an application to counting triangles in graphs[C]∥Proceedings of the Thirteenth annual ACM-SIAM Symposium on Discrete Algorithms.2012:623-632
[10] 陈学工,邱华,付金华,等.基于三角形不规则网模型的快速体素化方法[J].计算机应用,2010,30(12):3281-3283 Chen Xue-gong,Qiu Hua,Fu Jin-hua,et al.Fast voxelization based on triangulated irregular network model[J].Journal of Computer Applications,2010,0(12):3281-3283
[11] Schank T,Wagner D.Finding,counting and listing all triangles in large graphs,an experimental study[M]∥Experimental and Efficient Algorithms.Springer Berlin Heidelberg,2005:606-609
[12] Lind P G,González M C,Herrmann H J.Cycles and clustering in bipartite networks[J].Physical Review E,2005,72(5):056127
[13] 彭宇,罗清华,彭喜元.网络化测试体系中不确定性数据处理方法浅析 [J].仪器仪表学报,2010,31(1):229-240 Peng Yu,Luo Qing-hua,Peng Xi-yuan.Analysis of uncertain data processing methods in networking test framework[J].Chinese Journal of Scientific Instrument,2010,1(1):229-240
[14] Jowhari H,Ghodsi M.New streaming algorithms for countingtriangles in graphs[M]∥Computing and Combinatorics.Sprin-ger Berlin Heidelberg,2005:710-716
[15] Buriol L S,Frahling G,Leonardi S,et al.Counting triangles in data streams[C]∥Proceedings of the Twenty-fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.ACM,2006:253-262
[16] Becchetti L,Boldi P,Castillo C,et al.Efficient semi-streaming algorithms for local triangle counting in massive graphs[C]∥Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2008:16-24
[17] Pavan A,Tangwongsan K,Tirthapura S,et al.Counting andsampling triangles from a graph stream[J].Proceedings of the VLDB Endowment,2013,6(14):1870-1881
[18] Gong B,Yang L,Yang K.Synchronization on Erds-Rényi networks[J].Physical Review E,2005,72(3):037101
[19] 吴渝,杨涛,肖开洲.BBS突发舆情分析及基于小世界网络的预测模型[J].重庆邮电大学学报(自然科学版),2010,22(3):350-354 Wu Yu,Yang Tao,Xiao Kai-zhou.Analysis of emergent BBS sentiment and its prediction model based on small world network[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2010,22(3):350-354

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed