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 contributionpeer-review

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 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
Pages441-456
Number of pages16
ISBN (Print)9783319687827
DOIs
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

Conference

Conference18th International Conference on Web Information Systems Engineering, WISE 2017
Country/TerritoryRussian Federation
CityPuschino
Period7/10/1711/10/17

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this