The k-Trine Cohesive Subgraph and Its Efficient Algorithms

In this paper, we introduce and study a novel cohesive subgraph model, named k-trine, to address the defects in the classical k-core and k-truss models. Our analysis shows that the k-trine is a more feasible model for capturing cohesive subgraphs by containing the strongly connected vertices. We analyze the theoretical properties of k-trine and propose efficient algorithms to compute the k-trine. Particularly, we design batch processing algorithms to update the decomposition of k-trine against highly dynamic graphs. Extensive experiments on real-world networks validate the effectiveness of the k-trine model and the efficiency of our algorithms.