A Comparison of Approaches to Computing Betweenness Centrality for Large Graphs

2018
OriginalPaper
Chapter

Published in:

Author: John Matta
Published in: Complex Networks & Their Applications VI
Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Many algorithms require doing a large number of betweenness centrality calculations quickly, and accommodating this need is an active open research area. Two of the most important ways of addressing this problem are with approximated and distributed algorithms. It is difficult to know which approach will work best in practical situations, because results presented are often compared to similar algorithms, and universally recognized benchmarks do not exist. This paper evaluates one approximation approach and one distributed approach by applying each to the problem of node-based resilience measure clustering. This form of clustering is a good test for the algorithms, because it requires massive numbers of betweenness centrality calculations, as well as results that are accurate enough for the clustering to succeed. We find that with both the approximated and distributed approaches there is a trade-off between speed and accuracy, but each succeeds in reducing computation time by at least an order of magnitude.

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Business + Economics & Engineering + Technology"

Online-Abonnement

Springer Professional "Business + Economics & Engineering + Technology" gives you access to:

more than 102.000 books
more than 537 journals

from the following subject areas:

Automotive
Construction + Real Estate
Business IT + Informatics
Electrical Engineering + Electronics
Energy + Sustainability
Finance + Banking
Management + Leadership
Marketing + Sales
Mechanical Engineering + Materials
Insurance + Risk

Secure your knowledge advantage now!

inform now

Springer Professional "Engineering + Technology"

Online-Abonnement

Springer Professional "Engineering + Technology" gives you access to:

more than 67.000 books
more than 390 journals

from the following specialised fileds:

Automotive
Business IT + Informatics
Construction + Real Estate
Electrical Engineering + Electronics
Energy + Sustainability
Mechanical Engineering + Materials

Secure your knowledge advantage now!

inform now

Springer Professional "Business + Economics"

Online-Abonnement

Springer Professional "Business + Economics" gives you access to:

more than 67.000 books
more than 340 journals

from the following specialised fileds:

Construction + Real Estate
Business IT + Informatics
Finance + Banking
Management + Leadership
Marketing + Sales
Insurance + Risk

Secure your knowledge advantage now!

inform now

next chapter Cycle-Centrality in Economic and Biological Networks

Metadata
Footnotes
Literature

Title: A Comparison of Approaches to Computing Betweenness Centrality for Large Graphs
Author: John Matta
Publisher: Springer International Publishing
Book: Complex Networks & Their Applications VI
Print ISBN: 978-3-319-72149-1

Electronic ISBN: 978-3-319-72150-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-72150-7_1

This content is only visible if you are logged in and have the appropriate permissions.