Exacting eccentricity for small-world networks
- Publication Type:
- Conference Proceeding
- Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 785 - 796
- Issue Date:
|[2018 ICDE] Exacting Eccentricity for Small-World Networks.pdf||Accepted Manuscript version||1.16 MB|
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is currently unavailable due to the publisher's embargo.
The embargo period expires on 25 Oct 2020
© 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: