Suppose that we have a sample of edges, sampled uniformly at random from the edge set of a graph . Also, let . Now the graph changes, in particular, either a non-existing edge (if the graph is not complete) is inserted or an existing edge is deleted. Do we need to sample edges from scratch?More generally, if we have a sequence of edge insertions or deletions (call it an update), how can we maintain our sample of edges efficiently?If we naively run an sampler responsible for each edge in the sample for each update, we need $\tilde{O}(n)$ time per update.   Here is an idea of how one could solve this problem.

Idea: When an update takes place, we will invoke just one -rather than K-  sampler. Let , where is the edge set of the graph after updates.

• Let be an -wise independent hash function
• The -th “bucket” is responsible for all edges such that , for each . We also run an independent copy of an sampler for each bucket.
• When an update takes place, we hash the resulting inserted or deleted edge and invoke the corresponding sampler.
• The overall type of guarantee one would like to get is that the probability of an edge being in the sample is .  Also, one would like to make probabilistic statements that hold with high probability for all updates and for all vertices. This goal determines the -wise independence, as we want a Chernoff and a union bound to give a failure probability that is

For all the technical details and the formal statement of the results, take a look at [Lemma 4.3, 1] which is joint work with Sayan Bhattacharya, Monika Henzinger and Danupon Nanongkai.

References

[1] Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams, STOC 2015 by Sayan Bhattacharya, Monika Henzinger and Danupon Nanongkai and Charalampos E. Tsourakakis