4 papers · 1 filter
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…