4 papers
Dynamic PageRank: Algorithms and Lower Bounds
Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović +2
We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector for a graph under a sequence of…
Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the nodes so to minimize the total number of between-cluster positive and w…
Nearly Tight Bounds For Differentially Private Min - and Multiway Cut
Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka
Finding min - cuts in graphs is a basic algorithmic tool with applications in image segmentation, community detection, reinforcement learning, and data clustering. In this pr…
Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs
Slobodan Mitrović, Theodore Pan
Finding dense subgraphs is a fundamental algorithmic tool in data mining, community detection, and clustering. In this problem, one aims to find an induced subgraph whose edge-to-v…