Colorful h-star Core Decomposition

The h-clique based higher-order cohesive subgraph mining is an important operator in graph analysis. The h-clique core and h-clique densest subgraph are two representative higher-order cohesive subgraph models which have been widely used in many practical applications. However, computing these two models on large graphs is often very costly due to the hardness of counting the h-cliques. In this paper, we propose a relaxed higher-order cohesive subgraph model, called colorful h-star core, based on counting the number of colorful h-stars. Unlike the h-cliques, we show that the colorful h-stars can be counted and updated very efficiently using a novel dynamic programming (DP) algorithm. Based on the proposed DP algorithm, we develop an efficient colorful h-star core decomposition algorithm which takes O(h × m) time and uses O(h × n+m) space, where m and n denote the number of edges and nodes of the graph respectively. In addition, we also propose a graph reduction technique based on our colorful h-star core model to accelerate the computation of the state-of-the-art approximation algorithm for h-clique densest subgraph mining. Moreover, we show that the colorful h-star core can also provide a very good approximation of the h-clique densest subgraph. The results of comprehensive experiments on 11 large real-world datasets demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.