Exacting eccentricity for small-world networks
- 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.
© 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: