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 <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-clique characteristics in graphs. In this manuscript, we introduce the concept of colorful <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-star in a colored graph and proposes two higher-order cohesive subgraph models, namely colorful <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-star core and colorful <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-star truss. We show that the colorful <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-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 <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-star core decomposition algorithm which takes <inline-formula><tex-math notation="LaTeX">$O(h m)$</tex-math></inline-formula> time, <inline-formula><tex-math notation="LaTeX">$O(h n+m)$</tex-math></inline-formula> space; and a colorful <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-star truss decomposition algorithm which takes <inline-formula><tex-math notation="LaTeX">$O(h m^{1.5})$</tex-math></inline-formula> time, <inline-formula><tex-math notation="LaTeX">$O(hm)$</tex-math></inline-formula> space, where <inline-formula><tex-math notation="LaTeX">$m$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> denote the number of edges and nodes of the graph respectively. Moreover, we also propose a graph reduction technique based on our colorful <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-star core model to accelerate the computation of the approximation algorithm for <inline-formula><tex-math notation="LaTeX">$ h$</tex-math></inline-formula>-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.