Data Science and Engineering (Jul 2018)

Discovering Hierarchical Subgraphs of K-Core-Truss

  • Zhenjun Li,
  • Yunting Lu,
  • Wei-Peng Zhang,
  • Rong-Hua Li,
  • Jun Guo,
  • Xin Huang,
  • Rui Mao

DOI
https://doi.org/10.1007/s41019-018-0068-2
Journal volume & issue
Vol. 3, no. 2
pp. 136 – 149

Abstract

Read online

Abstract 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.

Keywords