Colorful Star Motif Counting: Concepts, Algorithms and Applications

Hongchao Qin, Sen Gao, Rong Hua Li*, Hongzhi Chen, Ye Yuan, Guoren Wang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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 takesO(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.

Original languageEnglish
Pages (from-to)1105-1125
Number of pages21
JournalIEEE Transactions on Knowledge and Data Engineering
Volume37
Issue number3
DOIs
Publication statusPublished - 2025

Keywords

  • Colorful star
  • H-clique densest subgraph
  • K-core
  • K-truss

Fingerprint

Dive into the research topics of 'Colorful Star Motif Counting: Concepts, Algorithms and Applications'. Together they form a unique fingerprint.

Cite this

Qin, H., Gao, S., Li, R. H., Chen, H., Yuan, Y., & Wang, G. (2025). Colorful Star Motif Counting: Concepts, Algorithms and Applications. IEEE Transactions on Knowledge and Data Engineering, 37(3), 1105-1125. https://doi.org/10.1109/TKDE.2024.3514997