Size-Estimation Framework with Applications to Transitive Closure and Reachability

By Edith Cohen. 1997

Computing the transitive closure in directed graphs is a fundamental graph problem. We consider the more restricted problem of computing the number of nodes reachable from every node and the size of the transitive closure. The fastest known transitive closure algorithms run inO(min{mn,n2.38}) time, wherenis the number of nodes andmthe number of edges in the graph. We present anO(m) time randomized (Monte Carlo) algorithm that estimates, with small relative error, the sizes of all reachability sets and the transitive closure. Another ramification of our estimation scheme is a O(m) time algorithm for estimating sizes of neighborhoods in directed graphs with nonnegative edge lengths. Our size-estimation algorithms are much faster than performing the respective explicit computations.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, methodology): “Compared to [2], the novel application of Cohen’s algorithm arises for estimating influence for multiple sources, which drastically reduces the computation by cleverly using the least-label list from single source.”
Efficient influence maximization in social networks (2009, methodology): “Let G (cid:48)∗ denote the resulting directed acyclic graph (DAG), and let Cohen’s algorithm estimates | R G (cid:48) ( S ∪ { v } ) | in T iterations.”
Counting Distinct Elements in a Data Stream (2002, result): “Cohen [ Coh97 ] considered this problem in the context of graph-theoretic applications; her algorithm is similar in spirit to that of [FM85,AMS99]; specifically, it has a high-level viewpoint similar to the first algorithm in this paper.”
Finding interesting associations without support pruning (2000, methodology): “3 Min-Hashing Schemes The Min-Hashing scheme used an idea due to Cohen [5], in the context of estimating transitive closure and reachability sets.”
Distributed verification and hardness of distributed approximation (2010, unknown): “partiteness, cycle containment, e-cycle containment, cut, s-t cut, least-element list [4, 14], and edge on all paths.”
Ligra: a lightweight graph processing framework for shared memory (2013, background): “Cohen [10] describes an algorithm for approximating neighborhood sizes, which requires O(|E| log |V |) expected number of operations for undirected graphs.”
Bootstrapped Graph Diffusions (2018, background): “The use of distance or reachability sketching based on [10] allows for highly scalable label learning also over the sketched affinity matrix.”
An optimal algorithm for the distinct elements problem (2010, background): “The problem of space-efficient F0-estimation is well-studied, beginning with the work of Flajolet and Martin [20], and continuing with a long line of research, [3, 4, 5, 6, 9, 12, 16, 17, 19, 23, 24, 26, 36].”
Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “It ﬁrst generates c weighted versions of G , denoted as g 1 , g 2 , . . . , g c , such that in each g i ( i ∈ [1 , c ] ), the length of each edge e is sampled from L ( e ) independently. g , and After that, it constructs a sketch [11] on each i utilizes the sketches for inﬂuence maximization.”
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2017, background): “e use of distance or reachability sketching based on [9] allows for highly scalable label learning also over the sketched anity matrix.”
Scalable diffusion-aware optimization of network topology (2014, methodology): “We will adapt a linear-time algorithm by Cohen [5] for our problem.”
ANF: a fast and scalable tool for data mining in massive graphs (2002, methodology): “Lipton and Naughton’s work was improved by Cohen, who gave an O(m) time algorithm using only O(n + m) memory [4].”
Google news personalization: scalable online collaborative filtering (2007, background): “Our similarity measure, the Jaccard coe.cient, thankfully admits a LSH scheme called Min-Hashing (short for Minwise Independent Permutation Hashing) that was .rst introduced by Cohen [8] to estimate the size of transitive closure and reachability sets (see also Broder [4]).”
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2018, background): “The use of distance or reachability sketching based on [10] allows for highly scalable label learning also over the sketched affinity matrix.”
Robust and efficient fuzzy match for online data cleaning (2003, background): “denote an indicator variable over a boolean X, i.e., I[X] = 1 if X is true, and 0 otherwise. Then (as shown in [4, 6 ]),”