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

Listing dense subgraphs is a fundamental task with a variety of network analytics applications. A lot of research has been done focusing on k-cliques, i.e. complete subgraphs on k nodes. However, requiring complete connectivity between the nodes of a subgraph may be too restrictive in many real applications. Hence, in this paper, we consider a natural relaxation of cliques, called k-diamonds and defined as cliques of size with one missing edge. We first provide a sequential algorithm that counts and lists all the k-diamonds in large graphs, for any constant k⁠. A parallel extension of the sequential algorithm is then proposed and analyzed in a MapReduce-style model, achieving the same local and total space usage of the state-of-the-art algorithms for k-cliques. The running time is optimal on dense graphs and sqrt(m) larger than k-clique counting if the graph is sparse. Our algorithms compute induced diamonds by analyzing the structure of directed stars formed by the graph nodes and their neighbors.