Discovering Hierarchical Subgraphs of K-Core-Truss

Data Science and Engineering

Rong-Hua Li¹  Xin Huang²  Jun Guo³  Zhenjun Li³  Wei-Peng Zhang³  Rui Mao³  Yunting Lu⁴ 

[1] Beijing institute of technology;Hong Kong Baptist University;Shenzhen University;Shenzhen institute of information technology;

关键词: Cohesive subgraph model;    Community search;    k-core-truss;    k-core;    k-truss;   

DOI  :  10.1007/s41019-018-0068-2

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown