Accelerating Node Influence Computation via Integration of Strongly Connected Component Assignment and Reachability Computation

Abstract

We study the problem of efficiently computing the influence of all nodes under the SIR model. In our previous work, we proposed the burn‐Out extracted LC (BELC) technique and combined it with existing techniques to develop the BSRM method. In this paper, we propose two new methods, BS and BI. BS removes the REP and MCP pruning techniques from BSRM. BI extends BS by integrating SCC assignment and reachability computation. Experiments on four large‐scale networks show that the proposed methods are faster while producing the same influence values. We also analyze how network structure affects their performance.