Centrality measures aim to indicate who is important in a network. Various notions of ‘being important’ give rise to different centrality measures. In this paper, we study how important the central vertices are for the connectivity structure of the network, by investigating how the removal of the most central vertices affects the number of connected components and the size of the giant component. We use local convergence techniques to identify the limiting number of connected components for locally converging graphs and centrality measures that depend on the vertex’s neighbourhood. For the size of the giant, we prove a general upper bound. For the matching lower bound, we specialise to the case of degree centrality on one of the most popular models in network science, the configuration model, for which we show that removal of the highest-degree vertices destroys the giant most.

We study competing first passage percolation on graphs generated by the configuration model with infinite-mean degrees. Initially, two uniformly chosen vertices are infected with a type 1 and type 2 infection, respectively, and the infection then spreads via nearest neighbors in the graph. The time it takes for the type 1 (resp. 2) infection to traverse an edge e is given by a random variable $X_1(e)$ (resp. $X_2(e)$) and, if the vertex at the other end of the edge is still uninfected, it then becomes type 1 (resp. 2) infected and immune to the other type. Assuming that the degrees follow a power-law distribution with exponent $\tau \in (1,2)$, we show that with high probability as the number of vertices tends to infinity, one of the infection types occupies all vertices except for the starting point of the other type. Moreover, both infections have a positive probability of winning regardless of the passage-time distribution. The result is also shown to hold for the erased configuration model, where self-loops are erased and multiple edges are merged, and when the degrees are conditioned to be smaller than $n^\alpha$ for some $\alpha\gt 0$.

We provide a general purpose result for the coupling of exploration processes of random graphs, both undirected and directed, with their local weak limits when this limit is a marked Galton–Watson process. This class includes in particular the configuration model and the family of inhomogeneous random graphs with rank-1 kernel. Vertices in the graph are allowed to have attributes on a general separable metric space and can potentially influence the construction of the graph itself. The coupling holds for any fixed depth of a breadth-first exploration process.

We study a stochastic compartmental susceptible–infected (SI) epidemic process on a configuration model random graph with a given degree distribution over a finite time interval. We split the population of graph vertices into two compartments, namely, S and I, denoting susceptible and infected vertices, respectively. In addition to the sizes of these two compartments, we keep track of the counts of SI-edges (those connecting a susceptible and an infected vertex) and SS-edges (those connecting two susceptible vertices). We describe the dynamical process in terms of these counts and present a functional central limit theorem (FCLT) for them as the number of vertices in the random graph grows to infinity. The FCLT asserts that the counts, when appropriately scaled, converge weakly to a continuous Gaussian vector semimartingale process in the space of vector-valued càdlàg functions endowed with the Skorokhod topology. We discuss applications of the FCLT in percolation theory and in modelling the spread of computer viruses. We also provide simulation results illustrating the FCLT for some common degree distributions.

An important problem in modeling networks is how to generate a randomly sampled graph with given degrees. A popular model is the configuration model, a network with assigned degrees and random connections. The erased configuration model is obtained when self-loops and multiple edges in the configuration model are removed. We prove an upper bound for the number of such erased edges for regularly-varying degree distributions with infinite variance, and use this result to prove central limit theorems for Pearson’s correlation coefficient and the clustering coefficient in the erased configuration model. Our results explain the structural correlations in the erased configuration model and show that removing edges leads to different scaling of the clustering coefficient. We prove that for the rank-1 inhomogeneous random graph, another null model that creates scale-free simple networks, the results for Pearson’s correlation coefficient as well as for the clustering coefficient are similar to the results for the erased configuration model.

We consider a dynamic network cascade process developed by Duncan Watts applied to a class of random networks, developed independently by Newman and Miller, which allows a specified amount of clustering (short loops). We adapt existing methods for locally tree-like networks to formulate an appropriate two-type branching process to describe the spread of a cascade started with a single active node and obtain a fixed-point equation to implicitly express the extinction probability of such a cascade. In so doing, we also recover a formula that has appeared in various forms in works by Hackett et al. and Miller which provides a threshold condition for certain extinction of the cascade. We find that clustering impedes cascade propagation for networks of low average degree by reducing the connectivity of the network, but for networks with high average degree, the presence of small cycles makes cascades more likely.

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, and the flooding time, which represents the time (weighted length) needed to reach all the vertices in the graph starting from a uniformly chosen vertex. Our result consists in describing the asymptotic behavior of the diameter and the flooding time, as the number of vertices n tends to infinity, in the case where the weight distribution G has an exponential tail behavior, and proving that this category of distributions is the largest possible for which the asymptotic behavior holds.

Recent work studying triadic closure in undirected graphs has drawn attention to the distinction between measures that focus on the “center” node of a wedge (i.e., length-2 path) versus measures that focus on the “initiator,” a distinction with considerable consequences. Existing measures in directed graphs, meanwhile, have all been center-focused. In this work, we propose a family of eight directed closure coefficients that measure the frequency of triadic closure in directed graphs from the perspective of the node initiating closure. The eight coefficients correspond to different labeled wedges, where the initiator and center nodes are labeled, and we observe dramatic empirical variation in these coefficients on real-world networks, even in cases when the induced directed triangles are isomorphic. To understand this phenomenon, we examine the theoretical behavior of our closure coefficients under a directed configuration model. Our analysis illustrates an underlying connection between the closure coefficients and moments of the joint in- and out-degree distributions of the network, offering an explanation of the observed asymmetries. We also use our directed closure coefficients as predictors in two machine learning tasks. We find interpretable models with AUC scores above 0.92 in class-balanced binary prediction, substantially outperforming models that use traditional center-focused measures.

We introduce a weighted configuration model graph, where edge weights correspond to the probability of infection in an epidemic on the graph. On these graphs, we study the development of a Susceptible–Infectious–Recovered epidemic using both Reed–Frost and Markovian settings. For the special case of having two different edge types, we determine the basic reproduction numberR0, the probability of a major outbreak, and the relative final size of a major outbreak. Results are compared with those for a calibrated unweighted graph. The degree distributions are based on both theoretical constructs and empirical network data. In addition, bivariate standard normal copulas are used to model the dependence between the degrees of the two edge types, allowing for modeling the correlation between edge types over a wide range. Among the results are that the weighted graph produces much richer results than the unweighted graph. Also, while R0 always increases with increasing correlation between the two degrees, this is not necessarily true for the probability of a major outbreak nor for the relative final size of a major outbreak. When using copulas we see that these can produce results that are similar to those of the empirical degree distributions, indicating that in some cases a copula is a viable alternative to using the full empirical data.

A large and sparse random graph with independent exponentially distributed link weights can be used to model the propagation of messages or diseases in a network with an unknown connectivity structure. In this article we study an extended setting where, in addition, the nodes of the graph are equipped with nonnegative random weights which are used to model the effect of boundary delays across paths in the network. Our main results provide approximative formulas for typical first passage times, typical flooding times, and maximum flooding times in the extended setting, over a time scale logarithmic with respect to the network size.

In this paper we consider the degree-wise effect of a second step for a random walk on a graph. We prove that under the configuration model, for any fixed degree sequence the probability of exceeding a given degree threshold is smaller after two steps than after one. This builds on recent work of Kramer et al. (2016) regarding the friendship paradox under random walks.

This paper studies the friendship paradox for weighted and directed networks, from a probabilistic perspective. We consolidate and extend recent results of Cao and Ross and Kramer, Cutler and Radcliffe, to weighted networks. Friendship paradox results for directed networks are given; connections to detailed balance are considered.

Random multigraphs with fixed degrees are obtained by the configuration model or by so called random stub matching. New combinatorial results are given for the global probability distribution of edge multiplicities and its marginal local distributions of loops and edges. The number of multigraphs on triads is determined for arbitrary degrees, and aggregated triads are shown to be useful for analyzing regular and almost regular multigraphs. Relationships between entropy and complexity are given and numerically illustrated for multigraphs with different number of vertices and specified average and variance for the degrees.

We prove nonuniversality results for first-passage percolation on the configuration model with independent and identically distributed (i.i.d.) degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviours are possible. When the weights are almost surely larger than a constant, the weight and number of edges in the graph grow proportionally to log log n, as for the graph distances. On the other hand, when the continuous-time branching process describing the first-passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the continuous-time processes started from the two sources. This nonuniversality is in sharp contrast to the setting where the degree sequence has a finite variance, Bhamidi et al. (2012).

Respondent-driven sampling (RDS) is frequently used when sampling from hidden populations. In RDS, sampled individuals pass on participation coupons to at most c of their acquaintances in the community (c = 3 being a common choice). If these individuals choose to participate, they in turn pass coupons on to their acquaintances, and so on. The process of recruiting is shown to behave like a new Reed–Frost-type network epidemic, in which 'becoming infected' corresponds to study participation. We calculate R0, the probability of a major 'outbreak', and the relative size of a major outbreak for c < ∞ in the limit of infinite population size and compare to the standard Reed–Frost epidemic. Our results indicate that c should often be chosen larger than in current practice.

Consider a random multigraph G* with given vertex degrees d1,…, dn, constructed by the configuration model. We give a new proof of the fact that, asymptotically for a sequence of such multigraphs with the number of edges the probability that the multigraph is simple stays away from 0 if and only if The new proof uses the method of moments, which makes it possible to use it in some applications concerning convergence in distribution. Corresponding results for bipartite graphs are included.

We study the array of point-to-point distances in random regular graphs equipped with exponential edge lengths. We consider the regime where the degree is kept fixed while the number of vertices tends to ∞. The marginal distribution of an individual entry is now well understood, thanks to the work of Bhamidi, van der Hofstad and Hooghiemstra (2010). The purpose of this note is to show that the whole array, suitably recentered, converges in the weak sense to an explicit infinite random array. Our proof consists in analyzing the invasion of the network by several mutually exclusive flows emanating from different sources and propagating simultaneously along the edges.

We show that in preferential attachment models with power-law exponent τ ∈ (2, 3) the distance between randomly chosen vertices in the giant component is asymptotically equal to (4 + o(1))log log N / (-log(τ − 2)), where N denotes the number of nodes. This is twice the value obtained for the configuration model with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.

We study first passage percolation (FPP) on the configuration model (CM) having power-law degrees with exponent τ ∈ [1, 2) and exponential edge weights. We derive the distributional limit of the minimal weight of a path between typical vertices in the network and the number of edges on the minimal-weight path, both of which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via construction of infinite limiting objects describing the FPP problem in the densely connected core of the network. We consider two separate cases, the original CM, in which each edge, regardless of its multiplicity, receives an independent exponential weight, and the erased CM, for which there is an independent exponential weight between any pair of direct neighbors. While the results are qualitatively similar, surprisingly, the limiting random variables are quite different. Our results imply that the flow carrying properties of the network are markedly different from either the mean-field setting or the locally tree-like setting, which occurs as τ > 2, and for which the hopcount between typical vertices scales as log n. In our setting the hopcount is tight and has an explicit limiting distribution, showing that information can be transferred remarkably quickly between different vertices in the network. This efficiency has a down side in that such networks are remarkably fragile to directed attacks. These results continue a general program by the authors to obtain a complete picture of how random disorder changes the inherent geometry of various random network models; see Aldous and Bhamidi (2010), Bhamidi (2008), and Bhamidi, van der Hofstad and Hooghiemstra (2009).