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, $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ 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 $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ truss model. Compared to k -core and k -truss, $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ 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 $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ truss decomposition and $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ truss search. In particular, we develop a k -core-truss decomposition algorithm to find all $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ truss in a graph G by iteratively removing edges with the smallest $${mathsf {degree}}$$ degree - $${mathsf {support}}$$ support . In addition, we offer a $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ truss search algorithm to identifying a particular $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ 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 $${mathsf {k}}$$ k - $${mathsf {core}}$$ core - $${mathsf {truss}}$$ truss model and proposed algorithms.
展开▼
