Computer Science ›› 2015, Vol. 42 ›› Issue (11): 188-190.doi: 10.11896/j.issn.1002-137X.2015.11.039

Previous Articles     Next Articles

Approximating Triangle Counting Based on Sampling in Complex Networks

HUANG Qu-zhi and ZHANG Jun-chao   

  • Online:2018-11-14 Published:2018-11-14

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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!