Efficient progressive minimum k-core search

Li, C; Zhang, F; Zhang, Y; Qin, L; Zhang, W; Lin, X

Efficient progressive minimum k-core search

Li, C

Zhang, F Zhang, Y

Qin, L

Zhang, W Lin, X

Permalink

Publisher:: VLDB Endowment
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2020, 13, (3), pp. 361-374
Issue Date:: 2020-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (1.01 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Li, C https://orcid.org/0000-0002-6164-2643
dc.contributor.author	Zhang, F
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.date.accessioned	2021-04-19T00:21:55Z
dc.date.available	2021-04-19T00:21:55Z
dc.date.issued	2020-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2020, 13, (3), pp. 361-374
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/148193
dc.description.abstract	As one of the most representative cohesive subgraph models, k-core model has recently received significant attention in the literature. In this paper, we investigate the problem of the minimum k-core search: given a graph G, an integer k and a set of query vertices Q = q, we aim to find the smallest k-core subgraph containing every query vertex q ∈ Q. It has been shown that this problem is NP-hard with a huge search space, and it is very challenging to find the optimal solution. There are several heuristic algorithms for this problem, but they rely on simple scoring functions and there is no guarantee as to the size of the resulting subgraph, compared with the optimal solution. Our empirical study also indicates that the size of their resulting subgraphs may be large in practice. In this paper, we develop an effective and efficient progressive algorithm, namely PSA, to provide a good trade-off between the quality of the result and the search time. Novel lower and upper bound techniques for the minimum k-core search are designed. Our extensive experiments on 12 real-life graphs demonstrate the effectiveness and efficiency of the new techniques.
dc.language	en
dc.publisher	VLDB Endowment
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3368289.3368300
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.title	Efficient progressive minimum k-core search
dc.type	Journal Article
utslib.citation.volume	13
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
dc.date.updated	2021-04-19T00:21:54Z
pubs.issue	3
pubs.publication-status	Published
pubs.volume	13
utslib.citation.issue	3

Abstract:

As one of the most representative cohesive subgraph models, k-core model has recently received significant attention in the literature. In this paper, we investigate the problem of the minimum k-core search: given a graph G, an integer k and a set of query vertices Q = q, we aim to find the smallest k-core subgraph containing every query vertex q ∈ Q. It has been shown that this problem is NP-hard with a huge search space, and it is very challenging to find the optimal solution. There are several heuristic algorithms for this problem, but they rely on simple scoring functions and there is no guarantee as to the size of the resulting subgraph, compared with the optimal solution. Our empirical study also indicates that the size of their resulting subgraphs may be large in practice. In this paper, we develop an effective and efficient progressive algorithm, namely PSA, to provide a good trade-off between the quality of the result and the search time. Novel lower and upper bound techniques for the minimum k-core search are designed. Our extensive experiments on 12 real-life graphs demonstrate the effectiveness and efficiency of the new techniques.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/148193