z-logo
Premium
Triangle counting in large networks: a review
Author(s) -
Al Hasan Mohammad,
Dave Vachik S.
Publication year - 2017
Publication title -
wiley interdisciplinary reviews: data mining and knowledge discovery
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.506
H-Index - 47
eISSN - 1942-4795
pISSN - 1942-4787
DOI - 10.1002/widm.1226
Subject(s) - enumeration , computer science , counting problem , property (philosophy) , task (project management) , theoretical computer science , simple (philosophy) , set (abstract data type) , graph , algorithm , mathematics , discrete mathematics , philosophy , management , epistemology , economics , programming language
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 Discov 2018, 8:e1226. doi: 10.1002/widm.1226 This article is categorized under: Algorithmic Development > Structure Discovery

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here