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(h m)$ time, $O(h n+m)$ space; and a colorful $h$-star truss decomposition algorithm which takes $O(h m^{1.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.

I. Introduction

Motifs, also known as graphlets, patterns, or subgraphs, play a crucial role as the foundational elements in networks [1]. The analysis of motifs has proven ingaining insights into network evolution [2], [3], [4], developing advanced graph classification algorithms [5], [6], and fostering cutting-edge clustering techniques [7], [8].valuable in At the core of motif mining and analysis lies the essential task of motif counting, which entails efficiently computing the occurrences of a specific motif (e.g., a triangle, a clique, etc.) within a graph. Moreover, the exploration of motif counting boasts a rich historical background, starting from the origins of triangle counting to its current significant interest in recent years.