关键词: 图, 核分解, 高阶内聚子图模型, 上界

Abstract: The colorful h-star core is a cohesive subgraph model defined based on colorful h-stars,which has a wide range of applications in understanding the complex relationships of networks and analyzing the higher-order structure of communities.However,the existing colorful h-star core decomposition algorithms have significant limitations:as the h-value increases,the h-star degree grows exponentially,which is prone to data overflow and leads to erroneous computation results.To address this problem,this paper proposes a pruning method to identify the vertices that have no effect on the h-star core number,and further derives a tight upper bound for the h-star core number by mathematical derivation,which can effectively replace the h-star degree during the core decomposition process,thus solving the problem of computational errors due to the excessive h-star.Experimental results show that the proposed method can correctly compute the h-star core decomposition with more than 10 times improvement in computational efficiency.

Key words: Graph, Core decomposition, High-order cohesive subgraph model, Upper bound