Directed hybrid random networks mixing preferential attachment with uniform attachment mechanisms

Annals of the Institute of Statistical Mathematics - Motivated by the complexity of network data, we propose a directed hybrid random network that mixes preferential attachment (PA) rules with...     

A preferential attachment model with Poisson growth for scale-free networks

We propose a scale-free network model with a tunable power-law exponent. The Poisson growth model, as we call it, is an offshoot of the celebrated model of Barabási and Albert where a network is generated iteratively from a small seed network; at each step a node is added together with a number of incident edges preferentially attached to nodes already in the network. A key feature of our model is that the number of edges added at each step is a random variable with Poisson distribution, and, unlike the Barabási–Albert model where this quantity is fixed, it can generate any network. Our model is motivated by an application in Bayesian inference implemented as Markov chain Monte Carlo to estimate a network; for this purpose, we also give a formula for the probability of a network under our model.     

Local clustering coefficients in preferential attachment models

The local clustering coefficients of preferential attachment models are analyzed. Previously, a general approach to preferential attachment was proposed (the PA-class was introduced); it was shown that the degree distribution in all models of the PA-class obeys a power law. The global clustering coefficient was also analyzed, and a lower bound for the mean local clustering coefficient was found. In the paper, new results are obtained by analyzing the local clustering coefficients of models of the PA-class. Namely, the behavior of the mean value C ₂(n, d) of local clustering over vertices of degree d is studied.     

Small subgraphs of random regular graphs

The main aim of this short paper is to answer the following question. Given a fixed graph H, for which values of the degree d does a random d-regular graph on n vertices contain a copy of H with probability close to one?     

Asymmetry and structural information in preferential attachment graphs

Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas Erd?s‐Rényi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with m edges is added, exhibit any symmetry. In recent work it was proved that preferential attachment graphs are symmetric for m = 1, and there is some nonnegligible probability of symmetry for m = 2. It was conjectured that these graphs are asymmetric when m ≥ 3. We settle this conjecture in the affirmative, then use it to estimate the structural entropy of the model. To do this, we also give bounds on the number of ways that the given graph structure could have arisen by preferential attachment. These results have further implications for information theoretic problems of interest on preferential attachment graphs.     

General results on preferential attachment and clustering coefficient

This is a review paper that covers some recent results on the behavior of the clustering coefficient in preferential attachment networks and scale-free networks in general. The paper focuses on general approaches to network science. In other words, instead of discussing different fully specified random graph models, we describe some generic results which hold for classes of models. Namely, we first discuss a generalized class of preferential attachment models which includes many classical models. It turns out that some properties can be analyzed for the whole class without specifying the model. Such properties are the degree distribution and the global and average local clustering coefficients. Finally, we discuss some surprising results on the behavior of the global clustering coefficient in scale-free networks. Here we do not assume any underlying model.     

A preferential attachment model with random initial degrees

In this paper, a random graph process {G(t)} _t≥1 is studied and its degree sequence is analyzed. Let {W _t } _t≥1 be an i.i.d. sequence. The graph process is defined so that, at each integer time t, a new vertex with W _t edges attached to it, is added to the graph. The new edges added at time t are then preferentially connected to older vertices, i.e., conditionally on G(t-1), the probability that a given edge of vertex t is connected to vertex i is proportional to d _i (t-1)+δ, where d _i (t-1) is the degree of vertex i at time t-1, independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent τ=min{τ_W,τ_P}, where τ_W is the power-law exponent of the initial degrees {W _t } _t≥1 and τ_P the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze.     

Fluctuations in a general preferential attachment model via Stein's method

We consider a class of dynamic random graphs known as preferential attachment models, where the probability that a new vertex connects to an older vertex is proportional to a sublinear function of the indegree of the older vertex at that time. It is well known that the distribution of a uniformly chosen vertex converges to a limiting distribution. Depending on the parameters, the tail of the limiting distribution may behave like a power law or a stretched exponential. Using Stein's method we provide rates of convergence to zero of the total variation distance between the finite distribution and its limit. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.     

Perfect matchings and Hamiltonian cycles in the preferential attachment model

In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with m random vertices selected with probabilities proportional to their current degrees. (Constant m is the only parameter of the model.) We prove that if , then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that . One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are “older” (ie, are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting—sometimes called uniform attachment—in which vertices are added one by one and each vertex connects to m older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version.     

Weighted distances in scale‐free preferential attachment models

We study three preferential attachment models where the parameters are such that the asymptotic degree distribution has infinite variance. Every edge is equipped with a nonnegative i.i.d. weight. We study the weighted distance between two vertices chosen uniformly at random, the typical weighted distance, and the number of edges on this path, the typical hopcount. We prove that there are precisely two universality classes of weight distributions, called the explosive and conservative class. In the explosive class, we show that the typical weighted distance converges in distribution to the sum of two i.i.d. finite random variables. In the conservative class, we prove that the typical weighted distance tends to infinity, and we give an explicit expression for the main growth term, as well as for the hopcount. Under a mild assumption on the weight distribution the fluctuations around the main term are tight.     

Condensation in preferential attachment models with location‐based choice

We introduce a model of a preferential attachment based random graph which extends the family of models in which condensation phenomena can occur. Each vertex has an associated uniform random variable which we call its location. Our model evolves in discrete time by selecting r vertices from the graph with replacement, with probabilities proportional to their degrees plus a constant α. A new vertex joins the network and attaches to one of these vertices according to a given probability associated to the ranking of their locations. We give conditions for the occurrence of condensation, showing the existence of phase transitions in α below which condensation occurs. The condensation in our model differs from that in preferential attachment models with fitness in that the condensation can occur at a random location, that it can be due to a persistent hub, and that there can be more than one point of condensation.     

Small subgraphs in random graphs and the power of multiple choices

The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with G₀ as the empty graph on n vertices, in every step a set of r edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining r−1 edges are discarded. Thus after N steps, we have seen rN edges, and selected exactly N out of these to create a graph GN.In a recent paper by Krivelevich, Loh, and Sudakov (2009) [11], the problem of avoiding a copy of some fixed graph F in GN for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs F. In this work we disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions N₀(F,r,n) for arbitrary graphs F and any fixed integer r. That is, we propose an edge selection strategy that a.a.s. (asymptotically almost surely, i.e. with probability 1−o(1) as n→∞) avoids creating a copy of F for as long as N=o(N₀), and prove that any online strategy will a.a.s. create such a copy once N=ω(N₀).     

Growth of preferential attachment random graphs via continuous-time branching processes

Some growth asymptotics of a version of ‘preferential attachment’ random graphs are studied through an embedding into a continuous-time branching scheme. These results complement and extend previous work in the literature.     

Degree growth rates and index estimation in a directed preferential attachment model

Preferential attachment is widely used to model power-law behavior of degree distributions in both directed and undirected networks. In a directed preferential attachment model, despite the well-known marginal power-law degree distributions, not much investigation has been done on the joint behavior of the in- and out-degree growth. Also, statistical estimates of the marginal tail exponent of the power-law degree distribution often use the Hill estimator as one of the key summary statistics, even though no theoretical justification has been given. This paper focuses on the convergence of the joint empirical measure for in- and out-degrees and proves the consistency of the Hill estimator. To do this, we first derive the asymptotic behavior of the joint degree sequences by embedding the in- and out-degrees of a fixed node into a pair of switched birth processes with immigration and then establish the convergence of the joint tail empirical measure. From these steps, the consistency of the Hill estimators is obtained.     

A scaling limit for the degree distribution in sublinear preferential attachment schemes

We consider a general class of preferential attachment schemes evolving by a reinforcement rule with respect to certain sublinear weights. In these schemes, which grow a random network, the sequence of degree distributions is an object of interest which sheds light on the evolving structures. In this article, we use a fluid limit approach to prove a functional law of large numbers for the degree structure in this class, starting from a variety of initial conditions. The method appears robust and applies in particular to ‘non‐tree’ evolutions where cycles may develop in the network. A main part of the argument is to show that there is a unique nonnegative solution to an infinite system of coupled ODEs, corresponding to a rate formulation of the law of large numbers limit, through C₀‐semigroup/dynamical systems methods. These results also resolve a question in Chung, Handjani and Jungreis (2003). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 703–731, 2016     

Asymptotic dependence of in- and out-degrees in a preferential attachment model with reciprocity

Extremes - Reciprocity characterizes the information exchange between users in a network, and some empirical studies have revealed that social networks have a high proportion of reciprocal edges....     

Multigraph limit of the dense configuration model and the preferential attachment graph

The configuration model is the most natural model to generate a random multigraph with a given degree sequence. We use the notion of dense graph limits to characterize the special form of limit objects of convergent sequences of configuration models. We apply these results to calculate the limit object corresponding to the dense preferential attachment graph and the edge reconnecting model. Our main tools in doing so are (1) the relation between the theory of graph limits and that of partially exchangeable random arrays (2) an explicit construction of our random graphs that uses urn models.     

A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least infected neighbours becomes infected and remains so forever. Assume that initially vertices are randomly infected, where is the total number of vertices of the graph. Suppose also that , where is the average degree. We determine a critical function such that when , complete infection occurs with high probability as , but when , then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to .