The last few years have made clear the role and impact of networks in our daily lives. Examples include the major role that the Internet as an information transmission network plays in our professional or personal lives; the influence that social networks have in the dissemination of news and information and impact our politics; disease transmission through contact and transportation networks; or the push in science to understand biological processes at the systems level including the emergence of macroscopic phenomenon such as consciousness and memory in neuroscience through the microscopic interaction of neurons. The importance of understanding the above application areas have generated an interdisciplinary effort from a wide array of communities (math, statistics, physics, CS and domain sciences like political science and neuroscience) to both collect data on these systems, postulate models for the evolution of these systems over time and develop models of processes such as epidemics or search algorithms on these systems. A recent talk aimed at high school students describing the motivation for the field can be found here:
I am an applied probabilist and my broad goals are to use techniques in mathematics and statistics to help domain scientists understand properties of their models, help them collect data from these networks via efficient algorithms and develop tools to analyze collected data. In most cases, the models postulated are so complex or the size of these networks are so large that unless one “does the math’’, it is hard to gain insight into these systems and models. Below is an overly verbose description of my research till date. My work falls in three interconnected areas each of which are expanded below (and when the text says “I have worked on” in many cases this means I have worked on this with an amazing set of collaborators, students etc!):
- Diffusion of information through networks.
- Emergence of connectivity within networks.
- Algorithmic and statistical applications of networks.
Verbose descriptions of my work can be found below. Numbers in the text below indicated references which are given at the bottom of the page. A video describing technical aspects of some of my recent work can be found here:
Diffusion of information through networks
Transportation networks entrusted with carrying flow of material between different parts of the network arise in a number of settings including the Internet (transporting information), the electrical grid, and road and rail networks. Such networks are described not just by the graph structure on vertices (such as servers or power plants) with edges representing valid connections, but also by edge weights arising through phenomenon such as congestion or geographical distance. My work in this area includes:
- understanding how these costs affect the geometry of the network and the time it takes for material to traverse the optimal path in various network models [5,21–23,25,34]. In many examples, weights on the edges of the network represent costs and the network tries to minimize costs of connecting individuals, whilst the amount of time information takes to percolate between individuals is measured by the number of edges on the optimal path. My work involves mathematically understanding both functionals for a host of network models. One of the major reasons for the growth of network models was the finding in [37] via sending traceroutes through the internet that the degree distribution of the internet seemed to have a heavy tail. I used the theory developed in the above set of papers in [19] to give a rigorous understanding of the relationship between the degree distribution found by algorithms such as traceroute and the underlying degree distribution of the graph.
- In a basic statistics course, one of the “central” distributions that shows up is the normal distribution (used for z-scores etc); this is a precursor to a much deeper phenomenon of “universality” where in settings with lots of small interactions, irrespective of the details of these interactions, probability distributions such as the normal emerge in giving quantitative insight into the nature of these interaction in a large system (e.g. large sample) limit and play a key role in statistics. In analogy to this, we studied a “universality’’ phenomenon for flows through networks in [24] and showed that similar asymptotics for optimal paths for network models hold for a wide range of possible edge cost distributions.
Related questions of flows through networks that I have studied include: understanding the vulnerability of these models against directed attacks [35] (e.g. a malicious attack causing the removal of important individuals in the network), in [2] rigorously understanding functionals for measuring the importance of individuals in a network postulated by social scientists (betweenness centrality of nodes) and in [5] analyzing pricing mechanisms which measure the importance of edges, originating from auction theory including the Vickrey-Clarke-Grooves (VCG) measure of overpayment of edges. - As described above, for a number of applications, one is interested in dynamic models on networks such as models for the spread of an infection (e.g. human or computer virus) or models of neurons each of whom are influenced by the individuals they are connected to. In [26,30] we studied epidemic models on networks and developed mathematical techniques to rigorously analyze these models including derving connections between the structural properties of the network and the rate of spread of the epidemic that would imply (or preclude) the spread of the epidemic to a non-trivial fraction of the network. In [15], in part motivated by models from areas like neuroscience and distributed computing, we considered models of networks where each node (e.g.neuron) is generating a signal (modelled via diffusions) and these signals are coupled through a network structure. We developed probabilistic techniques to understand the evolution of such systems in the large network limit.
Emergence of connectivity within networks
One of the foundational pieces of probabilistic combinatorics goes back to the 1960’s in the work of Erdos and Renyi. They found the following amazing phenomenon even for the simplest possible network model: start with n individuals. Fix a parameter λ that measures “average’’ number of friends per person in the network. Each individual connects to every other individual with probability λ/n. Then they found that when λ<1 the size of the largest connected component is of order , when λ=1 the largest and second largest components scale like whilst for λ>1 the size of the largest connected component scaled like f(λ)n where f(λ)>0 so was of the same order of the size of the network. Thus analogous to various phase transitions in physics (ice turning to water beyond a critical temperature), λ=1 is called the critical time for this model. In the ensuing decades, mathematicians found this sort of phenomenon for a host of network models and further found connections between the emergence of the large connected component as one traverses through the critical time and various models of gelation phenomenon in colloidal chemistry.
In this area my work includes:
- understanding the nature of emergence of this giant component and the critical regime in various inhomogenous random graph models [27,28].
- Suppose one has a collection of individuals who are trying to form connections between each other. Suppose there is a controller (with specific goals, for example to either speed up or slow down the emergence of a large connected component) for the network who has limited control in what edges are allowed to be formed at any given time. This question (motivated largely by computer science) has given rise to a thriving area of probabilistic combinatorics. My work in this area has been studying the nature of emergence of a large connected component for a class of control rules called bounded size rules [12–14]. On a related note imagine the evolution of components in a network via formation of edges as time ensues. One can view this a “race” between the various components to aggregate as many individuals within themselves thus causing changes in the identity of the “leader” (component with largest size). Erdos proposed the question of understanding this “leader problem” in particular the time at which the identity of the leader component fixates and does not change. For the Erdos-Renyi random graph this was solved by Luczak in the 90’s using combinatorial techniques. A more general problem related to inhomogenous random graph models was proposed and solved in [1].
- I studied more fine grained properties (topological or metric structure) of components of various random graph models in the critical regime [10,11,18,32] in particular showing the convergence of these components to random fractals (in some cases related to the limits of the classical Erdos-Renyi random graph, in other cases deriving new classes of random fractals). In a related direction, suppose one models a crystal as a graph consisting of molecules connected by edges. Now suppose you have a particle moving along the network by hopping randomly from one vertex to another using the edges in the network but “corrupting’’ the edges of the network. After enough steps, the network will get disconnected. In [31] we studied properties of the largest connected component in the network in the critical regime close to disconnection time once again to understand fractal properties of the resulting topology.
Algorithmic and statistical applications of networks
In this area my research includes:
- Understanding network data from indirect measurements. This includes Network Tomography i.e. developing provably accurate algorithms (we used ideas from phylogenetics) to reconstruct the structure of large communication networks from indirect measurements sent to a subset of vertices in [36]. Many real world networks are enormous (e.g. social networks run into billions of nodes; citation networks in hundereds of thousands etc). Even understanding elementary properties (e.g. typical path length between individuals) of these networks can be computationally non-trivial. In [3] we studied estimation of functionals such as the degree distribution from sampling network nodes or edges. Two new approaches especially for networks with heavy tailed degree distribution were proposed and evaluated both on real and synthetic data.
- Rigorously analyzing models of networks changing in time including models for Twitter networks [33] and developing general theory for such dynamic network models in [8]; the effect of changes in the driving parameters of these models and the development of statistical estimation techniques of when these change points happened (including consistency properties of these estimators) in [29]. The adjacency matrix of the network is one key representation of the network and is heavily used in machine learning tasks such as spectral clustering to partition the network. In [7] we developed theory to understand properties of these matrices (such as the spectral distribution) for various network models.
- I have developed math theory for understanding the behavior of MCMC algorithms used to generate one of the most popular network models in social science called exponential random graphs [6,9], and analyzed the use of these algorithms to simulate networks conditioned on atypical behavior [20]. Motivated by applications in migration flows in the US as well as brain networks, I have also studied extensions of the above techniques for weighted network models including algorithms for various models in [44], using these models and algorithms to gain insight into brain networks in [42] and understanding the behavior of these models in the large network limit in [16]. In [41] we used techniques from combinatorics (that I had previously used in studying critical random graphs) to convert data on vascular networks in the brain (represented as trees) from a sample of patients and convert these into function space so that tools from FDA could then be brought to bear on the data and give insight into the key factors of variation in the data.
- I have developed methodology to conduct exploratory data analysis of network data, in particular developing computational techniques and packages to extract subsets of individuals in a network that seem to form a “community’’ i.e. a collection that seem to be more densely connected to each other as opposed to outside the community. Here my work includes developing statistically principled techniques to discover community structure in networks [43,46] including weighted network data originating in areas such as economic flows through the US or bike-share networks [38–40]. One of the most important directions of research in this area is multi-layer networks (e.g. connectivity structure for the same regions in the brain observed for many individuals both normal and those afflicted by some condition such as Alzheimers disease). Community detection techniques for such data were developed in [45]. In many applications such as the above or those arising in bioinformatics and genetics, one has to solve an optimization problem which is computationally hard and thus has to resort to local search algorithms which often converge to local as opposed to global optima. In [17] we studied the complexity (number of local optima, size of a typical local optima as compared to the global optima etc) of such local search algorithms in particular to discover large average submatrices in a data matrices to understand the behavior of such local search schemes in a tractable setting.
References
[1] Louigi Addario-Berry, Shankar Bhamidi, and Sanchayan Sen. 2019. A probabilistic approach to the leader problem in random graphs. Submitted to Random Structures & Algorithms (2019).
[2] David J. Aldous and Shankar Bhamidi. 2010. Edge flows in the complete random-lengths network. Random Structures & Algorithms 37, 3 (2010), 271–311. DOI:https://doi.org/10.1002/rsa.20306
[3] Nelson Antunes, Shankar Bhamidi, Tianjian Guo, Vladas Pipiras, and Bang Wang. 2019. Sampling-based estimation of in-degree distribution with applications to directed complex networks. Submitted to Journal of Computational and Graphical Statistics (2019).
[4] Sayan Banerjee, Shankar Bhamidi, and Iain Carmichael. 2019. Fluctuation bounds for continuous time branching processes and nonparametric change point detection in growing networks. Submitted to Annals of Applied Probability (2019).
[5] S. Bhamidi. 2008. First passage percolation on locally treelike networks I. Dense random graphs. Journal of Mathematical Physics 49, (2008), 125218.
[6] S. Bhamidi, G. Bresler, and A. Sly. Mixing time of exponential random graphs. In Foundations of computer science, 2008. FOCS’08. IEEE 49th annual ieee symposium on, 803–812.
[7] S. Bhamidi, S.N. Evans, and A. Sen. 2009. Spectra of large random trees. Journal of Theoretical Probability (2009), 1–42.
[8] Shankar Bhamidi. 2007. Universal techniques to analyze preferential attachment trees: Global and local analysis. Preprint 19, (2007).
[9] Shankar Bhamidi, Guy Bresler, and Allan Sly. 2011. Mixing time of exponential random graphs. Annals of Applied Probability 21, 6 (2011), 2146–2170. DOI:https://doi.org/10.1214/10-AAP740
[10] Shankar Bhamidi, Nicolas Broutin, Sanchayan Sen, and Xuan Wang. 2014. Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph. Will be Re-submitted to Annals of Probability (2014).
[11] Shankar Bhamidi, Amarjit Budhiraja, and Sanchayan Sen. 2017. Critical random graphs and the differential equations technique. Indian J. Pure Appl. Math. 48, 4 (2017), 633–669. DOI:https://doi.org/10.1007/s13226-017-0249-0
[12] Shankar Bhamidi, Amarjit Budhiraja, and Xuan Wang. 2013. Aggregation models with limited choice and the multiplicative coalescent. Random Structures & Algorithms (2013), n/a–n/a. DOI:https://doi.org/10.1002/rsa.20493
[13] Shankar Bhamidi, Amarjit Budhiraja, and Xuan Wang. 2013. The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs. Probability Theory and Related Fields (2013), 1–64. DOI:https://doi.org/10.1007/s00440-013-0540-x
[14] Shankar Bhamidi, Amarjit Budhiraja, and Xuan Wang. 2014. Bounded-size rules: The barely subcritical regime. Combinatorics, Probability and Computing FirstView, (May 2014), 1–34. DOI:https://doi.org/10.1017/S0963548314000261
[15] Shankar Bhamidi, Amarjit Budhiraja, and Ruoyu Wu. 2019. Weakly interacting particle systems on inhomogeneous random graphs. Stochastic Processes and their Applications 129, 6 (2019), 2174–2206.
[16] Shankar Bhamidi, Suman Chakraborty, Skyler Cranmer, and Bruce Desmarais. 2018. Weighted exponential random graph models: Scope and large network limits. Journal of Statistical Physics 173, 3-4 (2018), 704–735. DOI:https://doi.org/10.1007/s10955-018-2103-0
[17] Shankar Bhamidi, Partha S. Dey, and Andrew B. Nobel. 2017. Energy landscape for large average submatrix detection problems in Gaussian random matrices. Probability Theory and Related Fields 168, 3-4 (2017), 919–983. DOI:https://doi.org/10.1007/s00440-017-0766-0
[18] Shankar Bhamidi, Souvik Dhara, Remco van der Hofstad, and Sanchayan Sen. 2019. Universality for critical heavy-tailed network models: Metric structure of maximal components. Submitted to Electronic Journal of Probability (2019).
[19] Shankar Bhamidi, Jesse Goodman, Remco van der Hofstad, and Júlia Komjáthy. 2015. Degree distribution of shortest path trees and bias of network sampling algorithms. Annals of Applied Probability 25, 4 (2015), 1780–1826. DOI:https://doi.org/10.1214/14-AAP1036
[20] Shankar Bhamidi, Jan Hannig, Chia Ying Lee, and James Nolen. 2015. The importance sampling technique for understanding rare events in Erdoős-Rényi random graphs. Electron. J. Probab. 20, (2015), no. 107, 30. DOI:https://doi.org/10.1214/EJP.v20-2696
[21] Shankar Bhamidi and Remco van der Hofstad. 2012. Weak disorder asymptotics in the stochastic mean-field model of distance. Ann. Appl. Probab. 22, 1 (2012), 29–69. DOI:https://doi.org/10.1214/10-AAP753
[22] Shankar Bhamidi and Remco van der Hofstad. 2017. Diameter of the stochastic mean-field model of distance. Combin. Probab. Comput. 26, 6 (2017), 797–825. DOI:https://doi.org/10.1017/S0963548317000232
[23] Shankar Bhamidi, Remco van der Hofstad, and Gerard Hooghiemstra. 2011. First passage percolation on the Erdős-Rényi random graph. Combin. Probab. Comput. 20, 5 (2011), 683–707. DOI:https://doi.org/10.1017/S096354831100023X
[24] Shankar Bhamidi, Remco van der Hofstad, and Gerard Hooghiemstra. 2012. Universality for first passage percolation on sparse random graphs. arXiv preprint arXiv:1210.6839 (2012).
[25] Shankar Bhamidi, Remco van der Hofstad, and Gerard Hooghiemstra. 2013. Weak disorder in the stochastic mean-field model of distance II. Bernoulli 19, 2 (2013), 363–386. DOI:https://doi.org/10.3150/11-BEJ402
[26] Shankar Bhamidi, Remco van der Hofstad, and Júlia Komjáthy. 2014. The front of the epidemic spread and first passage percolation. J. Appl. Probab. 51A, Celebrating 50 Years of The Applied Probability Trust (2014), 101–121. DOI:https://doi.org/10.1239/jap/1417528470
[27] Shankar Bhamidi, Remco van der Hofstad, and Johan S. H. van Leeuwaarden. 2010. Scaling limits for critical inhomogeneous random graphs with finite third moments. Electron. J. Probab. 15, (2010), no. 54, 1682–1703.
[28] Shankar Bhamidi, Remco van der Hofstad, and Johan S. H. van Leeuwaarden. 2012. Novel scaling limits for critical inhomogeneous random graphs. Ann. Probab. 40, 6 (2012), 2299–2361. DOI:https://doi.org/10.1214/11-AOP680
[29] Shankar Bhamidi, Jimmy Jin, and Andrew Nobel. 2018. Change point detection in network models: Preferential attachment and long range dependence. Annals of Applied Probability 28, 1 (2018), 35–78. DOI:https://doi.org/10.1214/17-AAP1297
[30] Shankar Bhamidi, Danny Nam, Oanh Nguyen, and Allan Sly. 2019. Survival and extinction of epidemics on random graphs with general degrees. Submitted to Annals of Applied Probability (2019).
[31] Shankar Bhamidi and Sanchayan Sen. 2019. Geometry of the vacant set left by random walk on random graphs, wright’s constants, and critical random graphs with prescribed degrees. Accepted in Random Structures & Algorithms (2019).
[32] Shankar Bhamidi, Sanchayan Sen, and Xuan Wang. 2017. Continuum limit of critical inhomogeneous random graphs. Probability Theory and Related Fields 169, 1-2 (2017), 565–641. DOI:https://doi.org/10.1007/s00440-016-0737-x
[33] Shankar Bhamidi, J. Michael Steele, and Tauhid Zaman. 2015. Twitter event networks and the superstar model. Annals of Applied Probability 25, 5 (2015), 2462–2502. DOI:https://doi.org/10.1214/14-AAP1053
[34] S. Bhamidi, R. van der Hofstad, and G. Hooghiemstra. 2010. First passage percolation on random graphs with finite mean degrees. The Annals of Applied Probability 20, 5 (2010), 1907–1965.
[35] S. Bhamidi, R. van der Hofstad, and G. Hooghiemstra. 2010. Extreme value theory, poisson-dirichlet distributions, and first passage percolation on random networks. Advances in Applied Probability 42, 3 (2010), 706–738.
[36] S. Bhamidi, R. Rajagopal, and S. Roch. 2010. Network delay inference from additive metrics. Random Structures & Algorithms 37, 2 (2010), 176–203.
[37] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the internet topology. In ACM sigcomm computer communication review, 251–262.
[38] Mark He, Joseph Glasser, Shankar Bhamidi, and Nikhil Kaza. 2019. Intertemporal community detection in bikeshare networks. arXiv preprint arXiv:1906.04582 (2019).
[39] Mark He, Joseph Glasser, Nathaniel Pritchard, Shankar Bhamidi, and Nikhil Kaza. 2019. Demarcating geographic regions using community detection in commuting networks. arXiv preprint arXiv:1903.06029 (2019).
[40] John Palowitch, Shankar Bhamidi, and Andrew B. Nobel. 2017. Significance-based community detection in weighted networks. J. Mach. Learn. Res. 18, (2017), Paper No. 188, 48.
[41] Dan Shen, Haipeng Shen, Shankar Bhamidi, Yolanda Muñoz Maldonado, Yongdai Kim, and J. S. Marron. 2014. Functional data analysis of tree data objects. Journal of Computational and Graphical Statistics 23, 2 (2014), 418–438. DOI:https://doi.org/10.1080/10618600.2013.786943
[42] Paul E Stillman, James D Wilson, Matthew J Denny, Bruce A Desmarais, Shankar Bhamidi, Skyler J Cranmer, and Zhong-Lin Lu. 2017. Statistical modeling of the default mode brain network reveals a segregated highway structure. Scientific reports 7, 1 (2017), 11694.
[43] James D Wilson, Shankar Bhamidi, and Andrew B Nobel. 2013. Measuring the statistical significance of local connections in directed networks. NIPS Workshop on Frontiers od Network Analysis: Methods, Models and Applications (2013).
[44] James D Wilson, Matthew J Denny, Shankar Bhamidi, Skyler J Cranmer, and Bruce A Desmarais. 2017. Stochastic weighted graphs: Flexible model specification and simulation. Social Networks 49, (2017), 37–47.
[45] James D. Wilson, John Palowitch, Shankar Bhamidi, and Andrew B. Nobel. 2017. Community extraction in multilayer networks with heterogeneous community structure. J. Mach. Learn. Res. 18, (2017), Paper No. 149, 49.
[46] James D Wilson, Simi Wang, Peter J Mucha, Shankar Bhamidi, and Andrew B Nobel. 2013. A testing based extraction algorithm for identifying significant communities in networks. Under revision for the Annals of Applied Statistics (2013).