Efficient probabilistic k-core computation on uncertain graphs

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

Efficient probabilistic k-core computation on uncertain graphs

Peng, Y Zhang, Y

Zhang, W

Lin, X Qin, L

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 1204 - 1207
Issue Date:: 2018-10-24

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (1.2 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Peng, Y	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Zhang, W https://orcid.org/0000-0001-6572-2600	en_US
dc.contributor.author	Lin, X	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.date.available	2020-10-24T18:07:39Z
dc.date.issued	2018-10-24	en_US
dc.identifier.citation	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 1204 - 1207	en_US
dc.identifier.isbn	9781538655207	en_US
dc.identifier.uri	http://hdl.handle.net/10453/131181
dc.description.abstract	© 2018 IEEE. As uncertainty is inherent in a wide spectrum of graph applications such as social network and brain network, it is highly demanded to re-visit classical graph problems in the context of uncertain graphs. Driven by real-Applications, in this paper, we study the problem of k-core computation on uncertain graphs and propose a new model, namely (k,θ )-core, which consists of nodes with probability at least θ to be kcore member in the uncertain graph. We show the computation of (k,θ )-core is NP-hard, and hence resort to sampling based methods. Effective and efficient pruning techniques are proposed to significantly reduce the candidate size. To further reduce the cost of k-core computation on multiple sampled graphs, we design a k-core membership check algorithm following a novel expansion-based search paradigm. Extensive experiments on reallife graphs demonstrate the effectiveness and efficiency of our proposed techniques.	en_US
dc.relation.ispartof	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018	en_US
dc.relation.isbasedon	10.1109/ICDE.2018.00110	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Efficient probabilistic k-core computation on uncertain graphs	en_US
dc.type	Conference Proceeding
utslib.for	0802 Computation Theory and Mathematics	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
utslib.copyright.status	open_access	*
pubs.publication-status	Published	en_US

Abstract:

© 2018 IEEE. As uncertainty is inherent in a wide spectrum of graph applications such as social network and brain network, it is highly demanded to re-visit classical graph problems in the context of uncertain graphs. Driven by real-Applications, in this paper, we study the problem of k-core computation on uncertain graphs and propose a new model, namely (k,θ )-core, which consists of nodes with probability at least θ to be kcore member in the uncertain graph. We show the computation of (k,θ )-core is NP-hard, and hence resort to sampling based methods. Effective and efficient pruning techniques are proposed to significantly reduce the candidate size. To further reduce the cost of k-core computation on multiple sampled graphs, we design a k-core membership check algorithm following a novel expansion-based search paradigm. Extensive experiments on reallife graphs demonstrate the effectiveness and efficiency of our proposed techniques.

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

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