Triangle counting in large networks: a review
- 6 October 2017
- journal article
- review article
- Published by Wiley in WIREs Data Mining and Knowledge Discovery
- Vol. 8 (2)
Abstract
Counting and enumeration of local topological structures, such as triangles, is an important task for analyzing large real‐life networks. For instance, triangle count in a network is used to compute transitivity—an important property for understanding graph evolution over time. Triangles are also used for various other tasks completed for real‐life networks, including community discovery, link prediction, and spam filtering. The task of triangle counting, though simple, has gained wide attention in recent years from the data mining community. This is due to the fact that most of the existing algorithms for counting triangles do not scale well to very large networks with millions (or even billions) of vertices. To circumvent this limitation, researchers proposed triangle counting methods that approximate the count or run on distributed clusters. In this paper, we discuss the existing methods of triangle counting, ranging from sequential to parallel, single‐machine to distributed, exact to approximate, and off‐line to streaming. We also present experimental results of performance comparison among a set of approximate triangle counting methods built under a unified implementation framework. Finally, we conclude with a discussion of future works in this direction.WIREs Data Mining Knowl Discov2018, 8:e1226. doi: 10.1002/widm.1226This article is categorized under: Algorithmic Development > Structure DiscoveryKeywords
Funding Information
- National Science Foundation (1149851)
This publication has 49 references indexed in Scilit:
- Colorful triangle counting and a MapReduce implementationInformation Processing Letters, 2012
- RAGE – A rapid graphlet enumerator for large networksComputer Networks, 2012
- Main-memory triangle computations for very large (sparse (power-law)) graphsTheoretical Computer Science, 2008
- Biological network comparison using graphlet degree distributionBioinformatics, 2007
- FANMOD: a tool for fast network motif detectionBioinformatics, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Approximating Clustering Coefficient and TransitivityJournal of Graph Algorithms and Applications, 2005
- Birds of a Feather: Homophily in Social NetworksAnnual Review of Sociology, 2001
- Random sampling with a reservoirACM Transactions on Mathematical Software, 1985
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973