Efficient Community Search with Size Constraint

Liu, B; Zhang, F; Zhang, W; Lin, X; Zhang, Y

Efficient Community Search with Size Constraint

Liu, B Zhang, F Zhang, W Lin, X Zhang, Y

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2021 IEEE 37th International Conference on Data Engineering (ICDE), 2021, 2021-April, pp. 97-108
Issue Date:: 2021-06-22

Closed Access

	Filename	Description	Size
	Efficient_Community_Search_with_Size_Constraint.pdf	Published version	3.62 MB	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	Liu, B
dc.contributor.author	Zhang, F
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.date	2021-04-19
dc.date.accessioned	2022-03-30T03:38:45Z
dc.date.available	2022-03-30T03:38:45Z
dc.date.issued	2021-06-22
dc.identifier.citation	2021 IEEE 37th International Conference on Data Engineering (ICDE), 2021, 2021-April, pp. 97-108
dc.identifier.isbn	9781728191843
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/155706
dc.description.abstract	The studies of k-truss based community search demonstrated that it can find high-quality personalized com-munities with good properties such as high connectivity and bounded diameter. Motivated by natural restrictions from real applications, in this paper, we investigate the search of triangle-connected k-truss with size constraint (denoted by SCkT) in a graph G: given a size constraint s, an integer k, and query set Q, SCkT search aims to find a triangle-connected k-truss H containing the vertices in Q and with size (i.e., total number of vertices in H) not exceeding s. We prove that the SCkT search problem is NP-hard. To tame the hardness, we fully exploit the properties of triangle-connected k-truss subgraphs s.t. a practically-efficient exact solution for SCkT search is developed. A novel and effective lower bound is proposed to early terminate unpromising search branches and narrow down the search space. Two search strategies, expansion and shrinking, are investigated to tailor for efficient support of SCkT search. A hybrid search method is proposed combining the expansion and shrinking strategies, where a score function is used to guide the search order. Our extensive experiments on real-life and synthetic graphs demonstrate the effectiveness of the SCkT model and the efficiency of the proposed techniques.
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	2021 IEEE 37th International Conference on Data Engineering (ICDE)
dc.relation.ispartof	2021 IEEE 37th International Conference on Data Engineering
dc.relation.ispartofseries	IEEE International Conference on Data Engineering
dc.relation.isbasedon	10.1109/icde51399.2021.00016
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Efficient Community Search with Size Constraint
dc.type	Conference Proceeding
utslib.citation.volume	2021-April
utslib.location.activity	Chania, Greece
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
utslib.copyright.status	closed_access	*
dc.date.updated	2022-03-30T03:38:44Z
pubs.finish-date	2021-04-22
pubs.publication-status	Published
pubs.start-date	2021-04-19
pubs.volume	2021-April

Abstract:

The studies of k-truss based community search demonstrated that it can find high-quality personalized com-munities with good properties such as high connectivity and bounded diameter. Motivated by natural restrictions from real applications, in this paper, we investigate the search of triangle-connected k-truss with size constraint (denoted by SCkT) in a graph G: given a size constraint s, an integer k, and query set Q, SCkT search aims to find a triangle-connected k-truss H containing the vertices in Q and with size (i.e., total number of vertices in H) not exceeding s. We prove that the SCkT search problem is NP-hard. To tame the hardness, we fully exploit the properties of triangle-connected k-truss subgraphs s.t. a practically-efficient exact solution for SCkT search is developed. A novel and effective lower bound is proposed to early terminate unpromising search branches and narrow down the search space. Two search strategies, expansion and shrinking, are investigated to tailor for efficient support of SCkT search. A hybrid search method is proposed combining the expansion and shrinking strategies, where a score function is used to guide the search order. Our extensive experiments on real-life and synthetic graphs demonstrate the effectiveness of the SCkT model and the efficiency of the proposed techniques.

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

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