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

### Like this:

Like Loading...