Discovering Hierarchical Subgraphs of K-Core-Truss

Zhenjun Li*, Yunting Lu, Wei Peng Zhang, Rong Hua Li, Jun Guo, Xin HUANG, Rui Mao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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

Original languageEnglish
Pages (from-to)136-149
Number of pages14
JournalData Science and Engineering
Volume3
Issue number2
DOIs
Publication statusPublished - 1 Jun 2018

Scopus Subject Areas

  • Computational Mechanics
  • Computer Science Applications

User-Defined Keywords

  • Cohesive subgraph model
  • Community search
  • k-core
  • k-core-truss
  • k-truss

Fingerprint

Dive into the research topics of 'Discovering Hierarchical Subgraphs of K-Core-Truss'. Together they form a unique fingerprint.

Cite this