Abstract:
Consider the complete n-vertex graph whose edge-lengths are independent exponentially distributed random variables. Simultaneously for each pair of vertices, put a constant flow between them along the shortest path. Each edge gets some random total flow. In the $n \to \infty$ limit we find explicitly the empirical distribution of these edge-flows, suitably normalized.

Abstract:
We demonstrate the use of computational phylogenetic techniques to solve a central problem in inferential network monitoring. More precisely, we design a novel algorithm for multicast-based delay inference, i.e. the problem of reconstructing the topology and delay characteristics of a network from end-to-end delay measurements on network paths. Our inference algorithm is based on additive metric techniques widely used in phylogenetics. It runs in polynomial time and requires a sample of size only $\poly(\log n)$.

Abstract:
Exponential random graphs are used extensively in the sociology literature. This model seeks to incorporate in random graphs the notion of reciprocity, that is, the larger than expected number of triangles and other small subgraphs. Sampling from these distributions is crucial for parameter estimation hypothesis testing, and more generally for understanding basic features of the network model itself. In practice sampling is typically carried out using Markov chain Monte Carlo, in particular either the Glauber dynamics or the Metropolis-Hasting procedure. In this paper we characterize the high and low temperature regimes of the exponential random graph model. We establish that in the high temperature regime the mixing time of the Glauber dynamics is $\Theta(n^2 \log n)$, where $n$ is the number of vertices in the graph; in contrast, we show that in the low temperature regime the mixing is exponentially slow for any local Markov chain. Our results, moreover, give a rigorous basis for criticisms made of such models. In the high temperature regime, where sampling with MCMC is possible, we show that any finite collection of edges are asymptotically independent; thus, the model does not possess the desired reciprocity property, and is not appreciably different from the Erd\H{o}s-R\'enyi random graph.

Abstract:
We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees, we show that the empirical spectral distributions for each of a number of random tree models converge to a deterministic (model dependent) limit as the number of vertices goes to infinity. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain precise asymptotics on the mass assigned to zero by the empirical spectral measures via the connection with the cardinality of a maximal matching. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, non-negative random variables with finite expected value. We greatly extend a celebrated result obtained by Schwenk for the uniform random trees by showing that, under mild conditions, with probability converging to one, the spectrum of a realization is shared by at least one other tree. For the the linear preferential attachment model with parameter $a > -1$, we show that the suitably rescaled $k$ largest eigenvalues converge jointly.

Abstract:
Condensation phenomenon is often observed in social networks such as Twitter where one "superstar" vertex gains a positive fraction of the edges, while the remaining empirical degree distribution still exhibits a power law tail. We formulate a mathematically tractable model for this phenomenon that provides a better fit to empirical data than the standard preferential attachment model across an array of networks observed in Twitter. Using embeddings in an equivalent continuous time version of the process, and adapting techniques from the stable age-distribution theory of branching processes, we prove limit results for the proportion of edges that condense around the superstar, the degree distribution of the remaining vertices, maximal nonsuperstar degree asymptotics and height of these random trees in the large network limit.

Abstract:
Bounded-size rules are dynamic random graph processes which incorporate limited choice along with randomness in the evolution of the system. One starts with the empty graph and at each stage two edges are chosen uniformly at random. One of the two edges is then placed into the system according to a decision rule based on the sizes of the components containing the four vertices. For bounded-size rules, all components of size greater than some fixed $K\geq 1$ are accorded the same treatment. Writing $\BS(t)$ for the state of the system with nt/2 edges, Spencer and Wormald proved that for such rules, there exists a critical time t_c such that when t< t_c the size of the largest component is of order $\log{n}$ while for $t> t_c$, the size of the largest component is of order $n$. In this work we obtain upper bounds (that hold with high probability) of order $n^{2\gamma} \log ^4 n$, on the size of the largest component, at time instants $t_n = t_c-n^{-\gamma}$, where $\gamma\in (0,1/4)$. This result for the barely subcritical regime forms a key ingredient in the study undertaken in \cite{amc-2012}, of the asymptotic dynamic behavior of the process describing the vector of component sizes and associated complexity of the components for such random graph models in the critical scaling window. The proof uses a coupling of BSR processes with a certain family of inhomogeneous random graphs with vertices in the type space $\Rbold_+\times \cD([0,\infty):\NNN_0)$ where $\cD([0,\infty):\NNN_0)$ is the Skorohod $D$-space of functions that are right continuous and have left limits equipped with the usual Skorohod topology. The coupling construction also gives an alternative characterization (than the usual explosion time of the susceptibility function) of the critical time $t_c$ for the emergence of the giant component in terms of the operator norm of integral operators on certain $L^2$ spaces.

Abstract:
Random graph models with limited choice have been studied extensively with the goal of understanding the mechanism of the emergence of the giant component. One of the standard models are the Achlioptas random graph processes on a fixed set of $n$ vertices. Here at each step, one chooses two edges uniformly at random and then decides which one to add to the existing configuration according to some criterion. An important class of such rules are the bounded-size rules where for a fixed $K\geq 1$, all components of size greater than $K$ are treated equally. While a great deal of work has gone into analyzing the subcritical and supercritical regimes, the nature of the critical scaling window, the size and complexity (deviation from trees) of the components in the critical regime and nature of the merging dynamics has not been well understood. In this work we study such questions for general bounded-size rules. Our first main contribution is the construction of an extension of Aldous's standard multiplicative coalescent process which describes the asymptotic evolution of the vector of sizes and surplus of all components. We show that this process, referred to as the standard augmented multiplicative coalescent (AMC) is `nearly' Feller with a suitable topology on the state space. Our second main result proves the convergence of suitably scaled component size and surplus vector, for any bounded-size rule, to the standard AMC. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from [8], on the size of the largest component in the barely subcritical regime.

Abstract:
We consider the complete graph $\cK_n$ on $n$ vertices with exponential mean $n$ edge lengths. Writing $C_{ij}$ for the weight of the smallest-weight path between vertex $i,j\in [n]$, Janson showed that $\max_{i,j\in [n]} C_{ij}/\log{n}$ converges in probability to 3. We extend this result by showing that $\max_{i,j\in [n]} C_{ij} - 3\log{n}$ converges in distribution to a limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erd\H{o}s-R\'enyi random graph in work by Riordan and Wormald.

Abstract:
Motivated by applications, the last few years have witnessed tremendous interest in understanding the structure as well as the behavior of dynamics for inhomogeneous random graph models. In this study we analyze the maximal components at criticality of one famous class of such models, the rank-one inhomogeneous random graph model. Viewing these components as measured random metric spaces, under finite moment assumptions for the weight distribution, we show that the components in the critical scaling window with distances scaled by $n^{-1/3}$ converge in the Gromov-Haussdorf-Prokhorov metric to rescaled versions of the limit objects identified for the Erd\H{o}s-R\'enyi random graph components at criticality Addario-Berry, Broutin and Goldschmidt (2012). A key step is the construction of connected components of the random graph through an appropriate tilt of a famous class of random trees called $\mathbf{p}$-trees (studied previously by Aldous, Miermont and Pitman (2004) and by Camarri and Pitman (2000)). This is the first step in rigorously understanding the scaling limits of objects such as the Minimal spanning tree and other strong disorder models from statistical physics (see Braunstein et al., 2003) for such graph models. By asymptotic equivalence (Janson, 2010), the same results are true for the Chung-Lu model and the Britton-Deijfen-Lof model. A crucial ingredient of the proof of independent interest is tail bounds for the height of $\mathbf{p}$-trees. The techniques developed in this paper form the main technical bedrock for proving continuum scaling limits in the critical regime for a wide array of other random graph models (Bhamidi, Broutin, Sen and Wang, 2014) including the configuration model and inhomogeneous random graphs with general kernels which were introduced by Bollobas, Janson and Riordan (2007).

Abstract:
In the recent past, there has been a concerted effort to develop mathematical models for real-world networks and to analyze various dynamics on these models. One particular problem of significant importance is to understand the effect of random edge lengths or costs on the geometry and flow transporting properties of the network. Two different regimes are of great interest, the weak disorder regime where optimality of a path is determined by the sum of edge weights on the path and the strong disorder regime where optimality of a path is determined by the maximal edge weight on the path. In the context of the stochastic mean-field model of distance, we provide the first mathematically tractable model of weak disorder and show that no transition occurs at finite temperature. Indeed, we show that for every finite temperature, the number of edges on the minimal weight path (i.e., the hopcount) is $\Theta(\log{n})$ and satisfies a central limit theorem with asymptotic means and variances of order $\Theta(\log{n})$, with limiting constants expressible in terms of the Malthusian rate of growth and the mean of the stable-age distribution of an associated continuous-time branching process. More precisely, we take independent and identically distributed edge weights with distribution $E^s$ for some parameter $s>0$, where $E$ is an exponential random variable with mean 1. Then the asymptotic mean and variance of the central limit theorem for the hopcount are $s\log{n}$ and $s^2\log{n}$, respectively. We also find limiting distributional asymptotics for the value of the minimal weight path in terms of extreme value distributions and martingale limits of branching processes.