Sharpest possible clustering bounds using robust random graph analysis.

Complex network theory crucially depends on the assumptions made about the degree distribution, while fitting degree distributions to network data is challenging, in particular for scale-free networks with power-law degrees. We present a robust assessment of complex networks that does not depend on the entire degree distribution, but only on its mean, range, and dispersion: summary statistics that are easy to obtain for most real-world networks. By solving several semi-infinite linear programs, we obtain tight (the sharpest possible) bounds for correlation and clustering measures, for all networks with degree distributions that share the same summary statistics. We identify various extremal random graphs that attain these tight bounds as the graphs with specific three-point degree distributions. We leverage the tight bounds to obtain robust laws that explain how degree-degree correlations and local clustering evolve as a function of node degrees and network size. These robust laws indicate that power-law networks with diverging variance are among the most extreme networks in terms of correlation and clustering, building a further theoretical foundation for the widely reported scale-free network phenomena such as correlation and clustering decay.

Robust subgraph counting with distribution-free random graph analysis.

Subgraphs such as cliques, loops, and stars play a crucial role in real-world networks. Random graph models can provide estimates for how often certain subgraphs appear, which can be tested against real-world networks. These estimated subgraph counts, however, crucially depend on the assumed degree distribution. Fitting a degree distribution to network data is challenging, in particular, for scale-free networks with power-law degrees. Therefore, in this paper we develop robust subgraph counts that do not depend on the entire degree distribution but only on its mean and mean absolute deviation (MAD), summary statistics that are easy to obtain for most real-world networks. By solving an optimization problem, we provide tight (the sharpest possible) bounds for the subgraph counts, for all possible subgraphs, and for all networks with degree distributions that share the same mean and MAD. We identify the extremal random graph that attains these tight bounds as the graph with a specific three-point degree distribution. We leverage the bounds on the maximal subgraph counts to obtain robust scaling laws for how the number of subgraphs grows as a function of the network size. The scaling laws indicate that sparse power-law networks are not the most extreme networks in terms of subgraph counts but dense power-law networks are. The robust bounds are also shown to hold for several real-world data sets.

Variational principle for scale-free network motifs.

For scale-free networks with degrees following a power law with an exponent τ ∈ (2, 3), the structures of motifs (small subgraphs) are not yet well understood. We introduce a method designed to identify the dominant structure of any given motif as the solution of an optimization problem. The unique optimizer describes the degrees of the vertices that together span the most likely motif, resulting in explicit asymptotic formulas for the motif count and its fluctuations. We then classify all motifs into two categories: motifs with small and large fluctuations.

Triadic Closure in Configuration Models with Unbounded Degree Fluctuations.

The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for k = Ω ( n ) settles on a power law c ( k ) ∼ n 5 - 2 τ k - 2 ( 3 - τ ) with τ ∈ ( 2 , 3 ) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.

Robust heavy-traffic approximations for service systems facing overdispersed demand.

Arrival processes to service systems often display fluctuations that are larger than anticipated under the Poisson assumption, a phenomenon that is referred to as overdispersion. Motivated by this, we analyze a class of discrete-time stochastic models for which we derive heavy-traffic approximations that are scalable in the system size. Subsequently, we show how this leads to novel capacity sizing rules that acknowledge the presence of overdispersion. This, in turn, leads to robust approximations for performance characteristics of systems that are of moderate size and/or may not operate in heavy traffic.

Cluster Tails for Critical Power-Law Inhomogeneous Random Graphs.

Recently, the scaling limit of cluster sizes for critical inhomogeneous random graphs of rank-1 type having finite variance but infinite third moment degrees was obtained in Bhamidi et al. (Ann Probab 40:2299-2361, 2012). It was proved that when the degrees obey a power law with exponent τ ∈ ( 3 , 4 ) , the sequence of clusters ordered in decreasing size and multiplied through by n - ( τ - 2 ) / ( τ - 1 ) converges as n → ∞ to a sequence of decreasing non-degenerate random variables. Here, we study the tails of the limit of the rescaled largest cluster, i.e., the probability that the scaling limit of the largest cluster takes a large value u, as a function of u. This extends a related result of Pittel (J Combin Theory Ser B 82(2):237-269, 2001) for the Erdos-Rényi random graph to the setting of rank-1 inhomogeneous random graphs with infinite third moment degrees. We make use of delicate large deviations and weak convergence arguments.

Local clustering in scale-free networks with hidden variables.

We investigate the presence of triangles in a class of correlated random graphs in which hidden variables determine the pairwise connections between vertices. The class rules out self-loops and multiple edges. We focus on the regime where the hidden variables follow a power law with exponent τ∈(2,3), so that the degrees have infinite variance. The natural cutoff h_{c} characterizes the largest degrees in the hidden variable models, and a structural cutoff h_{s} introduces negative degree correlations (disassortative mixing) due to the infinite-variance degrees. We show that local clustering decreases with the hidden variable (or degree). We also determine how the average clustering coefficient C scales with the network size N, as a function of h_{s} and h_{c}. For scale-free networks with exponent 2<τ<3 and the default choices h_{s}∼N^{1/2} and h_{c}∼N^{1/(τ-1)} this gives C∼N^{2-τ}lnN for the universality class at hand. We characterize the extremely slow decay of C when τ≈2 and show that for τ=2.1, say, clustering starts to vanish only for networks as large as N=10^{9}.

Clustering spectrum of scale-free networks.

Real-world networks often have power-law degrees and scale-free properties, such as ultrasmall distances and ultrafast information spreading. In this paper, we study a third universal property: three-point correlations that suppress the creation of triangles and signal the presence of hierarchy. We quantify this property in terms of c[over ¯](k), the probability that two neighbors of a degree-k node are neighbors themselves. We investigate how the clustering spectrum k↦c[over ¯](k) scales with k in the hidden-variable model and show that c[over ¯](k) follows a universal curve that consists of three k ranges where c[over ¯](k) remains flat, starts declining, and eventually settles on a power-law c[over ¯](k)∼k^{-α} with α depending on the power law of the degree distribution. We test these results against ten contemporary real-world networks and explain analytically why the universal curve properties only reveal themselves in large networks.

Power-law relations in random networks with communities.

Most random graph models are locally tree-like-do not contain short cycles-rendering them unfit for modeling networks with a community structure. We introduce the hierarchical configuration model (HCM), a generalization of the configuration model that includes community structures, while properties such as the size of the giant component, and the size of the giant percolating cluster under bond percolation can still be derived analytically. Viewing real-world networks as realizations of HCM, we observe two previously undiscovered power-law relations: between the number of edges inside a community and the community sizes, and between the number of edges going out of a community and the community sizes. We also relate the power-law exponent τ of the degree distribution with the power-law exponent of the community-size distribution γ. In the case of extremely dense communities (e.g., complete graphs), this relation takes the simple form τ=γ-1.

Epidemic spreading on complex networks with community structures.

Many real-world networks display a community structure. We study two random graph models that create a network with similar community structure as a given network. One model preserves the exact community structure of the original network, while the other model only preserves the set of communities and the vertex degrees. These models show that community structure is an important determinant of the behavior of percolation processes on networks, such as information diffusion or virus spreading: the community structure can both enforce as well as inhibit diffusion processes. Our models further show that it is the mesoscopic set of communities that matters. The exact internal structures of communities barely influence the behavior of percolation processes across networks. This insensitivity is likely due to the relative denseness of the communities.

Transient analysis of the Erlang A model.

We consider the Erlang A model, or [Formula: see text] queue, with Poisson arrivals, exponential service times, and m parallel servers, and the property that waiting customers abandon the queue after an exponential time. The queue length process is in this case a birth-death process, for which we obtain explicit expressions for the Laplace transforms of the time-dependent distribution and the first passage time. These two transient characteristics were generally presumed to be intractable. Solving for the Laplace transforms involves using Green's functions and contour integrals related to hypergeometric functions. Our results are specialized to the [Formula: see text] queue, the M / M / m queue, and the M / M / m / m loss model. We also obtain some corresponding results for diffusion approximations to these models.