Simple And Efficient Four-cycle Counting On Sparse Graphs

Burkhardt Paul, Harris David G.. Arxiv 2023

[Paper]    
ARXIV Graph

We consider the problem of counting 4-cycles ($C_4$) in an undirected graph $G$ of $n$ vertices and $m$ edges (in bipartite graphs, 4-cycles are also often referred to as $\mathit{\text{butterflies}}$). Most recently, Wang et al. (2019, 2022) developed algorithms for this problem based on hash tables and sorting the graph by degree. Their algorithm takes $O(m\overline{\delta })$ expected time and $O(m)$ space, where $\overline{\delta }\le O(\sqrt{m})$ is the $\mathit{\text{averagedegeneracy}}$ parameter introduced by Burkhardt, Faber \& Harris (2020). We develop a streamlined version of this algorithm requiring $O(m\overline{\delta })$ time and precisely $n$ words of space. It has several practical improvements and optimizations; for example, it is fully deterministic, does not require any auxiliary storage or sorting of the input graph, and uses only addition and array access in its inner loops. Our algorithm is very simple and easily adapted to count 4-cycles incident to each vertex and edge. Empirical tests demonstrate that our array-based approach is $4\times$ – $7\times$ faster on average compared to popular hash table implementations.

Similar Work

• General Graph Identification By Hashing
• Edge Sampling And Graph Parameter Estimation Via Vertex Neighborhood Accesses
• An O(N) Sorting Algorithm Machine Learning Sort
• Learning-based Efficient Graph Similarity Computation Via Multi-scale Convolutional Set Matching