A graph that includes multiple nodes and edges is received. Multiple instances of the graph are generated by randomly instantiating the edges according to either a binary independent cascade model or a randomized edge length independent cascade model. Where the binary independent cascade model is used, combined reachability sketches are generated for each node across all instances of the graph. Where the randomized edge length independent cascade model is used, combined all-distances sketches are generated for each node across all instances of the graph. Depending on which model is used, the combined reachability or all-distances sketches are used to estimate the influence of nodes in the graph or to estimate a subset of nodes from a graph of a specified size with a maximum influence using a greedy algorithm.