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 -cliques, i.e. complete subgraphs on 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 -diamonds and defined as cliques of size with one missing edge. We first provide a sequential algorithm that, in time, counts and lists all the -diamonds in large graphs, for any constant ⁠. 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 -cliques. The running time is optimal on dense graphs and larger than -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.