We introduce a novel preferential attachment model using the draw variables of a modified Pólya urn with an expanding number of colors, notably capable of modeling influential opinions (in terms of vertices of high degree) as the graph evolves. Similar to the Barabási-Albert model, the generated graph grows in size by one vertex at each time instance; in contrast however, each vertex of the graph is uniquely characterized by a color, which is represented by a ball color in the Pólya urn. More specifically at each time step, we draw a ball from the urn and return it to the urn along with a number of reinforcing balls of the same color; we also add another ball of a new color to the urn. We then construct an edge between the new vertex (corresponding to the new color) and the existing vertex whose color ball is drawn. Using color-coded vertices in conjunction with the time-varying reinforcing parameter allows for vertices added (born) later in the process to potentially attain a high degree in a way that is not captured in the Barabási-Albert model. We study the degree count of the vertices by analyzing the draw vectors of the underlying stochastic process. In particular, we establish the probability distribution of the random variable counting the number of draws of a given color which determines the degree of the vertex corresponding to that color in the graph. We further provide simulation results presenting a comparison between our model and the Barabási-Albert network.

We explore a simple model of network dynamics which has previously been applied to the study of information flow in the context of epidemic spreading. A random rooted network is constructed that evolves according to the following rule: at a constant rate, pairs of nodes (i, j) are randomly chosen to interact, with an edge drawn from i to j (and any other out-edge from i deleted) if j is strictly closer to the root with respect to graph distance. We characterise the dynamics of this random network in the limit of large size, showing that it instantaneously forms a tree with long branches that immediately collapse to depth two, then it slowly rearranges itself to a star-like configuration. This curious behaviour has consequences for the study of the epidemic models in which this information network was first proposed.

Numerous works have been proposed to generate random graphs preserving the same properties as real-life large-scale networks. However, many real networks are better represented by hypergraphs. Few models for generating random hypergraphs exist, and also, just a few models allow to both preserve a power-law degree distribution and a high modularity indicating the presence of communities. We present a dynamic preferential attachment hypergraph model which features partition into communities. We prove that its degree distribution follows a power-law, and we give theoretical lower bounds for its modularity. We compare its characteristics with a real-life co-authorship network and show that our model achieves good performances. We believe that our hypergraph model will be an interesting tool that may be used in many research domains in order to reflect better real-life phenomena.

Many classic networks grow by hooking small components via vertices. We introduce a class of networks that grows by fusing the edges of a small graph to an edge chosen uniformly at random from the network. For this random edge-hooking network, we study the local degree profile, that is, the evolution of the average degree of a vertex over time. For a special subclass, we further determine the exact distribution and an asymptotic gamma-type distribution. We also study the “core,” which consists of the well-anchored edges that experience fusing. A central limit theorem emerges for the size of the core.

At the end, we look at an alternative model of randomness attained by preferential hooking, favoring edges that experience more fusing. Under preferential hooking, the core still follows a Gaussian law but with different parameters. Throughout, Pólya urns are systematically used as a method of proof.

Motivated by recent studies of big samples, this work aims to construct a parametric model which is characterized by the following features: (i) a ‘local’ reinforcement, i.e. a reinforcement mechanism mainly based on the last observations, (ii) a random persistent fluctuation of the predictive mean, and (iii) a long-term almost sure convergence of the empirical mean to a deterministic limit, together with a chi-squared goodness-of-fit result for the limit probabilities. This triple purpose is achieved by the introduction of a new variant of the Eggenberger–Pólya urn, which we call the rescaled Pólya urn. We provide a complete asymptotic characterization of this model, pointing out that, for a certain choice of the parameters, it has properties different from the ones typically exhibited by the other urn models in the literature. Therefore, beyond the possible statistical application, this work could be interesting for those who are concerned with stochastic processes with reinforcement.

Empirical studies (e.g. Jiang et al. (2015) and Mislove et al. (2007)) show that online social networks have not only in- and out-degree distributions with Pareto-like tails, but also a high proportion of reciprocal edges. A classical directed preferential attachment (PA) model generates in- and out-degree distributions with power-law tails, but the theoretical properties of the reciprocity feature in this model have not yet been studied. We derive asymptotic results on the number of reciprocal edges between two fixed nodes, as well as the proportion of reciprocal edges in the entire PA network. We see that with certain choices of parameters, the proportion of reciprocal edges in a directed PA network is close to 0, which differs from the empirical observation. This points out one potential problem of fitting a classical PA model to a given network dataset with high reciprocity, and indicates that alternative models need to be considered.

A hooking network is built by stringing together components randomly chosen from a set of building blocks (graphs with hooks). The vertices are endowed with “affinities” which dictate the attachment mechanism. We study the distance from the master hook to a node in the network chosen according to its affinity after many steps of growth. Such a distance is commonly called the depth of the chosen node. We present an exact average result and a rather general central limit theorem for the depth. The affinity model covers a wide range of attachment mechanisms, such as uniform attachment and preferential attachment, among others. Naturally, the limiting normal distribution is parametrized by the structure of the building blocks and their probabilities. We also take the point of view of a visitor uninformed about the affinity mechanism by which the network is built. To explore the network, such a visitor chooses the nodes uniformly at random. We show that the distance distribution under such a uniform choice is similar to the one under random choice according to affinities.

We introduce a class of non-uniform random recursive trees grown with an attachment preference for young age. Via the Chen–Stein method of Poisson approximation, we find that the outdegree of a node is characterized in the limit by ‘perturbed’ Poisson laws, and the perturbation diminishes as the node index increases. As the perturbation is attenuated, a pure Poisson limit ultimately emerges in later phases. Moreover, we derive asymptotics for the proportion of leaves and show that the limiting fraction is less than one half. Finally, we study the insertion depth in a random tree in this class. For the insertion depth, we find the exact probability distribution, involving Stirling numbers, and consequently we find the exact and asymptotic mean and variance. Under appropriate normalization, we derive a concentration law and a limiting normal distribution. Some of these results contrast with their counterparts in the uniform attachment model, and some are similar.

In this paper, several properties of a class of trees presenting preferential attachment phenomenon—plane-oriented recursive trees (PORTs) are uncovered. Specifically, we investigate the degree profile of a PORT by determining the exact probability mass function of the degree of a node with a fixed label. We compute the expectation and the variance of degree variable via a Pólya urn approach. In addition, we study a topological index, Zagreb index, of this class of trees. We calculate the exact first two moments of the Zagreb index (of PORTs) by using recurrence methods. Lastly, we determine the limiting degree distribution in PORTs that grow in continuous time, where the embedding is done in a Poissonization framework. We show that it is exponential after proper scaling.

The directed preferential attachment model is revisited. A new exact characterization of the limiting in- and out-degree distribution is given by two independent pure birth processes that are observed at a common exponentially distributed time T (thus creating dependence between in- and out-degree). The characterization gives an explicit form for the joint degree distribution, and this confirms previously derived tail probabilities for the two marginal degree distributions. The new characterization is also used to obtain an explicit expression for tail probabilities in which both degrees are large. A new generalized directed preferential attachment model is then defined and analyzed using similar methods. The two extensions, motivated by empirical evidence, are to allow double-directed (i.e. undirected) edges in the network, and to allow the probability of connecting an ingoing (outgoing) edge to a specified node to also depend on the out-degree (in-degree) of that node.

We consider a simple preferential attachment graph process, which begins with a finite graph and in which a new (t + 1)st vertex is added at each subsequent time step t that is connected to each previous vertex u ≤ t with probability du(t)/t, where du(t) is the degree of u at time t. We analyse the graph obtained as the infinite limit of this process, and we show that, as long as the initial finite graph is neither edgeless nor complete, with probability 1 the outcome will be a copy of the Rado graph augmented with a finite number of either isolated or universal vertices.

We consider subgraph counts in general preferential attachment models with power-law degree exponent $\tau > 2$. For all subgraphs H, we find the scaling of the expected number of subgraphs as a power of the number of vertices. We prove our results on the expected number of subgraphs by defining an optimization problem that finds the optimal subgraph structure in terms of the indices of the vertices that together span it and by using the representation of the preferential attachment model as a Pólya urn model.

A new network evolution model is introduced in this paper. The model is based on cooperations of N units. The units are the nodes of the network and the cooperations are indicated by directed links. At each evolution step N units cooperate, which formally means that they form a directed N-star subgraph. At each step either a new unit joins the network and it cooperates with N − 1 old units, or N old units cooperate. During the evolution both preferential attachment and uniform choice are applied. Asymptotic power law distributions are obtained both for in-degrees and for out-degrees.

Vipps is a peer-to-peer mobile payment solution launched by Norway’s largest financial services group DNB. The Vipps transaction data may be viewed as a graph with users corresponding to the nodes, and the financial transactions between the users defining the edges. We have followed the evolution of this graph from May 2015 to September 2016. This is a unique data set, as information about transactions of individuals is usually not available for research. In this paper, we use an advanced statistical model where preferential attachment is combined with fitness. We show that the intrinsic quality of the nodes in the Vipps network plays an important part in the evolution of the network. This insight may, e.g., be used to identify influential nodes for viral marketing.

We extend the work of Antunović et al. (2016) on competing types in preferential attachment models to include cases where the types have different fitnesses, which may be either multiplicative or additive. We show that, depending on the values of the parameters of the models, there are different possible limiting behaviours depending on the zeros of a certain function. In particular, we show the existence of choices of the parameters where one type is favoured both by having higher fitness and by the type of attachment mechanism, but the other type has a positive probability of dominating the network in the limit.

Continuous-time branching processes (CTBPs) are powerful tools in random graph theory, but are not appropriate to describe real-world networks since they produce trees rather than (multi)graphs. In this paper we analyze collapsed branching processes (CBPs), obtained by a collapsing procedure on CTBPs, in order to define multigraphs where vertices have fixed out-degree m≥2. A key example consists of preferential attachment models (PAMs), as well as generalized PAMs where vertices are chosen according to their degree and age. We identify the degree distribution of CBPs, showing that it is closely related to the limiting distribution of the CTBP before collapsing. In particular, this is the first time that CTBPs are used to investigate the degree distribution of PAMs beyond the tree setting.