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.


[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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: