| Field |
Value |
Language |
|
dc.contributor.author |
Zhang, F |
|
|
dc.contributor.author |
Zhang, W |
|
|
dc.contributor.author |
Zhang, Y
https://orcid.org/0000-0002-2674-1638
|
|
|
dc.contributor.author |
Qin, L
https://orcid.org/0000-0001-6068-5062
|
|
|
dc.contributor.author |
Lin, X |
|
|
dc.date.accessioned |
2022-01-31T04:51:59Z |
|
|
dc.date.available |
2022-01-31T04:51:59Z |
|
|
dc.date.issued |
2017-02 |
|
|
dc.identifier.citation |
Proceedings of the VLDB Endowment, 2017, 10, (6), pp. 649-660 |
|
|
dc.identifier.issn |
2150-8097 |
|
|
dc.identifier.uri |
http://hdl.handle.net/10453/153954
|
|
|
dc.description.abstract |
<jats:p>
In this paper, we study the problem of the anchored
<jats:italic>k</jats:italic>
-core. Given a graph
<jats:italic>G</jats:italic>
, an integer
<jats:italic>k</jats:italic>
and a budget
<jats:italic>b</jats:italic>
, we aim to identify
<jats:italic>b</jats:italic>
vertices in
<jats:italic>G</jats:italic>
so that we can determine the largest induced subgraph
<jats:italic>J</jats:italic>
in which every vertex, except the
<jats:italic>b</jats:italic>
vertices, has at least
<jats:italic>k</jats:italic>
neighbors in
<jats:italic>J</jats:italic>
. This problem was introduced by Bhawalkar and Kleinberg
<jats:italic>e</jats:italic>
t al. in the context of user engagement in social networks, where a user may leave a community if he/she has less than
<jats:italic>k</jats:italic>
friends engaged. The problem has been shown to be NP-hard and inapproximable. A polynomial-time algorithm for graphs with bounded tree-width has been proposed. However, this assumption usually does not hold in real-life graphs, and their techniques cannot be extended to handle general graphs.
</jats:p>
<jats:p>
Motivated by this, we propose an efficient algorithm, namely <u>o</u>nion-<u>l</u>ayer based <u>a</u>nchored <u>k</u>-core (OLAK), for the anchored
<jats:italic>k</jats:italic>
-core problem on large scale graphs. To facilitate computation of the anchored
<jats:italic>k</jats:italic>
-core, we design an
<jats:italic>onion layer</jats:italic>
structure, which is generated by a simple onion-peeling-like 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
<jats:italic>onion layers</jats:italic>
, which significantly reduces the search space. Based on the well-organized 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.
</jats:p> |
|
|
dc.language |
en |
|
|
dc.publisher |
VLDB Endowment |
|
|
dc.relation.ispartof |
Proceedings of the VLDB Endowment |
|
|
dc.relation.isbasedon |
10.14778/3055330.3055332 |
|
|
dc.rights |
This work is licensed under the Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License. To view a copy
of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For
any use beyond those covered by this license, obtain permission by emailing
info@vldb.org.
Proceedings of the VLDB Endowment, Vol. 10, No. 6
Copyright 2017 VLDB Endowment 2150-8097/17/02. |
|
|
dc.rights |
info:eu-repo/semantics/openAccess |
|
|
dc.subject |
0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies |
|
|
dc.title |
OLAK |
|
|
dc.type |
Journal Article |
|
|
utslib.citation.volume |
10 |
|
|
utslib.for |
0802 Computation Theory and Mathematics |
|
|
utslib.for |
0806 Information Systems |
|
|
utslib.for |
0807 Library and Information Studies |
|
|
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 |
|
|
pubs.organisational-group |
/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science |
|
|
utslib.copyright.status |
open_access |
* |
|
dc.date.updated |
2022-01-31T04:51:58Z |
|
|
pubs.issue |
6 |
|
|
pubs.publication-status |
Published |
|
|
pubs.volume |
10 |
|
|
utslib.citation.issue |
6 |
|
