Discovering hierarchical subgraphs of K-core-truss

Zhen jun Li, Wei Peng Zhang, Rong Hua Li*, Jun Guo, Xin HUANG, Rui Mao

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


Discovering dense subgraphs in a graph is a fundamental graph mining task, which has a wide range of applications in social networks, biology and graph visualization to name a few. Even the problems of computing most dense subgraphs (e.g., clique, quasi-clique, k-densest subgraph) are NP-hard, there exists polynomial time algorithms for computing k-core and k-truss. In this paper, we propose a novel dense subgraph, (formula presented), that leverages on a new type of important edges based on the concepts of k-core and k-truss. Compared with k-core and k-truss, (formula presented) can significantly discover the interesting and important structural information outside the scope of the k-core and k-truss. We study two useful problems of (formula presented) decomposition and (formula presented) search. In particular, we develop a (formula presented) decomposition algorithm to find all (formula presented) in a graph G by iteratively removing edges with the smallest (formula presented). In addition, we propose a (formula presented) search algorithm to identify a particular (formula presented) 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 the (formula presented) model and proposed algorithms.

Original languageEnglish
Title of host publicationWeb Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings
EditorsLu Chen, Athman Bouguettaya, Andrey Klimenko, Fedor Dzerzhinskiy, Stanislav V. Klimenko, Xiangliang Zhang, Qing Li, Yunjun Gao, Weijia Jia
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783319687827
Publication statusPublished - 2017
Event18th International Conference on Web Information Systems Engineering, WISE 2017 - Puschino, Russian Federation
Duration: 7 Oct 201711 Oct 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10569 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Web Information Systems Engineering, WISE 2017
Country/TerritoryRussian Federation
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Discovering hierarchical subgraphs of K-core-truss'. Together they form a unique fingerprint.

Cite this