12 papers
Subcritical percolation and network archaeology on random recursive tree substrate networks
Shankar Bhamidi, Akshay Sakanaveeti
We study a network-archaeology problem for a dynamic graph whose latent substrate is a random recursive tree and whose observed topology is enriched by an independent homogeneous E…
Network evolution with self-reinforcement
Shankar Bhamidi, Remco van der Hofstad, Frank den Hollander +1
We study a new class of preferential attachment trees with \emph{self-reinforcement}. At each time, each vertex is assigned a weight equal to the cumulative sum over past times of…
The stochastic block model has the overlap graph property for modularity
Shankar Bhamidi, David Gamarnik, Remco van der Hofstad +4
The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to…
Consistency of Lloyd's Algorithm Under Perturbations
Dhruv Patel, Hui Shen, Shankar Bhamidi +2
In the context of unsupervised learning, Lloyd's algorithm is one of the most widely used clustering algorithms. It has inspired a plethora of work investigating the correctness of…
Non-equilibrium coagulation processes and subcritical percolation on evolving networks
Sayan Banerjee, Shankar Bhamidi, Remco van der Hofstad +1
We investigate percolation on growing networks where the evolution of connected components resembles a non-equilibrium version of the multiplicative coalescent. The supercritical $…
Network evolution with mesoscopic delay
Sayan Banerjee, Shankar Bhamidi, Partha Dey +1
Owing to the influence of real-world networks both in science and society, numerous mathematical models have been developed to understand the structure and evolution of these syste…