About

Professor Shankar Bhamidi has had the opportunity to work with many students on problems in probability, random graphs, network science, statistics, and machine learning. His advising has included PhD students, master's students, and broader dissertation mentoring across the department. His research focus encompasses a range of topics related to complex networks and statistical learning techniques, including community detection methods, latent community structures, high-dimensional problems in statistics and probability, and network embedding. Through his mentorship, he has guided students on dissertation topics such as dynamic random graphs, statistical analysis of relational data, and testing-based community detection methods for complex networks. Professor Bhamidi's work integrates probabilistic and geometric approaches to analyze non-standard data, contributing to the understanding of network-based data and statistical learning consistency. He has also served on PhD dissertation committees across multiple departments, reflecting his broad engagement in interdisciplinary research and mentoring.

Research topics

• Discrete mathematics
• Mathematics
• Combinatorics
• Computer Science
• Geography
• Economic geography
• Regional science
• Cartography
• Mathematical analysis
• Geometry
• Statistical physics
• Physics

Selected publications

• Consistency of Lloyd’s algorithm under perturbations

  Electronic Journal of Statistics · 2026-01-01

  articleOpen access
  PublisherDOI

• The spatial distribution of coupling between tau and neurodegeneration in amyloid-β positive mild cognitive impairment

  UNC Libraries · 2026-04-21

  articleOpen access
  PublisherDOI

• Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms

  ArXiv.org · 2025-07-25 · 1 citations

  preprintOpen access1st authorCorresponding

  We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applications in biology and social sciences \cites{madeira-survey,shabalin2009finding} and is known to exhibit a computation-to-optimization gap between the optimal value and best values achievable by existing polynomial time algorithms. In this paper we consider the class of online algorithms, which includes the best known algorithm for this problem, and derive a tight approximation factor ${4\over 3\sqrt{2}}$ for this class. The result is established using a simple implementation of recently developed Branching-Overlap-Gap-Property \cite{huang2025tight}. We further extend our results to $(\mathbb R^n)^{\otimes p}$ tensors with i.i.d. Gaussian entries, for which the approximation factor is proven to be ${2\sqrt{p}/(1+p)}$.

  PublisherOA PDFDOI

• Multiscale genesis of a tiny giant for percolation on scale-free random graphs

  The Annals of Probability · 2025-07-01 · 1 citations

  articleOpen access1st authorCorresponding

  We study the critical behavior for percolation on inhomogeneous random networks on n vertices, where the weights of the vertices follow a power-law distribution with exponent τ∈(2,3). Such networks, often referred to as scale-free networks, exhibit critical behavior when the percolation probability tends to zero at an appropriate rate, as n→∞. We identify the critical window for several scale-free random graph models, such as the Norros–Reittu model, Chung–Lu model and generalized random graphs. Surprisingly, there exists a finite time inside the critical window, after which we see a sudden emergence of a “tiny” giant component. This is a novel behavior, which is in contrast with the critical behavior in other known universality classes with τ∈(3,4) and τ>4. Precisely, for edge-retention probabilities πn=λn−(3−τ)/2, there is an explicitly computable λc>0 such that the critical window is of the form λ∈(0,λc), where the largest clusters have size of order nβ with β=(τ2−4τ+5)/[2(τ−1)]∈[ 2−1,12) and have nondegenerate scaling limits, while in the supercritical regime λ>λc, a unique “tiny giant” component of size Θ(n) emerges, and its size concentrates. For λ∈(0,λ c), the scaling limit of the maximum component sizes can be described in terms of components of a one-dimensional inhomogeneous percolation model on Z+ studied in a seminal work by Durrett and Kesten (In A Tribute to Paul Erdős (1990) 161–176 Cambridge Univ. Press). For λ>λc, we use a relation to general inhomogeneous random graphs, as studied by Bollobás, Janson and Riordan (Random Structures Algorithms 31 (2007) 3–122), to prove that the sudden emergence of the tiny giant is caused by a phase transition inside a smaller core of vertices of weight of order at least n.

  PublisherOA PDFDOI

• Large Deviations for Markovian Graphon Processes and Associated Dynamical Systems on Networks

  ArXiv.org · 2025-06-10

  preprintOpen access1st authorCorresponding

  We consider temporal models of rapidly changing Markovian networks modulated by time-evolving spatially dependent kernels that define rates for edge formation and dissolution. Alternatively, these can be viewed as Markovian networks with $O(1)$ jump rates viewed over a long time horizon. In the regimes we consider, the window averages of graphon valued processes over suitable time intervals are natural state descriptors for the system. Under appropriate conditions on the jump-rate kernels, we establish laws of large numbers and large deviation principles(LDP) for the graphon processes averaged over a suitable time window, both in the weak topology and with respect to the cut norm in the associated graphon space. Although the problem setting and analysis are more involved than for the well-studied static random network model, the variational problem associated with the rate function admits an explicit solution, yielding an equally tractable, though different, expression for the rate function, similar to the static case. Using these results, we then establish the LDP for node-valent dynamical systems driven by the underlying evolving network.

  PublisherOA PDFDOI

• Evolution of recursive trees with limited memory

  ArXiv.org · 2025-10-21

  preprintOpen access

  Motivated by questions in social networks, distributed computing and probabilistic combinatorics, the last few years have seen increasing interest in network evolution models where new vertices entering the system need to make decisions based on a partial snapshot of the current state of the network. This paper considers a specific variant of the classical random recursive tree dynamics, where a vertex at time $n+1$ has information only on those vertices that have arrived in the interval $[j(n), n]$ for a sequence $j(n) \uparrow \infty$, and connects to vertices uniformly at random amongst this set. We consider two different regimes on the density information, termed macroscopic and mesoscopic regimes, which respectively correspond to $j(n)=θn$ for some $θ\in (0,1)$, and $j(n)=n-n^β$ for some $β\in (0,1)$. Our main interest is in studying asymptotics of various local and global functionals of the network. We show that in the macroscopic regime, the local limit is expressed in terms of an associated continuous time branching process that depends on the parameter $θ$, while it is a $\mathrm{Poisson}(1)$-branching process in the mesoscopic regime for any $β\in (0,1)$. Furthermore, the height of the macroscopic tree is logarithmic, which we prove exploiting a connection with scaled-attachment random recursive trees (SARRTs) as studied by Devroye, Fawzi and Fraiman (RSA 2011), while it is polynomial in the mesoscopic regime; our argument in this latter case relies on a differential equation approach to track the ancestor indices of late-coming vertices, together with a multiscale analysis. Further, we develop an exploration algorithm to simultaneously reveal the ancestral path of youngest vertices. Using this algorithm, we show that in the mesoscopic regime, the global structure experiences a phase transition at $β=1/2$.

  PublisherOA PDFDOI

• Network Evolution With Mesoscopic Delays

  Random Structures and Algorithms · 2025-09-01 · 1 citations

  articleOpen accessCorresponding

  ABSTRACT 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 systems, particularly in a temporal context. Recent advancements in fields like distributed cyber‐security and social networks have spurred the creation of probabilistic models of evolution, where individuals make decisions based on only partial information about the network's current state. This paper seeks to explore models incorporating network delay , where new participants receive information from a time‐lagged snapshot of the system. In the context of mesoscopic network delays, we develop probabilistic tools built on stochastic approximation to understand asymptotics of both local functionals, such as local neighborhoods and degree distributions, as well as global properties, such as the evolution of the degree of the network's initial founder. A companion paper (Banerjee et al. 2024) explores the regime of macroscopic delays in the evolution of the network.

  PublisherOA PDFDOI

• Community Extraction in Multilayer Networks with Heterogeneous Community Structure.

  Europe PMC (PubMed Central) · 2024-07-27 · 33 citations

  article

  Multilayer networks are a useful way to capture and model multiple, binary or weighted relationships among a fixed group of objects. While community detection has proven to be a useful exploratory technique for the analysis of single-layer networks, the development of community detection methods for multilayer networks is still in its infancy. We propose and investigate a procedure, called Multilayer Extraction, that identifies densely connected vertex-layer sets in multilayer networks. Multilayer Extraction makes use of a significance based score that quantifies the connectivity of an observed vertex-layer set through comparison with a fixed degree random graph model. Multilayer Extraction directly handles networks with heterogeneous layers where community structure may be different from layer to layer. The procedure can capture overlapping communities, as well as background vertex-layer pairs that do not belong to any community. We establish consistency of the vertex-layer set optimizer of our proposed multilayer score under the multilayer stochastic block model. We investigate the performance of Multilayer Extraction on three applications and a test bed of simulations. Our theoretical and numerical evaluations suggest that Multilayer Extraction is an effective exploratory tool for analyzing complex multilayer networks. Publicly available code is available at https://github.com/jdwilson4/MultilayerExtraction.

  PublisherDOI

• Critical first passage percolation on random graphs

  arXiv (Cornell University) · 2024-12-04

  preprintOpen access1st authorCorresponding

  In 1999, Zhang proved that, for first passage percolation on the square lattice $\mathbb{Z}^2$ with i.i.d. non-negative edge weights, if the probability that the passage time distribution of an edge $P(t_e = 0) =1/2 $, the critical value for bond percolation on $\mathbb{Z}^2$, then the passage time from the origin $0$ to the boundary of $[-n,n]^2$ may converge to $\infty$ or stay bounded depending on the nature of the distribution of $t_e$ close to zero. In 2017, Damron, Lam, and Wang gave an easily checkable necessary and sufficient condition for the passage time to remain bounded. Concurrently, there has been tremendous growth in the study of weak and strong disorder on random graph models. Standard first passage percolation with strictly positive edge weights provides insight in the weak disorder regime. Critical percolation on such graphs provides information on the strong disorder (namely the minimal spanning tree) regime. Here we consider the analogous problem of Zhang but now for a sequence of random graphs $\{G_n:n\geq 1\}$ generated by a supercritical configuration model with a fixed degree distribution. Let $p_c$ denote the associated critical percolation parameter, and suppose each edge $e\in E(G_n)$ has weight $t_e \sim p_c δ_0 +(1-p_c)δ_{F_ζ}$ where $F_ζ$ is the cdf of a random variable $ζ$ supported on $(0,\infty)$. The main question of interest is: when does the passage time between two randomly chosen vertices have a limit in distribution in the large network $n\to \infty$ limit? There are interesting similarities between the answers on $\mathbb{Z}^2$ and on random graphs, but it is easier for the passage times on random graphs to stay bounded.

  PublisherOA PDFDOI

• Scaling limits and universality: Critical percolation on weighted graphs converging to an 𝐿³ graphon

  Transactions of the American Mathematical Society · 2024-09-05

  article

  We develop a general universality technique for establishing metric scaling limits of critical random discrete structures exhibiting mean-field behavior that requires four ingredients: (i) from the barely subcritical regime to the critical window, components merge approximately like the multiplicative coalescent, (ii) asymptotics of the susceptibility functions are the same as that of the Erdős-Rényi random graph, (iii) asymptotic negligibility of the maximal component size and the diameter in the barely subcritical regime, and (iv) macroscopic averaging of distances between vertices in the barely subcritical regime. As an application of the general universality theorem, we establish, under some regularity conditions, the critical percolation scaling limit of graphs that converge, in a suitable topology, to an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L cubed"> <mml:semantics> <mml:msup> <mml:mi>L</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:annotation encoding="application/x-tex">L^3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> graphon. In particular, we define a notion of the critical window in this setting. The <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L cubed"> <mml:semantics> <mml:msup> <mml:mi>L</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:annotation encoding="application/x-tex">L^3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> assumption ensures that the model is in the Erdős-Rényi universality class and that the scaling limit is Brownian. Our results do not assume any specific functional form for the graphon. As a consequence of our results on graphons, we obtain the metric scaling limit for Aldous-Pittel’s RGIV model inside the critical window (see D.J. Aldous and B. Pittel [Random Structures Algorithms 17 (2000), pp. 79–102]). Our universality principle has applications in a number of other problems including in the study of noise sensitivity of critical random graphs (see E. Lubetzky and Y. Peled [Israel J. Math. 252 (2022), pp. 187–214]). In Bhamidi et al. [ <italic>Scaling limits and universality II: geometry of maximal components in dynamic random graph models in the critical regime</italic> , In preparation], we use our universality theorem to establish the metric scaling limit of critical bounded size rules. Our method should yield the critical metric scaling limit of Ruciński and Wormald’s random graph process with degree restrictions provided an additional technical condition about the barely subcritical behavior of this model can be proved (see A. Ruciński and N. C. Wormald [Combin. Probab. Comput. 1 (1992), pp. 169–180]).

  PublisherDOI

Recent grants

• Dynamic network models: Entrance boundary and continuum scaling limits, condensation phenomena and probabilistic combinatorial optimization

  NSF · $100k · 2016–2020

• Collaborative Research: Specification and Estimation of Exponential Family Random Graph Models for Weighted Networks

  NSF · $203k · 2014–2017

• Structural properties of random tree models and their applications in network flows, brain circulation networks and statistical physics

  NSF · $210k · 2011–2015

Frequent coauthors

• Remco van der Hofstad

  Eindhoven University of Technology

  45 shared

• Tauhid Zaman

  Yale University

  26 shared

• J. Michael Steele

  25 shared

• Sanchayan Sen

  20 shared

• Andrew B. Nobel

  19 shared

• Gerard Hooghiemstra

  Delft University of Technology

  17 shared

• Sayan Banerjee

  16 shared

• Amarjit Budhiraja

  14 shared

Labs

• Shankar Bhamidi LabPI