Finding Critical Users in Social Communities: The Collapsed Core and Truss Problems

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

Finding Critical Users in Social Communities: The Collapsed Core and Truss Problems

Zhang, F Li, C

Zhang, Y

Qin, L

Zhang, W

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2020, 32 (1), pp. 78 - 91
Issue Date:: 2020-01-01

Closed Access

	Filename	Description	Size
	TKDE_2018.pdf	Published Version	1.13 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	Zhang, F	en_US
dc.contributor.author	Li, C https://orcid.org/0000-0002-6164-2643	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.contributor.author	Zhang, W	en_US
dc.date.issued	2020-01-01	en_US
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2020, 32 (1), pp. 78 - 91	en_US
dc.identifier.issn	1041-4347	en_US
dc.identifier.uri	http://hdl.handle.net/10453/129391
dc.description.abstract	© 1989-2012 IEEE. In social networks, the leave of critical users may significantly break network engagement, i.e., lead a large number of other users to drop out. A popular model to measure social network engagement is kk-core, the maximal subgraph in which every vertex has at least kk neighbors. To identify critical users, we propose the collapsed kk-core problem: given a graph GG, a positive integer kk and a budget bb, we aim to find bb vertices in GG such that the deletion of the bb vertices leads to the smallest kk-core. We prove the problem is NP-hard and inapproximate. An efficient algorithm is proposed, which significantly reduces the number of candidate vertices. We also study the user leave towards the model of kk-truss which further considers tie strength by conducting additional computation w.r.t. kk-core. We prove the corresponding collapsed kk-truss problem is also NP-hard and inapproximate. An efficient algorithm is proposed to solve the problem. The advantages and disadvantages of the two proposed models are experimentally compared. Comprehensive experiments on nine real-life social networks demonstrate the effectiveness and efficiency of our proposed methods.	en_US
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation	http://purl.org/au-research/grants/arc/DE140100999
dc.relation	http://purl.org/au-research/grants/arc/DE140100679
dc.relation	http://purl.org/au-research/grants/arc/DP160101513
dc.relation	http://purl.org/au-research/grants/arc/DP170103710
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering	en_US
dc.relation.isbasedon	10.1109/TKDE.2018.2880976	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Finding Critical Users in Social Communities: The Collapsed Core and Truss Problems	en_US
dc.type	Journal Article
utslib.citation.volume	1	en_US
utslib.citation.volume	32	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
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/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	closed_access
pubs.issue	1	en_US
pubs.publication-status	Published	en_US
pubs.volume	32	en_US

Abstract:

© 1989-2012 IEEE. In social networks, the leave of critical users may significantly break network engagement, i.e., lead a large number of other users to drop out. A popular model to measure social network engagement is kk-core, the maximal subgraph in which every vertex has at least kk neighbors. To identify critical users, we propose the collapsed kk-core problem: given a graph GG, a positive integer kk and a budget bb, we aim to find bb vertices in GG such that the deletion of the bb vertices leads to the smallest kk-core. We prove the problem is NP-hard and inapproximate. An efficient algorithm is proposed, which significantly reduces the number of candidate vertices. We also study the user leave towards the model of kk-truss which further considers tie strength by conducting additional computation w.r.t. kk-core. We prove the corresponding collapsed kk-truss problem is also NP-hard and inapproximate. An efficient algorithm is proposed to solve the problem. The advantages and disadvantages of the two proposed models are experimentally compared. Comprehensive experiments on nine real-life social networks demonstrate the effectiveness and efficiency of our proposed methods.

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

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