2022/03/01 by Diego Santoro, Ilie Sarpe · 18 citations
Computer Science · Mathematics · Physics and Astronomy · Psychology · #Algorithm #Betweenness centrality #Centrality #Complex Network Analysis Techniques #Complex network #Computation #Computer science #Mathematics #Mental Health Research Topics #Network controllability #Network science #Node (physics) #Opinion Dynamics and Social Influence #Physics #Statistics #Theoretical computer science #cs.DS #cs.LG #cs.SI
paper · pdf · doi:10.1145/3485447.3512204
published in Proceedings of the ACM Web Conference 2022, 1579-1588 · Accepted at TheWebConf 2022 (WWW '22)
arxiv created 2022/03/01 · arxiv updated 2022/03/02 · openalex created_date 2022/04/03 · openalex publication_date 2022/04/25 · openalex updated_date 2026/08/05
In network analysis, the betweenness centrality of a node informally captures the fraction of shortest paths visiting that node. The computation of the betweenness centrality measure is a fundamental task in the analysis of modern networks, enabling the identification of the most central nodes in such networks. Additionally to being massive, modern networks also contain information about the time at which their events occur. Such networks are often called temporal networks. The temporal information makes the study of the betweenness centrality in temporal networks (i.e., temporal betweenness centrality) much more challenging than in static networks (i.e., networks without temporal information). Moreover, the exact computation of the temporal betweenness centrality is often impractical on even moderately-sized networks, given its extremely high computational cost. A natural approach to reduce such computational cost is to obtain high-quality estimates of the exact values of the temporal betweenness centrality. In this work we present ONBRA, the first sampling-based approximation algorithm for estimating the temporal betweenness centrality values of the nodes in a temporal network, providing rigorous probabilistic guarantees on the quality of its output. ONBRA is able to compute the estimates of the temporal betweenness centrality values under two different optimality criteria for the shortest paths of the temporal network. In addition, ONBRA outputs high-quality estimates with sharp theoretical guarantees leveraging on the empirical Bernstein bound, an advanced concentration inequality. Finally, our experimental evaluation shows that ONBRA significantly reduces the computational resources required by the exact computation of the temporal betweenness centrality on several real world networks, while reporting high-quality estimates with rigorous guarantees.