A faster algorithm for computing c-closure

Abstract

Exploiting the structure of graphs is a well-known strategy for solving hard problems on complex graphs. In our studies we consider structural characteristics of social network graphs, in particular ways to exploit the high frequency of closed triangles due to the property of triadic closure. In recent years this property has been captured in the notion of c-closure introduced by Fox et al.~[SIAM Journal on Computing, 2020]. A graph is c-closed if any two nodes with at least c friends in common are also friends themselves. Multiple NP-complete problems exhibits FPT algorithms parameterized by c. Computing the actual value for c can be done in O(n^ω) time, where ω is the matrix multiplication complexity. We provide an improved algorithm for computing the c-closure of a graph that runs in O(nd³) time for a majority of real-world networks and O(nd³ + n²d) in the worst case. The algorithm exploits another common property of social networks, a low degeneracy value d.