Using Large Cliques for Hierarchical Dense Subgraph Discovery

Understanding the structure of dense regions in real-world networks is an important research area with myriad practical applications. Using higher-order structures (motifs), such as triangles, had been shown to be effective to locate the dense subgraphs. However, going beyond the triangle structure is computationally demanding and mostly overlooked in the past. In this work, we investigate the use of large cliques (up to 10 nodes) for dense subgraph discovery. Relying on the nucleus decomposition framework that finds hierarchical dense subgraphs, we introduce efficient implementations to instantiate the framework up to 10-cliques. We analyze various real-world networks and discuss the density pointers, dense subgraph distributions, and also the hierarchical relationships. We investigate the clique count distributions per vertex and report surprising behaviors that are not observed in the degree distributions. Our analysis shows that utilizing larger cliques can yield denser structures with more interesting hierarchical relations in several networks.