Search

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(k), the probability that two neighbors of a degree-k node are neighbors themselves. We investigate how the clustering spectrum k ↦ c(k) scales with k in the hidden-variable model and show that c(k) follows a universal curve that consists of three k ranges where c(k) remains flat, starts declining, and eventually settles on a power-law c(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. [ABSTRACT FROM AUTHOR]

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 hc characterizes the largest degrees in the hidden variable models, and a structural cutoff hs 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 hs and hc. For scale-free networks with exponent 2 <τ<3 and the default choices hs~N1/2 and hc~N1/(τ-1) this gives C~N2-τ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=109. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider spin models on complex networks frequently used to model social and technological systems. We study the annealed ferromagnetic Ising model for random networks with either independent edges (Erdős-Rényi) or prescribed degree distributions (configuration model). Contrary to many physical models, the annealed setting is poorly understood and behaves quite differently than the quenched system. In annealed networks with a fluctuating number of edges, the Ising model changes the degree distribution, an aspect previously ignored. For random networks with Poissonian degrees, this gives rise to three distinct annealed critical temperatures depending on the precise model choice, only one of which reproduces the quenched one. In particular, two of these annealed critical temperatures are finite even when the quenched one is infinite because then the annealed graph creates a giant component for all sufficiently small temperatures. We see that the critical exponents in the configuration model with deterministic degrees are the same as the quenched ones, which are the mean-field exponents if the degree distribution has finite fourth moment and power-law-dependent critical exponents otherwise. Remarkably, the annealing for the configuration model with random independent and identically distributed degrees washes away the universality class with power-law critical exponents.