Anchored coreness: efficient reinforcement of social networks

Linghu, Q; Zhang, F; Lin, X; Zhang, W; Zhang, Y

Anchored coreness: efficient reinforcement of social networks

Linghu, Q Zhang, F Lin, X Zhang, W Zhang, Y

Permalink

Publisher:: SPRINGER
Publication Type:: Conference Proceeding
Citation:: VLDB Journal, 2022, 31, (2), pp. 227-252
Issue Date:: 2022-03-01

Closed Access

	Filename	Description	Size
	Linghu2022_Article_AnchoredCorenessEfficientReinf.pdf	Published version	2.2 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	Linghu, Q
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.date.accessioned	2022-03-30T03:45:43Z
dc.date.available	2022-03-30T03:45:43Z
dc.date.issued	2022-03-01
dc.identifier.citation	VLDB Journal, 2022, 31, (2), pp. 227-252
dc.identifier.issn	1066-8888
dc.identifier.issn	0949-877X
dc.identifier.uri	http://hdl.handle.net/10453/155710
dc.description.abstract	The stability of a social network has been widely studied as an important indicator for both the network holders and the participants. Existing works on reinforcing networks focus on a local view, e.g., the anchored k-core problem aims to enlarge the size of the k-core with a fixed input k. Nevertheless, it is more promising to reinforce a social network in a global manner: considering the engagement of every user (vertex) in the network. Since the coreness of a user has been validated as the “best practice” for capturing user engagement, we propose and study the anchored coreness problem in this paper: anchoring a small number of vertices to maximize the coreness gain (the total increment of coreness) of all the vertices in the network. We prove the problem is NP-hard and show it is more challenging than the existing local-view problems. An efficient greedy algorithm is proposed with novel techniques on pruning search space and reusing the intermediate results. The algorithm is also extended to distributed environment with a novel graph partition strategy to ensure the computing independency of each machine. Extensive experiments on real-life data demonstrate that our model is effective for reinforcing social networks and our algorithms are efficient.
dc.language	en
dc.publisher	SPRINGER
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	VLDB Journal
dc.relation.isbasedon	10.1007/s00778-021-00673-6
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0804 Data Format, 0805 Distributed Computing, 0806 Information Systems
dc.subject.classification	Information Systems
dc.title	Anchored coreness: efficient reinforcement of social networks
dc.type	Conference Proceeding
utslib.citation.volume	31
utslib.for	0804 Data Format
utslib.for	0805 Distributed Computing
utslib.for	0806 Information Systems
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:45:42Z
pubs.issue	2
pubs.publication-status	Published
pubs.volume	31
utslib.citation.issue	2

Abstract:

The stability of a social network has been widely studied as an important indicator for both the network holders and the participants. Existing works on reinforcing networks focus on a local view, e.g., the anchored k-core problem aims to enlarge the size of the k-core with a fixed input k. Nevertheless, it is more promising to reinforce a social network in a global manner: considering the engagement of every user (vertex) in the network. Since the coreness of a user has been validated as the “best practice” for capturing user engagement, we propose and study the anchored coreness problem in this paper: anchoring a small number of vertices to maximize the coreness gain (the total increment of coreness) of all the vertices in the network. We prove the problem is NP-hard and show it is more challenging than the existing local-view problems. An efficient greedy algorithm is proposed with novel techniques on pruning search space and reusing the intermediate results. The algorithm is also extended to distributed environment with a novel graph partition strategy to ensure the computing independency of each machine. Extensive experiments on real-life data demonstrate that our model is effective for reinforcing social networks and our algorithms are efficient.

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

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