Exacting eccentricity for small-world networks

Li, W; Qiao, M; Qin, L; Zhang, Y; Chang, L; Lin, X

Exacting eccentricity for small-world networks

Li, W

Qiao, M Qin, L

Zhang, Y

Chang, L Lin, X

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 785 - 796
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.16 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Li, W https://orcid.org/0000-0003-4941-8814	en_US
dc.contributor.author	Qiao, M	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Chang, L	en_US
dc.contributor.author	Lin, X	en_US
dc.date.available	2020-10-25T18:09:35Z
dc.date.issued	2018-10-24	en_US
dc.identifier.citation	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 785 - 796	en_US
dc.identifier.isbn	9781538655207	en_US
dc.identifier.uri	http://hdl.handle.net/10453/131177
dc.description.abstract	© 2018 IEEE. This paper studies the efficiency issue on computing the exact eccentricity-distribution of a small-world network. Eccentricity-distribution reflects the importance of each node in a graph, which is beneficial for graph analysis. Moreover, it is key to computing two fundamental graph characters: diameter and radius. Existing eccentricity computation algorithms, however, are either inefficient in handling large-scale networks emerging nowadays in practice or approximate algorithms that are inappropriate to small-world networks. We propose an efficient approach for exact eccentricity computation. Our approach is based on a plethora of insights on the bottleneck of the existing algorithms-one-node eccentricity computation and the upper/lower bounds update. Extensive experiments demonstrate that our approach outperforms the state-of-The-Art up to three orders of magnitude on real large small-world networks.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP160101513
dc.relation.ispartof	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018	en_US
dc.relation.isbasedon	10.1109/ICDE.2018.00076	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Exacting eccentricity for small-world networks	en_US
dc.type	Conference Proceeding
utslib.for	0801 Artificial Intelligence and Image Processing	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
utslib.copyright.status	open_access	*
pubs.publication-status	Published	en_US

Abstract:

© 2018 IEEE. This paper studies the efficiency issue on computing the exact eccentricity-distribution of a small-world network. Eccentricity-distribution reflects the importance of each node in a graph, which is beneficial for graph analysis. Moreover, it is key to computing two fundamental graph characters: diameter and radius. Existing eccentricity computation algorithms, however, are either inefficient in handling large-scale networks emerging nowadays in practice or approximate algorithms that are inappropriate to small-world networks. We propose an efficient approach for exact eccentricity computation. Our approach is based on a plethora of insights on the bottleneck of the existing algorithms-one-node eccentricity computation and the upper/lower bounds update. Extensive experiments demonstrate that our approach outperforms the state-of-The-Art up to three orders of magnitude on real large small-world networks.

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

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