OLAK: An efficient algorithm to prevent unraveling in social networks

Zhang, F; Zhang, W; Zhang, Y; Qin, L; Lin, X

OLAK: An efficient algorithm to prevent unraveling in social networks

Zhang, F

Zhang, W Zhang, Y

Qin, L

Lin, X

Permalink

Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2016, 10 (6), pp. 649 - 660
Issue Date:: 2016-01-01

Closed Access

	Filename	Description	Size
	OLAK An Efficient Algorithm to Prevent Unraveling in Social Networks.pdf	Published Version	493.23 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, F https://orcid.org/0000-0003-0548-0130	en_US
dc.contributor.author	Zhang, W	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	Lin, X	en_US
dc.date.issued	2016-01-01	en_US
dc.identifier.citation	Proceedings of the VLDB Endowment, 2016, 10 (6), pp. 649 - 660	en_US
dc.identifier.uri	http://hdl.handle.net/10453/115304
dc.description.abstract	© 2017. VLDB Endowment. In this paper, we study the problem of the anchored k-core. Given a graph G, an integer k and a budget b, we aim to identify b vertices in G so that we can determine the largest induced subgraph J in which every vertex, except the b vertices, has at least k neighbors in J. This problem was introduced by Bhawalkar and Kleinberg et al. In the context of user engagement in social networks, where a user may leave a community if he/she has less than k friends engaged. The problem has been shown to be NP-hard and inapproximable. A polynomial-time algorithm for graphs with bounded treewidth has been proposed. However, this assumption usually does not hold in real-life graphs, and their techniques cannot be extended to handle general graphs. Motivated by this, we propose an efficient algorithm, namely onion-layer based anchored k-core (OLAK), for the anchored k-core problem on large scale graphs. To facilitate computation of the anchored k-core, we design an onion layer structure, which is generated by a simple onion-peelinglike algorithm against a small set of vertices in the graph. We show that computation of the best anchor can simply be conducted upon the vertices on the onion layers, which significantly reduces the search space. Based on the wellorganized layer structure, we develop efficient candidates exploration, early termination and pruning techniques to further speed up computation. Comprehensive experiments on 10 real-life graphs demonstrate the effectiveness and efficiency of our proposed methods.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DE140100679
dc.relation.ispartof	Proceedings of the VLDB Endowment	en_US
dc.title	OLAK: An efficient algorithm to prevent unraveling in social networks	en_US
dc.type	Journal Article
utslib.citation.volume	6	en_US
utslib.citation.volume	10	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	0807 Library and Information Studies	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/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Life Sciences
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	6	en_US
pubs.publication-status	Published	en_US
pubs.volume	10	en_US

Abstract:

© 2017. VLDB Endowment. In this paper, we study the problem of the anchored k-core. Given a graph G, an integer k and a budget b, we aim to identify b vertices in G so that we can determine the largest induced subgraph J in which every vertex, except the b vertices, has at least k neighbors in J. This problem was introduced by Bhawalkar and Kleinberg et al. In the context of user engagement in social networks, where a user may leave a community if he/she has less than k friends engaged. The problem has been shown to be NP-hard and inapproximable. A polynomial-time algorithm for graphs with bounded treewidth has been proposed. However, this assumption usually does not hold in real-life graphs, and their techniques cannot be extended to handle general graphs. Motivated by this, we propose an efficient algorithm, namely onion-layer based anchored k-core (OLAK), for the anchored k-core problem on large scale graphs. To facilitate computation of the anchored k-core, we design an onion layer structure, which is generated by a simple onion-peelinglike algorithm against a small set of vertices in the graph. We show that computation of the best anchor can simply be conducted upon the vertices on the onion layers, which significantly reduces the search space. Based on the wellorganized layer structure, we develop efficient candidates exploration, early termination and pruning techniques to further speed up computation. Comprehensive experiments on 10 real-life graphs 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/115304