We present a new randomized algorithm for estimating the number of triangles in massive graphs revealed as a stream of edges in arbitrary order. It exploits the fact that graphs arising from various domains often have small vertex covers, which enables us to reduce the space usage and sample complexity of triangle counting algorithms. The algorithm runs in four passes over the edge set and uses constant processing time per edge. We obtain precise bounds on the complexity and the approximation guarantee of our algorithm. For graphs where even the minimum vertex cover is prohibitively large, we extend the approach to achieve a trade-off between the number of passes and the space usage. Experiments on real-world graphs validate our theoretical analysis and show that the new algorithm yields more accurate estimates than state-of- the-art approaches using the same amount of space.
展开▼
