18 citations · 169 across the 45 of their papers we have counts for
20 papers · 1 filter
Estimating Hitting Times Locally At Scale
Themistoklis Haris, Fabian Spaeh, Spyros Dragazis +1
Hitting times provide a fundamental measure of distance in random processes, quantifying the expected number of steps for a random walk starting at node to reach node . They…
Node-Differentially Private Estimation of the Number of Connected Components
Iden Kalemaj, Sofya Raskhodnikova, Adam Smith +1
We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an -vertex graph and…
Finding Densest -Connected Subgraphs
Francesco Bonchi, David García-Soriano, Atsushi Miyauchi +1
Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph dis…
Joint Alignment From Pairwise Differences with a Noisy Oracle
Michael Mitzenmacher, Charalampos E. Tsourakakis
In this work we consider the problem of recovering discrete random variables (where is constant) with the smallest possible numbe…
Query-Efficient Correlation Clustering
David García-Soriano, Konstantin Kutzkov, Francesco Bonchi +1
Correlation clustering is arguably the most natural formulation of clustering. Given n objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the…
Flowless: Extracting Densest Subgraphs Without Flow Computations
Digvijay Boob, Yu Gao, Richard Peng +4
We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgra…