Degree-dependent network growth: From preferential attachment to explosive percolation

We present a simple model of network growth and solve it by writing down the dynamic equations for its macroscopic characteristics like the degree distribution and degree correlations. This allows us to study carefully the percolation transition using a generating functions theory. The model considers a network with a fixed number of nodes wherein links are introduced using degree-dependent linking probabilities $p_k$. To illustrate the techniques and support our findings using Monte-Carlo simulations, we introduce the exemplary linking rule $p_k$ proportional to $k^{-alpha}$, with $alpha$ between -1 and plus infinity. This parameter may be used to interpolate between different regimes. For negative $alpha$, links are most likely attached to high-degree nodes. On the other hand, in case $alpha>0$, nodes with low degrees are connected and the model asymptotically approaches a process undergoing explosive percolation.

Percolation on bipartite scale-free networks

Recent studies introduced biased (degree-dependent) edge percolation as a model for failures in real-life systems. In this work, such process is applied to networks consisting of two types of nodes with edges running only between nodes of unlike type. Such bipartite graphs appear in many social networks, for instance in affiliation networks and in sexual contact networks in which both types of nodes show the scale-free characteristic for the degree distribution. During the depreciation process, an edge between nodes with degrees k and q is retained with probability proportional to (kq)^(-alpha), where alpha is positive so that links between hubs are more prone to failure. The removal process is studied analytically by introducing a generating functions theory. We deduce exact self-consistent equations describing the system at a macroscopic level and discuss the percolation transition. Critical exponents are obtained by exploiting the Fortuin-Kasteleyn construction which provides a link between our model and a limit of the Potts model.

Biased Percolation on Scale-free Networks

Biased (degree-dependent) percolation was recently shown to provide new strategies for turning robust networks fragile and vice versa. Here we present more detailed results for biased edge percolation on scale-free networks. We assume a network in which the probability for an edge between nodes $i$ and $j$ to be retained is proportional to $(k_ik_j)^{-alpha}$ with $k_i$ and $k_j$ the degrees of the nodes. We discuss two methods of network reconstruction, sequential and simultaneous, and investigate their properties by analytical and numerical means. The system is examined away from the percolation transition, where the size of the giant cluster is obtained, and close to the transition, where nonuniversal critical exponents are extracted using the generating functions method. The theory is found to agree quite well with simulations. By introducing an extension of the Fortuin-Kasteleyn construction, we find that biased percolation is well described by the $qto 1$ limit of the $q$-state Potts model with inhomogeneous couplings.