Logo image
Back
Edge Sample and Discard: A New Algorithm for Counting Triangles in Large Dynamic Graphs
Conference proceeding

Edge Sample and Discard: A New Algorithm for Counting Triangles in Large Dynamic Graphs

Guyue Han and Harish Sethu
2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)
Jul 2017
DOI: https://doi.org/10.1145/3110025.3110061

Abstract

Monitoring key properties of dynamic graphs in real time can help detect spam accounts in social networks, identify anomalies and intrusions, and inform resource management. Traditional frameworks for dynamic graphs have relied on processing only the stream of edges added into or deleted from an evolving graph, but not any additional related information such as the degrees or neighbor lists of nodes associated with the edges. In this paper, we propose a new edge sampling framework for big-graph analytics in dynamic graphs which enhances the traditional model and offers significantly improved trade-off between accuracy and computational/memory costs in the running estimates of a graph's properties. To demonstrate this higher accuracy using the framework, we present a new sampling algorithm, called Edge Sample and Discard, which generates an unbiased estimate of the total number of triangles in a fully dynamic graph. The experimental results show that, with the help of the neighborhood information of the sampled edges, the accuracy achieved by our algorithm is substantially better than the accuracy achieved by current state-of-the-art algorithms.

Metrics

7 Record Views
15 citations in Scopus

Details

Logo image