We first present a simple algorithm for sampling uniformly at random from the local neighborhood of each node. The approach builds upon min-wise independent permutations [1]}, a powerful technique for estimating the Jaccard similarity between sets. Assume we are given two sets \(A \subseteq U\)  and \(B \subseteq U\) , where \(U\)  is a universe of elements, for example all integers. We want to estimate the fraction \(\frac{|A\cap B|}{|A\cup B|}\) . Let \(\pi : U \rightarrow U\)  be a random permutation of the elements in \(U\) . With probability \(\frac{|A\cap B|}{|A\cup B|}\)  the smallest element in \(A \cup B\)  with respect to the total order defined by \(\pi \)  is contained in \(A\cap B\)  and thus the indicator variable denoting whether the smallest elements in \(\pi (A)\)  and \(\pi (B)\)  are identical yields an unbiased estimator of the Jaccard similarity \(J(A, B)\) . The mean of \(t = O(\frac{1}{\alpha \varepsilon ^2})\)  independent estimator is an \(1\pm \varepsilon \) -approximation of \(J(A, B) \ge \alpha \)  with probability more than 1/2. The success probability can be boosted to any \(1-\delta \)  by taking the median of \(\log 1/\delta \)  independent estimators.
