Betweenness centrality estimation with predictions

Betweenness centrality (BC) is a fundamental measure in network analysis, defining the importance of nodes based on how frequently they are present in the shortest paths of the network. Exact BC computation is prohibitively expensive on large graphs, which motivates the development of sampling-based approximation algorithms. Modern BC estimation algorithms rely on uniform sampling of node pairs, which is reliable and analytically convenient. This thesis investigates non-uniform sampling strategies for BC estimation, with the goal of balancing the informativeness of the samples against the runtime required to process them. We propose a framework where a predictor assigns probabilities to node pairs based on their shortest path length, which directly affects both the number of internal nodes in a sample and the time needed to compute the associated shortest paths. Within this framework, we study three reference predictors: the uniform-informative predictor, which excludes void pairs and samples the informative ones uniformly; the informative predictor, which favors distant pairs; and the inverse predictor, which favors closer pairs. Our theoretical analysis and experimental evaluation show that sampling distant pairs provides limited accuracy gains but yields a significant slowdown. In contrast, when considering large networks, sampling closer pairs through the inverse predictor achieves estimates of comparable quality to uniform sampling within a fraction of the runtime. At the same time, it is crucial to avoid overly unbalanced distributions that may lead to poor estimates and, consequently, large supremum deviations. These results highlight the potential of prediction-guided sampling, and suggest future directions for practical heuristics that approximate the inverse predictor without relying on exact distances.

La betweenness centrality (BC) è una misura fondamentale nell’analisi delle reti, che definisce l’importanza dei nodi in base alla frequenza con cui compaiono nei cammini minimi della rete. Il calcolo esatto della BC è estremamente costoso per grafi di grandi dimensioni, il che motiva lo sviluppo di algoritmi di approssimazione basati sul campionamento. Gli algoritmi moderni per stimare la BC si basano sul campionamento uniforme delle coppie di nodi, una strategia affidabile e conveniente dal punto di vista analitico. Questa tesi esplora strategie di campionamento non uniforme per la stima della BC, con l’obiettivo di bilanciare l’informatività dei campioni con il tempo di calcolo necessario per processarli. Proponiamo un framework in cui un predittore assegna probabilità alle coppie di nodi in base alla loro distanza minima, che influisce sia sul numero di nodi interni presenti nei cammini minimi, sia sul tempo richiesto per calcolare i corrispondenti cammini minimi. In questo contesto analizziamo tre predittori di riferimento: il predittore "uniform-informative", che esclude le coppie non informative e campiona uniformemente le restanti; il predittore "informative", che privilegia le coppie distanti; e il predittore "inverse", che privilegia le coppie più vicine. La nostra analisi teorica e sperimentale mostra che campionare coppie distanti può portare a benefici limitati in termini di accuratezza, ma al prezzo di un notevole rallentamento. Al contrario, nei grafi di grandi dimensioni, campionare coppie più vicine tramite il predittore "inverse" permette di ottenere stime di qualità comparabile a quelle del campionamento uniforme, ma in una frazione del tempo. Allo stesso tempo, è fondamentale evitare distribuzioni troppo sbilanciate: se alle coppie distanti viene assegnata una probabilità troppo bassa, le stime dei nodi più centrali possono risultare molto imprecise, con conseguenti grandi errori assoluti. Questi risultati evidenziano il potenziale del campionamento guidato da predittori e suggeriscono futuri sviluppi basati su euristiche pratiche per approssimare il predittore "inverse" senza dover ricorrere al calcolo delle distanze esatte.