To avoid running heavy MC simulations and reserve the theoretical guarantee, the sketch-based approach [1]} pre-computes a number of Reverse Reachable (RR) sketches based on a specific diffusion model and then evaluates the influence spread of given users set \(S\)  by exploiting the portion of RR-sketches which \(S\)  can reach. Here, the RR-sketch is constructed by randomly selecting a node \(u\in V\) , and conducting a reverse MC sampling starting from \(u\) . By performing the above operation iteratively \(\theta \)  times,
the RR sketches can be obtained.
Compared with the simulation-based approach, the sketch-based approach has a lower time complexity under a theoretical guarantee.
