Formally, the Betweenness Centrality of a vertex is defined as: Intuitively, this ratio determines how well a vertex connects pairs of vertices in the network. Example Betweenness Centrality scores for a small graphīetweenness Centrality determines the importance of vertices in a network by measuring the ratio of shortest paths passing through a particular vertex to the total number of shortest paths between all pairs of vertices. This post describes how we used CUDA and NVIDIA GPUs to accelerate the BC computation, and how choosing efficient parallelization strategies results in an average speedup of 2.7x, and more than 10x speedup for road networks and meshes versus a naïve edge-parallel strategy. Unfortunately, the fastest known algorithm for computing betweenness centrality has time complexity for graphs with vertices and edges, making the analysis of large networks challenging. It has many practical use cases, including finding the best locations for stores within cities, power grid contingency analysis, and community detection. Betweenness Centrality (BC) is a popular analytic that determines vertex influence in a graph. Real-world applications of graph algorithms involve tremendously large networks that cannot be inspected manually. Graph analysis is a fundamental tool for domains as diverse as social networks, computational biology, and machine learning.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |