Colorful Star Motif Counting: Concepts, Algorithms and Applications

A colorful star motif is a star-shaped graph where any two nodes have different colors. Counting the colorful star motif can help to analyze the structural properties of real-life colorful graphs, model higher-order clustering, and accelerate the mining of the densest subgraph exhibiting h-clique characteristics in graphs. In this manuscript, we introduce the concept of colorful h-star in a colored graph and proposes two higher-order cohesive subgraph models, namely colorful h-star core and colorful h-star truss. 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 a colorful h-star core decomposition algorithm which takes O(hm) time, O(hn + m) space; and a colorful h-star truss decomposition algorithm which takes O(hm1.5) time, O(hm) space, where m and n denote the number of edges and nodes of the graph respectively. Moreover, we also propose a graph reduction technique based on our colorful h-star core model to accelerate the computation of the approximation algorithm for h-clique densest subgraph mining. The results of comprehensive experiments on 11 large real-world datasets demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.