Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient Approximate Computation of Betweenness Centrality
| Content Provider | Semantic Scholar |
|---|---|
| Author | Gkorou, Dimitra Pouwelse, Johan A. Epema, Dick H. J. |
| Copyright Year | 2010 |
| Abstract | Betweenness Centrality (BC) is a powerful metric for identifying central nodes in complex network analysis, but its computation in large and dynamic systems is costly. Most of the previous approximations for computing BC are either restricted to only one type of networks, or are too computationally inefficient to be applied to large or dynamically changing networks. We explore two approximative approaches for computing BC, and we evaluate them experimentally using both synthetic graphs and graphs derived from real data. For dynamic networks, our approach relies on the observation that the nodes with high BC in real-world networks remain almost invariant over time. For large networks, we propose an approximation of BC, k-BC, which consists in reducing the number of shortest paths taken into account. We evaluate our methods using synthetic scale-free and random graphs, and a graph created by the Bartercast reputation mechanism used in the Tribler P2P network, and we show that the proposed methods approximate BC with sufficient accuracy and low cost. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.researchgate.net/profile/Dimitra_Gkorou/publication/273765352_Efficient_Approximate_Computation_of_Betweenness_Centrality/links/550b5ed90cf265693cef7675.pdf |
| Alternate Webpage(s) | https://www.researchgate.net/profile/Dimitra_Gkorou/publication/273765352_Efficient_Approximate_Computation_of_Betweenness_Centrality/links/550b5ed90cf265693cef7675.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
