Explore the vast range of titles available.

We consider models of evolving networks Gn:n≥0 modulated by two parameters: an attachment function f:N0→R+ and a (possibly random) attachment sequence mi:i≥1. Starting with a single vertex, at each discrete step i≥1 a new vertex vi enters the system with mi≥1 edges which it sequentially connects to a pre-existing vertex v∈Gi-1 with probability proportional to f(degree(v)). We consider the problem of emergence of persistent hubs: existence of a finite (a.s.) time n∗ such that for all n≥n∗ the identity of the maximal degree vertex (or in general the K largest degree vertices for K≥1) does not change. We obtain general conditions on f and mi:i≥1 under which a persistent hub emerges, and also those under which a persistent hub fails to emerge. In the case of lack of persistence, for the specific case of trees (mi≡1 for all i), we derive asymptotics for the maximal degree and the index of the maximal deg ree vertex (time at which the vertex with current maximal degree entered the system) to understand the movement of the maximal degree vertex as the network evolves. A key role in the analysis is played by an inverse rate weighted martingale constructed from a continuous time embedding of the discrete time model. Asymptotics for this martingale, including concentration inequalities and moderate deviations form the technical foundations for the main results.

One major open conjecture in the area of critical random graphs, formulated by statistical physicists, and supported by a large amount of numerical evidence over the last decade (Braunstein et al. in Phys Rev Lett 91(16):168701, 2003; Wu et al. in Phys Rev Lett 96(14):148702, 2006; Braunstein et al. Int J Bifurc Chaos 17(07):2215–2255, 2007; Chen et al. in Phys Rev Lett 96(6):068702, 2006) is as follows: for a wide array of random graph models with degree exponent τ∈(3,4), distances between typical points both within maximal components in the critical regime as well as on the minimal spanning tree on the giant component in the supercritical regime scale like n(τ-3)/(τ-1). In this paper we study the metric space structure of maximal components of the multiplicative coalescent, in the regime where the sizes converge to excursions of Lévy processes “without replacement” (Aldous and Limic Electron in J Probab 3(3):59, 1998), yielding a completely new class of limiting random metric spaces. A by-product of the analysis yields the continuum scaling limit of one fundamental class of random graph models with degree exponent τ∈(3,4) where edges are rescaled by n-(τ-3)/(τ-1) yielding the first rigorous proof of the above conjecture. The limits in this case are compact “tree-like” random fractals with a dense collection of hubs (infinite degree vertices), a finite number of which are identified with leaves to form shortcuts. In a special case, we show that the Minkowski dimension of the limiting spaces equal (τ-2)/(τ-3) a.s., in stark contrast to the Erdős-Rényi scaling limit whose Minkowski dimension is 2 a.s. It is generally believed that dynamic versions of a number of fundamental random graph models, as one moves from the barely subcritical to the critical regime can be approximated by the multiplicative coalescent. In work in progress, the general theory developed in this paper is used to prove analogous limit results for other random graph models with degree exponent τ∈(3,4). Our proof makes crucial use of inhomogeneous continuum random trees (ICRT), which have previously arisen in the study of the entrance boundary of the additive coalescent. We show that tilted versions of the same objects using the associated mass measure, describe connectivity properties of the multiplicative coalescent. Since convergence of height processes of corresponding approximating p-trees is not known, we use general methodology in Athreya et al. (2014) and develop novel techniques relying on first showing convergence in the Gromov-weak topology and then extending this to Gromov–Hausdorff–Prokhorov convergence by proving a global lower mass-bound.

We develop a method to identify statistically significant communities in a weighted network with a high proportion of self-looping weights. We use this method to find overlapping agglomerations of U.S. counties by representing inter-county commuting as a weighted network. We identify three types of communities; non-nodal, nodal and monads, which correspond to different types of regions. The results suggest that traditional regional delineations that rely on ad hoc thresholds do not account for important and pervasive connections that extend far beyond expected metropolitan boundaries or megaregions.

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 ≥ 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. This result is new even for the classical Erdős–Rényi setting. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from Bhamidi et al. (The barely subcritical regime. Arxiv preprint, 2012 ) on the size of the largest component in the barely subcritical regime.

We investigate the statistical learning of nodal attribute functionals in homophily networks using random walks. Attributes can be discrete or continuous. A generalization of various existing canonical models, based on preferential attachment is studied (model class P ), where new nodes form connections dependent on both their attribute values and popularity as measured by degree. An associated model class U is described, which is amenable to theoretical analysis and gives access to asymptotics of a host of functionals of interest. Settings where asymptotics for model class U transfer over to model class P through the phenomenon of resolvability are analyzed. For the statistical learning, we consider several canonical attribute agnostic sampling schemes such as Metropolis-Hasting random walk, versions of node2vec (Grover and Leskovec, 2016) that incorporate both classical random walk and non-backtracking propensities and propose new variants which use attribute information in addition to topological information to explore the network. Estimators for learning the attribute distribution, degree distribution for an attribute type and homophily measures are proposed. The performance of such statistical learning framework is studied on both synthetic networks (model class P ) and real world systems, and its dependence on the network topology, degree of homophily or absence thereof, (un)balanced attributes, is assessed.

We investigate the functional organization of the Default Mode Network (DMN) – an important subnetwork within the brain associated with a wide range of higher-order cognitive functions. While past work has shown the whole-brain network of functional connectivity follows small-world organizational principles, subnetwork structure is less well understood. Current statistical tools, however, are not suited to quantifying the operating characteristics of functional networks as they often require threshold censoring of information and do not allow for inferential testing of the role that local processes play in determining network structure. Here, we develop the correlation Generalized Exponential Random Graph Model (cGERGM) – a statistical network model that uses local processes to capture the emergent structural properties of correlation networks without loss of information. Examining the DMN with the cGERGM, we show that, rather than demonstrating small-world properties, the DMN appears to be organized according to principles of a segregated highway – suggesting it is optimized for function-specific coordination between brain regions as opposed to information integration across the DMN. We further validate our findings through assessing the power and accuracy of the cGERGM on a testbed of simulated networks representing various commonly observed brain architectures.

In this paper we explore first passage percolation (FPP) on the Erdős–Rényi random graph Gn(pn), where we assign independent random weights, having an exponential distribution with rate 1, to the edges. In the sparse regime, i.e., when npn → λ > 1, we find refined asymptotics both for the minimal weight of the path between uniformly chosen vertices in the giant component, as well as for the hopcount (i.e., the number of edges) on this minimal weight path. More precisely, we prove a central limit theorem for the hopcount, with asymptotic mean and variance both equal to (λ log n)/(λ − 1). Furthermore, we prove that the minimal weight centred by (log n)/(λ − 1) converges in distribution. We also investigate the dense regime, where npn → ∞. We find that although the base graph is ultra-small (meaning that graph distances between uniformly chosen vertices are o(log n)), attaching random edge weights changes the geometry of the network completely. Indeed, the hopcount Hn satisfies the universality property that whatever the value of pn, Hn/log n → 1 in probability and, more precisely, (Hn − βn log n)/, where βn = λn/(λn − 1), has a limiting standard normal distribution. The constant βn can be replaced by 1 precisely when λn ≫ , a case that has appeared in the literature (under stronger conditions on λn) in [4, 13]. We also find lower bounds for the maximum, over all pairs of vertices, of the optimal weight and hopcount. This paper continues the investigation of FPP initiated in [4] and [5]. Compared to the setting on the configuration model studied in [5], the proofs presented here are much simpler due to a direct relation between FPP on the Erdős–Rényi random graph and thinned continuous-time branching processes.

Co-evolving network models, wherein dynamics such as random walks on the network influence the evolution of the network structure, which in turn influences the dynamics, are of interest in a range of domains. While much of the literature in this area is currently supported by numerics, providing evidence for fascinating conjectures and phase transitions, proving rigorous results has been quite challenging. We propose a general class of co-evolving tree network models driven by local exploration, started from a single vertex called the root. New vertices attach to the current network via randomly sampling a vertex and then exploring the graph for a random number of steps in the direction of the root, connecting to the terminal vertex. Specific choices of the exploration step distribution lead to the well-studied affine preferential attachment and uniform attachment models, as well as less well understood dynamic network models with global attachment functionals such as PageRank scores (Chebolu and Melsted, in: SODA, 2008). We obtain local weak limits for such networks and use them to derive asymptotics for the limiting empirical degree and PageRank distribution. We also quantify asymptotics for the degree and PageRank of fixed vertices, including the root, and the height of the network. Two distinct regimes are seen to emerge, based on the expected exploration distance of incoming vertices, which we call the ‘fringe’ and ‘non-fringe’ regimes. These regimes are shown to exhibit different qualitative and quantitative properties. In particular, networks in the non-fringe regime undergo ‘condensation’ where the root degree grows at the same rate as the network size. Networks in the fringe regime do not exhibit condensation. Further, non-trivial phase transition phenomena are shown to arise for: (a) height asymptotics in the non-fringe regime, driven by the subtle competition between the condensation at the root and network growth; (b) PageRank distribution in the fringe regime, connecting to the well known power-law hypothesis. In the process, we develop a general set of techniques involving local limits, infinite-dimensional urn models, related multitype branching processes and corresponding Perron–Frobenius theory, branching random walks, and in particular relating tail exponents of various functionals to the scaling exponents of quasi-stationary distributions of associated random walks. These techniques are expected to shed light on a variety of other co-evolving network models.

In this paper we establish the necessary and sufficient criterion for the contact process on Galton–Watson trees (resp., random graphs) to exhibit the phase of extinction (resp., short survival). We prove that the survival threshold λ₁ for a Galton–Watson tree is strictly positive if and only if its offspring distribution ξ has an exponential tail, that is, 𝔼e cξ < ∞ for some c > 0, settling a conjecture by Huang and Durrett (2018). On the random graph with degree distribution μ, we show that if μ has an exponential tail, then for small enough λ the contact process with the all-infected initial condition survives for n 1+o(1)-time whp (short survival), while for large enough λ it runs over e Θ(n)-time whp (long survival). When μ is subexponential, we prove that the contact process whp displays long survival for any fixed λ > 0.

The last few years have witnessed tremendous interest in understanding the structure as well as the behavior of dynamics for inhomogeneous random graph models to gain insight into real-world systems. In this study we analyze the maximal components at criticality of one famous class of such models, the rank-one inhomogeneous random graph model (Norros and Reittu, Adv Appl Probab 38(1):59–75, 2006 ; Bollobás et al., Random Struct Algorithms 31(1):3–122, 2007 , Section 16.4). 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ős–Rényi random graph components at criticality in Addario-Berry et al. (Probab. Theory Related Fields, 152(3–4):367–406, 2012 ). A key step is the construction of connected components of the random graph through an appropriate tilt of a fundamental class of random trees called p -trees (Camarri and Pitman, Electron. J. Probab 5(2):1–18, 2000 ; Aldous et al., Probab Theory Related Fields 129(2):182–218, 2004 ). 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 (Braunstein et al., Phys Rev Lett 91(16):168701, 2003 ) for such graph models. By asymptotic equivalence (Janson, Random Struct Algorithms 36(1):26–45, 2010 ), the same results are true for the Chung–Lu model (Chung and Lu, Proc Natl Acad Sci 99(25):15879–15882, 2002 ; Chung and Lu, Ann Combin 6(2):125–145, 2002 ; Chung and Lu, Complex graphs and networks, 2006 ) and the Britton–Deijfen–Martin–Löf model (Britton et al., J Stat Phys 124(6):1377–1397, 2006 ). A crucial ingredient of the proof of independent interest are tail bounds for the height of p -trees. The techniques developed in this paper form the main technical bedrock for the general program developed in Bhamidi et al. (Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős–Rényi random graph. arXiv preprint, 2014 ) for proving universality of the continuum scaling limits in the critical regime for a wide array of other random graph models including the configuration model and inhomogeneous random graphs with general kernels (Bollobás et al., Random Struct Algorithms 31(1):3–122, 2007 ).