Approximating Temporal Betweenness Centrality with Predictions

Recently, the Algorithms with Predictions framework has been introduced as a way to push algorithmic analysis beyond the worst-case scenario. The idea is to augment classical and modern algorithms with predictors, whether Machine Learning predictors or simple and practical predictors, to guide them towards a better performance. In this thesis, we investigate the application of this framework to the problem of approximating the Temporal Betweenness Centrality, a key measure for addressing the importance of the nodes in temporal networks. We design and analyze a perfect predictor that guides the sampling process of an approximation algorithm for the problem, providing strong theoretical guarantees on unbiasedness and error bounds. We formally prove that this predictor-based approach improves the state-of-the-art performances with respect to the required number of samples for achieving a high quality approximation. Beyond the theoretical contributions, we also explore more practical distance-based predictors and evaluate their effectiveness. Finally, we also present extensive empirical results obtained from large benchmark temporal networks datasets, validating our theoretical findings and demonstrating the potential of prediction-augmented algorithms for the analysis of temporal networks.

Recentemente il framework Algorithms with Predictions è stato introdotto con l'obiettivo di andare oltre l’analisi algoritmica al caso pessimo. L’idea è quella di arricchire gli algoritmi classici e moderni con oracoli, che possono essere predittori di Machine Learning oppure predittori semplici e pratici, al fine di guidarli verso prestazioni migliori. In questa tesi, studiamo l’applicazione di questo framework al problema dell’approssimazione della Temporal Betweenness Centrality, una misura fondamentale per valutare l’importanza dei nodi nelle reti temporali. Nella tesi si progetta e analizza un predittore perfetto che guida il processo di campionamento di un algoritmo di approssimazione per il problema, fornendo solide garanzie teoriche in termini di unbiasedness e limiti sull’errore. Inoltre, si dimostra formalmente che questo approccio basato su un predittore migliora lo stato dell’arte rispetto al numero di campioni richiesti per ottenere un’approssimazione di alta qualità. Oltre ai contributi teorici, si esplorano anche predittori più pratici basati sulle distanze e ne valutiamo l’efficacia. Infine, vengono presentati ampi risultati empirici ottenuti da grandi dataset di reti temporali di riferimento, che convalidano le nostre analisi teoriche e dimostrano il potenziale degli algoritmi arricchiti da predizioni per l’analisi delle reti temporali.