Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ICDE.2018.00076 | 2018 IEEE 34th International Conference on Data Engineering (ICDE) |
Keywords | Field | DocType |
Eccentricity,Small World Network | Graph,Bottleneck,Data mining,Computer science,Eccentricity (behavior),Small-world network,Theoretical computer science,Power graph analysis,Computation | Conference |
ISSN | ISBN | Citations |
1063-6382 | 978-1-5386-5521-4 | 0 |
PageRank | References | Authors |
0.34 | 15 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wentao Li | 1 | 153 | 7.66 |
| Miao Qiao | 2 | 90 | 5.04 |
| Lu Qin | 3 | 1430 | 95.44 |
| Ying Zhang | 4 | 1288 | 90.39 |
| Lijun Chang | 5 | 670 | 44.24 |
| Xuemin Lin | 6 | 5585 | 307.32 |