Finding the best k in core decomposition: A time and space optimal solution

Chu, D; Zhang, F; Lin, X; Zhang, W; Zhang, Y; Xia, Y; Zhang, C

Finding the best k in core decomposition: A time and space optimal solution

Chu, D Zhang, F Lin, X Zhang, W Zhang, Y

Xia, Y Zhang, C

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2020, 2020-April, pp. 685-696
Issue Date:: 2020-04-01

Closed Access

	Filename	Description	Size
	ICDE_2020_best_k.pdf	Published version	467.9 kB		View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Chu, D
dc.contributor.author	Zhang, F
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, W
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Xia, Y
dc.contributor.author	Zhang, C
dc.date	2020-04-20
dc.date.accessioned	2020-11-03T00:47:37Z
dc.date.available	2020-11-03T00:47:37Z
dc.date.issued	2020-04-01
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2020, 2020-April, pp. 685-696
dc.identifier.isbn	9781728129037
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/143700
dc.description.abstract	© 2020 IEEE. The mode of k-core and its hierarchical decomposition have been applied in many areas, such as sociology, the world wide web, and biology. Algorithms on related studies often need an input value of parameter k, while there is no existing solution other than manual selection. In this paper, given a graph and a scoring metric, we aim to efficiently find the best value of k such that the score of the k-core (or k-core set) is the highest. The problem is challenging because there are various community scoring metrics and the computation is costly on large datasets. With the well-designed vertex ordering techniques, we propose time and space optimal algorithms to compute the best k, which are applicable to most community metrics. The proposed algorithms can compute the score of every k-core (set) and can benefit the solutions to other k-core related problems. Extensive experiments are conducted on 10 real-world networks with size up to billion-scale, which validates both the efficiency of our algorithms and the effectiveness of the resulting k-cores.
dc.language	en
dc.publisher	IEEE
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	Proceedings - International Conference on Data Engineering
dc.relation.ispartof	2020 IEEE 36th International Conference on Data Engineering (ICDE)
dc.relation.isbasedon	10.1109/ICDE48307.2020.00065
dc.rights	© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.	en_US
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Finding the best k in core decomposition: A time and space optimal solution
dc.type	Conference Proceeding
utslib.citation.volume	2020-April
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
pubs.organisational-group	/University of Technology Sydney
utslib.copyright.status	closed_access	*
dc.date.updated	2020-11-03T00:47:31Z
pubs.finish-date	2020-04-24
pubs.publication-status	Published
pubs.start-date	2020-04-20
pubs.volume	2020-April

Abstract:

© 2020 IEEE. The mode of k-core and its hierarchical decomposition have been applied in many areas, such as sociology, the world wide web, and biology. Algorithms on related studies often need an input value of parameter k, while there is no existing solution other than manual selection. In this paper, given a graph and a scoring metric, we aim to efficiently find the best value of k such that the score of the k-core (or k-core set) is the highest. The problem is challenging because there are various community scoring metrics and the computation is costly on large datasets. With the well-designed vertex ordering techniques, we propose time and space optimal algorithms to compute the best k, which are applicable to most community metrics. The proposed algorithms can compute the score of every k-core (set) and can benefit the solutions to other k-core related problems. Extensive experiments are conducted on 10 real-world networks with size up to billion-scale, which validates both the efficiency of our algorithms and the effectiveness of the resulting k-cores.

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

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