TY - GEN
T1 - Spectral counting of triangles in power-law networks via element-wise sparsification
AU - Tsourakakis, Charalampos E.
AU - Drineas, Petross
AU - Michelakis, Eirinaios
AU - Koutis, Ioannis
AU - Faloutsos, Christos
N1 - Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.
PY - 2009
Y1 - 2009
N2 - Triangle counting is an important problem in graph mining. The clustering coefficient and the transitivity ratio, two commonly used measures effectively quantify the triangle density in order to quantify the fact that friends of friends tend to be friends themselves. Furthermore, several successful graph mining applications rely on the number of triangles. In this paper, we study the problem of counting triangles in large, power-law networks. Our algorithm, SPARSIFYINGEIGENTRIANGLE, relies on the spectral properties of power-law networks and the Achlioptas-McSherry sparsification process. SPARSIFYINGEIGENTRIANGLE is easy to parallelize, fast and accurate. We verify the validity of our approach with several experiments in real-world graphs, where we achieve at the same time high accuracy and important speedup versus a straight-forward exact counting competitor.
AB - Triangle counting is an important problem in graph mining. The clustering coefficient and the transitivity ratio, two commonly used measures effectively quantify the triangle density in order to quantify the fact that friends of friends tend to be friends themselves. Furthermore, several successful graph mining applications rely on the number of triangles. In this paper, we study the problem of counting triangles in large, power-law networks. Our algorithm, SPARSIFYINGEIGENTRIANGLE, relies on the spectral properties of power-law networks and the Achlioptas-McSherry sparsification process. SPARSIFYINGEIGENTRIANGLE is easy to parallelize, fast and accurate. We verify the validity of our approach with several experiments in real-world graphs, where we achieve at the same time high accuracy and important speedup versus a straight-forward exact counting competitor.
UR - http://www.scopus.com/inward/record.url?scp=70349838531&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349838531&partnerID=8YFLogxK
U2 - 10.1109/ASONAM.2009.32
DO - 10.1109/ASONAM.2009.32
M3 - Conference contribution
AN - SCOPUS:70349838531
SN - 9780769536897
T3 - Proceedings of the 2009 International Conference on Advances in Social Network Analysis and Mining, ASONAM 2009
SP - 66
EP - 71
BT - Proceedings of the 2009 International Conference on Advances in Social Network Analysis and Mining, ASONAM 2009
T2 - 2009 International Conference on Advances in Social Network Analysis and Mining, ASONAM 2009
Y2 - 20 July 2009 through 22 July 2009
ER -