Comparative Evaluations of GPS-BC and LLMs on Betweenness Centrality Variations

Abstract

When analyzing networks, Betweenness Centrality is a method of measurement that can be used to find the frequency at which a node is accessed when calculating the shortest path between various nodes. The more often a node is accessed, the greater the node’s Betweenness Centrality score becomes. This metric allows for numerous practical applications, from gene identification for diseases to analyzing the movement of data through informational infrastructures. With modern day computing power, we are able to utilize LLMs (Large Language Models) to calculate Betweenness Centrality on large-scale networks. However, the performance of LLMs may not be quick nor accurate when presenting a response for Betweenness Centrality graph problems. Therefore, we propose a GPS-BC module that has the capability to formulate accurate solutions for Betweenness Centrality problems using tailored algorithms. The problems contain several combinations of the constraints on (A) node color, (B) edge/path weights and (C) node degree. For all the constrained problems, GPT-5.2 was observed to have an average accuracy of 62% when reporting Betweenness Centrality scores. The accuracy decreases when increasing the complexity of the constraints imposed on a problem. Additionally, GPSBC algorithms were found to be, on average, 3.65× faster than the observed processing time for GPT-5.2. Through this approach of using validated algorithms in our GPS-BC module, we are able to process Betweenness Centrality calculations with efficiency and ensured accuracy.