# Maintaining a random sample of edges on a dynamic graph

Suppose that we have a sample of $K=O(npolylog(n))$ edges, sampled uniformly at random from the edge set $E$ of a graph $G(V,E)$. Also, let $K\ll |E|=m$. 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 $K$ 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 $K$ edges efficiently?If we naively run an $l_0$ 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- $l_0$ sampler. Let $E^* = {[n] \choose 2} \supseteq E^{(t)}$, where $E^{(t)}$ is the edge set of the graph after $t$ updates.

• Let $h:E^* \rightarrow [s_k]$ be an $r$-wise independent hash function
• The $i$-th “bucket” $Q_i^{(t)}$ is responsible for all edges such that $h(e)=i$, for each $i=1,\ldots,s_k$. We also run an independent copy of an $l_0$ sampler for each bucket.
• When an update takes place, we hash the resulting inserted or deleted edge $(u,v)$ and invoke the corresponding $l_0$ sampler.
• The overall type of guarantee one would like to get is that the probability of an edge being in the sample is $\approx \frac{K}{m}$.  Also, one would like to make probabilistic statements that hold with high probability for all updates and for all vertices. This goal determines the $r$-wise independence, as we want a Chernoff and a union bound to give a failure probability that is $o(1)$

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

 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