Vertex Hashing Assignment‐Based Distributed Sampling Algorithm for Large‐Scale Dynamic Graph Stream

Full abstract

Read the full abstract

ABSTRACT In recent years, research on triangle counting in large graphs has primarily focused on estimating the number of triangles in static graphs. Most streaming graph sampling algorithms are only capable of estimating triangle counts in static graphs and cannot handle dynamic graphs. Meanwhile, existing dynamic streaming graph sampling algorithms suffer from low estimation accuracy. To address these issues, we propose VHADS (Vertex Hashing Assignment‐based Distributed Sampling), a distributed sampling algorithm designed for estimating the number of triangles in large‐scale dynamic graph streams within a cluster environment. As a distributed streaming algorithm, VHADS effectively organises the edge data processed by worker nodes through a vertex‐hash allocation strategy, ensuring that each triangle is sampled by only one worker node in the cluster. This significantly increases the probability of triangle sampling and effectively reduces estimation errors. Compared to state‐of‐the‐art streaming sampling algorithms, VHADS offers the following advantages: (1) With the same sample size, VHADS achieves lower estimation errors in a shorter runtime, reducing the average error in global triangle counting by 72.05% and the average error in local triangle counting by 69.31%; (2) VHADS provides an unbiased estimation of triangle counts in dynamic streaming graphs, and rigorous theoretical analysis demonstrates that it achieves a higher triangle sampling probability.