Discovering Hierarchical Subgraphs of K-Core-Truss

Discovering dense subgraphs in a graph is a fundamental graph mining task, which has a wide range of applications in social networks, biology and visualization to name a few. Even the problem of computing most cohesive subgraphs is NP-hard (like clique, quasi-clique, k-densest subgraph), there exists a polynomial time algorithm for computing the k-core and k-truss. In this paper, we propose a novel dense subgraph model, k-core-truss, which leverages on a new type of important edges based on the basis of k-core and k-truss. We investigate the structural properties of the k-core-truss model. Compared to k-core and k-truss, k-core-truss can significantly discover the interesting and important structural information out the scope of k-core and k-truss. We study two useful problems of k-core-truss decomposition and k-core-truss search. In particular, we develop a k-core-truss decomposition algorithm to find all k-core-truss in a graph G by iteratively removing edges with the smallest degree-support. In addition, we offer a k-core-truss search algorithm to identifying a particular k-core-truss containing a given query node such that the core number k is the largest. Extensive experiments on several web-scale real-world datasets show the effectiveness and efficiency of k-core-truss model and proposed algorithms.