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:
Filename Description Size
[2018 ICDE] Exacting Eccentricity for Small-World Networks.pdfAccepted Manuscript version1.16 MB
Adobe PDF
Full metadata record
© 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: