From Stars to Diamonds: Counting and Listing Almost Complete Subgraphs in Large Networks.

This article focuses on the problem of enumerating |$k$|-diamonds, defined as cliques of size |$k$| with exactly one missing edge, as a natural relaxation of |$k$|-cliques in graph mining. It presents both a sequential algorithm with running time |$O(nm^{(k-1)/2})$| for counting |$k$|-diamonds in large graphs (for any constant |$k \geq 4$|) and a parallel MapReduce-based algorithm achieving the same asymptotic work and using |$O(m^{3/2})$| total space. The parallel algorithm matches the local and total space usage of state-of-the-art |$k$|-clique listing algorithms, with local running time |$O(nm^{(k-2)/2})$|, and is optimal on dense graphs but incurs an |$O(\sqrt{m})$| overhead compared to clique counting on sparse graphs. The work includes a structural classification of |$k$|-diamonds based on node degrees and edge orientations, enabling efficient enumeration without repetitions in both sequential and distributed settings.