Exploring finer granularity within the cores: Efficient (k, p)-Core computation

Zhang, C; Zhang, F; Zhang, W; Liu, B; Zhang, Y; Qin, L; Lin, X

Exploring finer granularity within the cores: Efficient (k, p)-Core computation

Zhang, C Zhang, F Zhang, W Liu, B Zhang, Y

Qin, L Lin, X

Permalink

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

Closed Access

	Filename	Description	Size
	ICDE_chen.pdf	Accepted version	731.2 kB	Adobe PDF	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	Zhang, C
dc.contributor.author	Zhang, F
dc.contributor.author	Zhang, W
dc.contributor.author	Liu, B
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L
dc.contributor.author	Lin, X
dc.date	2020-04-20
dc.date.accessioned	2020-11-03T01:34:01Z
dc.date.available	2020-11-03T01:34:01Z
dc.date.issued	2020-04-01
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2020, 2020-April, pp. 181-192
dc.identifier.isbn	9781728129037
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/143717
dc.description.abstract	© 2020 IEEE. In this paper, we propose and study a novel cohesive subgraph model, named (k, p)-core, which is a maximal subgraph where each vertex has at least k neighbours and at least p fraction of its neighbours in the subgraph. The model is motivated by the finding that each user in a community should have at least a certain fraction p of neighbors inside the community to ensure user engagement, especially for users with large degrees. Meanwhile, the uniform degree constraint k, as applied in the k-core model, guarantees a minimum level of user engagement in a community, and is especially effective for users with small degrees. We propose an O(m) algorithm to compute a (k, p)-core with given k and p, and an O(dm) algorithm to decompose a graph by (k, p)-core, where m is the number of edges in the graph G and d is the degeneracy of G. A space efficient index is designed for time-optimal (k, p)-core query processing. Novel techniques are proposed for the maintenance of (k, p)-core index against graph dynamic. Extensive experiments on 8 reallife datasets demonstrate that our (k, p)-core model is effective and the algorithms are efficient.
dc.language	en
dc.publisher	IEEE
dc.relation	http://purl.org/au-research/grants/arc/DP160101513
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.00023
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	Exploring finer granularity within the cores: Efficient (k, p)-Core computation
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-03T01:33:53Z
pubs.finish-date	2020-04-24
pubs.publication-status	Published
pubs.start-date	2020-04-20
pubs.volume	2020-April

Abstract:

© 2020 IEEE. In this paper, we propose and study a novel cohesive subgraph model, named (k, p)-core, which is a maximal subgraph where each vertex has at least k neighbours and at least p fraction of its neighbours in the subgraph. The model is motivated by the finding that each user in a community should have at least a certain fraction p of neighbors inside the community to ensure user engagement, especially for users with large degrees. Meanwhile, the uniform degree constraint k, as applied in the k-core model, guarantees a minimum level of user engagement in a community, and is especially effective for users with small degrees. We propose an O(m) algorithm to compute a (k, p)-core with given k and p, and an O(dm) algorithm to decompose a graph by (k, p)-core, where m is the number of edges in the graph G and d is the degeneracy of G. A space efficient index is designed for time-optimal (k, p)-core query processing. Novel techniques are proposed for the maintenance of (k, p)-core index against graph dynamic. Extensive experiments on 8 reallife datasets demonstrate that our (k, p)-core model is effective and the algorithms are efficient.

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

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