{"ID":2871475,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11454","arxiv_id":"2509.11454","title":"Fast Percolation Centrality Approximation with Importance Sampling","abstract":"In this work we present PercIS, an algorithm based on Importance Sampling to approximate the percolation centrality of all the nodes of a graph. Percolation centrality is a generalization of betweenness centrality to attributed graphs, and is a useful measure to quantify the importance of the vertices in a contagious process or to diffuse information. However, it is impractical to compute it exactly on modern-sized networks. First, we highlight key limitations of state-of-the-art sampling-based approximation methods for the percolation centrality, showing that in most cases they cannot achieve accurate solutions efficiently. Then, we propose and analyze a novel sampling algorithm based on Importance Sampling, proving tight sample size bounds to achieve high-quality approximations. Our extensive experimental evaluation shows that PercIS computes high-quality estimates and scales to large real-world networks, while significantly outperforming, in terms of sample sizes, accuracy and running times, the state-of-the-art.","short_abstract":"In this work we present PercIS, an algorithm based on Importance Sampling to approximate the percolation centrality of all the nodes of a graph. Percolation centrality is a generalization of betweenness centrality to attributed graphs, and is a useful measure to quantify the importance of the vertices in a contagious p...","url_abs":"https://arxiv.org/abs/2509.11454","url_pdf":"https://arxiv.org/pdf/2509.11454v1","authors":"[\"Antonio Cruciani\",\"Leonardo Pellegrina\"]","published":"2025-09-14T22:05:26Z","proceeding":"cs.SI","tasks":"[\"cs.SI\",\"cs.DS\"]","methods":"[]","has_code":false}