Triangle Counting by Adaptively Resampling over Evolving Graph Streams
Wei Xuan · Proceedings/Proceedings of the ... International Conference on Software Engineering and Knowledge Engineering · 2021
Triangle counting is a fundamental graph mining problem, widely used in many real-world application scenarios.Due to the large scale of graph streams and limited memory space, it is appropriate to achieve the estimation of global and local triangles by sampling.Existing streaming algorithms for triangle counting can be generalized into two categories.One is Reservoir-based methods employing a fixed memory budget, whose size is difficult to set for accurate estimation without any prior knowledge about graph streams.The other is Bernoullibased methods, which sample edges by a given probability with uncontrollable memory budget.In this work, we propose a novel and bounded-sampling-ratio method, called BSR-Sample, by adaptively resizing memory budget upwards over evolving graph streams.BSR-Sample can keep the sampling ratio always greater than or equal to a specified threshold with available memory space.Then, we design BSR-TC, a single-pass streaming algorithm for both global and local triangle counting, based on BSR-Sample.Experimental results show that BSR-TC achieves accuracy of at least 99.8% for global triangles, when the ratio of initial memory budget to whole graph streams ≥ 0.002% and given threshold = 20%.And our proposed BSR-TC can gain more advantage than the state-of-the-art algorithms over the continuous growth of graph streams.