Discovering hierarchical subgraphs of K-core-truss

Zhen jun Li; Wei Peng Zhang; Rong Hua Li; Jun Guo; Xin Huang; Rui Mao

doi:10.1007/978-3-319-68783-4_30

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

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-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 language	English
Title of host publication	Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings
Editors	Lu Chen, Athman Bouguettaya, Andrey Klimenko, Fedor Dzerzhinskiy, Stanislav V. Klimenko, Xiangliang Zhang, Qing Li, Yunjun Gao, Weijia Jia
Publisher	Springer Verlag
Pages	441-456
Number of pages	16
ISBN (Print)	9783319687827
DOIs	https://doi.org/10.1007/978-3-319-68783-4_30
Publication status	Published - 2017
Event	18th International Conference on Web Information Systems Engineering, WISE 2017 - Puschino, Russian Federation Duration: 7 Oct 2017 → 11 Oct 2017 https://link.springer.com/book/10.1007/978-3-319-68783-4

Publication series

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

Conference

Conference	18th International Conference on Web Information Systems Engineering, WISE 2017
Country/Territory	Russian Federation
City	Puschino
Period	7/10/17 → 11/10/17
Internet address	https://link.springer.com/book/10.1007/978-3-319-68783-4

Access to Document

10.1007/978-3-319-68783-4_30

Cite this

Li, Z. J., Zhang, W. P., Li, R. H., Guo, J., Huang, X., & Mao, R. (2017). Discovering hierarchical subgraphs of K-core-truss. In L. Chen, A. Bouguettaya, A. Klimenko, F. Dzerzhinskiy, S. V. Klimenko, X. Zhang, Q. Li, Y. Gao, & W. Jia (Eds.), Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings (pp. 441-456). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10569 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-68783-4_30

Li, Zhen jun ; Zhang, Wei Peng ; Li, Rong Hua et al. / Discovering hierarchical subgraphs of K-core-truss. Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. editor / Lu Chen ; Athman Bouguettaya ; Andrey Klimenko ; Fedor Dzerzhinskiy ; Stanislav V. Klimenko ; Xiangliang Zhang ; Qing Li ; Yunjun Gao ; Weijia Jia. Springer Verlag, 2017. pp. 441-456 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1b3c395e5e6b42268c5fdab471775c5a,

title = "Discovering hierarchical subgraphs of K-core-truss",

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

author = "Li, \{Zhen jun\} and Zhang, \{Wei Peng\} and Li, \{Rong Hua\} and Jun Guo and Xin Huang and Rui Mao",

note = "Funding Information: Acknowledgement. We thank anonymous reviewers for their insightful comments. The work was supported in part by NSFC Grants (61402292, U1301252, 61033009), NSF-Shenzhen Grants (JCYJ20150324140036826, JCYJ20140418095735561), and Startup Grant of Shenzhen Kongque Program (827/000065).; 18th International Conference on Web Information Systems Engineering, WISE 2017 ; Conference date: 07-10-2017 Through 11-10-2017",

year = "2017",

doi = "10.1007/978-3-319-68783-4\_30",

language = "English",

isbn = "9783319687827",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "441--456",

editor = "Lu Chen and Athman Bouguettaya and Andrey Klimenko and Fedor Dzerzhinskiy and Klimenko, \{Stanislav V.\} and Xiangliang Zhang and Qing Li and Yunjun Gao and Weijia Jia",

booktitle = "Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings",

address = "Germany",

url = "https://link.springer.com/book/10.1007/978-3-319-68783-4",

}

Li, ZJ, Zhang, WP, Li, RH, Guo, J, Huang, X & Mao, R 2017, Discovering hierarchical subgraphs of K-core-truss. in L Chen, A Bouguettaya, A Klimenko, F Dzerzhinskiy, SV Klimenko, X Zhang, Q Li, Y Gao & W Jia (eds), Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10569 LNCS, Springer Verlag, pp. 441-456, 18th International Conference on Web Information Systems Engineering, WISE 2017, Puschino, Russian Federation, 7/10/17. https://doi.org/10.1007/978-3-319-68783-4_30

Discovering hierarchical subgraphs of K-core-truss. / Li, Zhen jun; Zhang, Wei Peng; Li, Rong Hua et al.
Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. ed. / Lu Chen; Athman Bouguettaya; Andrey Klimenko; Fedor Dzerzhinskiy; Stanislav V. Klimenko; Xiangliang Zhang; Qing Li; Yunjun Gao; Weijia Jia. Springer Verlag, 2017. p. 441-456 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10569 LNCS).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

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 - Funding Information: Acknowledgement. We thank anonymous reviewers for their insightful comments. The work was supported in part by NSFC Grants (61402292, U1301252, 61033009), NSF-Shenzhen Grants (JCYJ20150324140036826, JCYJ20140418095735561), and Startup Grant of Shenzhen Kongque Program (827/000065).

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 - https://www.scopus.com/pages/publications/85031421802

U2 - 10.1007/978-3-319-68783-4_30

DO - 10.1007/978-3-319-68783-4_30

M3 - Conference proceeding

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 -

Li ZJ, Zhang WP, Li RH, Guo J, Huang X, Mao R. Discovering hierarchical subgraphs of K-core-truss. In Chen L, Bouguettaya A, Klimenko A, Dzerzhinskiy F, Klimenko SV, Zhang X, Li Q, Gao Y, Jia W, editors, Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. Springer Verlag. 2017. p. 441-456. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-68783-4_30

Discovering hierarchical subgraphs of K-core-truss

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this