TY - GEN
T1 - Discovering hierarchical subgraphs of K-core-truss
AU - Li, Zhen jun
AU - Zhang, Wei Peng
AU - Li, Rong Hua
AU - Guo, Jun
AU - Huang, Xin
AU - Mao, Rui
N1 - Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85031421802&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-68783-4_30
DO - 10.1007/978-3-319-68783-4_30
M3 - Conference contribution
AN - SCOPUS:85031421802
SN - 9783319687827
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 441
EP - 456
BT - Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings
A2 - Chen, Lu
A2 - Bouguettaya, Athman
A2 - Klimenko, Andrey
A2 - Dzerzhinskiy, Fedor
A2 - Klimenko, Stanislav V.
A2 - Zhang, Xiangliang
A2 - Li, Qing
A2 - Gao, Yunjun
A2 - Jia, Weijia
PB - Springer Verlag
T2 - 18th International Conference on Web Information Systems Engineering, WISE 2017
Y2 - 7 October 2017 through 11 October 2017
ER -