Spectral counting of triangles in power-law networks via element-wise sparsification

Charalampos E. Tsourakakis, Petross Drineas, Eirinaios Michelakis, Ioannis Koutis, Christos Faloutsos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2009 International Conference on Advances in Social Network Analysis and Mining, ASONAM 2009
Pages66-71
Number of pages6
DOIs
StatePublished - 2009
Externally publishedYes
Event2009 International Conference on Advances in Social Network Analysis and Mining, ASONAM 2009 - Athens, Greece
Duration: Jul 20 2009Jul 22 2009

Publication series

NameProceedings of the 2009 International Conference on Advances in Social Network Analysis and Mining, ASONAM 2009

Other

Other2009 International Conference on Advances in Social Network Analysis and Mining, ASONAM 2009
CountryGreece
CityAthens
Period7/20/097/22/09

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Software
  • Social Sciences(all)

Fingerprint Dive into the research topics of 'Spectral counting of triangles in power-law networks via element-wise sparsification'. Together they form a unique fingerprint.

Cite this