A sparsifier is generated from a union of multiple spanners of a graph. The edges of the sparsifier are weighted based on a measure of connectivity called robust connectivity. The robust connectivity of a node pair is the highest edge sampling probability at which a distance between the pair is likely to drop below a specified length. Each spanner is generated from a subgraph of the graph that is generated using a decreasing sampling probability. For the weight of each edge, a spanner is determined where an estimated distance between the nodes associated with the edge is greater than a threshold distance. The sampling probability of the subgraph used to generate the spanner is an estimate of the robust connectivity of the edge. The weight of the edge is set to the inverse of the estimated robust connectivity.