Non-Interactive Butterfly Counting in Bipartite Graphs Based on Local Differential Privacy

Counting butterflies in bipartite graphs is a fundamental task that has gained increasing attention. Estimating butterfly counts with edge local differential privacy for privacy protection is meaningful. Existing methods struggle to balance estimation accuracy, running efficiency, user synchronization and communication cost. We propose 2-path-based butterfly counting (PBC), which accurately and efficiently counts the number of butterflies in bipartite graphs in a non-interactive manner. PBC enhances running efficiency by transforming the butterfly count into a function of the 2-path count, and improves estimation accuracy with an unbiased estimation of the butterfly count. Additionally, PBC includes privacy budget allocation that minimizes the variance of the 2-path count. We evaluate PBC on four real-world datasets, demonstrating it's superior estimation accuracy and running efficiency compared to existing methods.