Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation

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

Research output: Contribution to journalArticlepeer-review

23 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 the graph. 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 considerable speedup versus a straight-forward exact counting competitor. Finally, our contributions include a simple method for making link recommendations in online social networks based on the number of triangles as well as a procedure for estimating triangles using sketches.

Original languageEnglish (US)
Pages (from-to)75-81
Number of pages7
JournalSocial Network Analysis and Mining
Volume1
Issue number2
DOIs
StatePublished - Jan 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Communication
  • Media Technology
  • Human-Computer Interaction
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation'. Together they form a unique fingerprint.

Cite this