Search

We prove concentration inequality results for geometric graph properties of an instance of the Cooper–Frieze [5] preferential attachment model withedge-steps. More precisely, we investigate a random graph model that at each time$t\in \mathbb{N}$, with probabilitypadds a new vertex to the graph (avertex-stepoccurs) or with probability$1-p$an edge connecting two existent vertices is added (anedge-stepoccurs). We prove concentration results for theglobal clustering coefficientas well as theclique number. More formally, we prove that the global clustering, with high probability, decays as$t^{-\gamma(p)}$for a positive function$\gamma$ofp, whereas the clique number of these graphs is, up to subpolynomially small factors, of order$t^{(1-p)/(2-p)}$.

It has been observed in real networks that the fraction of nodes P(k) with degree k satisfies the power-law P(k) ∝ k−γ for k > kmin > 0. However, the degree distribution of nodes in these networks before kmin varies slowly to the extent of being uniform as compared to the degree distribution after kmin. Most of the previous studies focus on the degree distribution after kmin and ignore the initial flatness in the distribution of degrees. In this paper, we propose a model that describes the degree distribution for the whole range of k > 0, i.e., before and after kmin. The network evolution is made up of two steps. In the first step, a new node is connected to the network through a preferential attachment method. In the second step, a certain number of edges between the existing nodes are added such that the end nodes of an edge are selected either uniformly or preferentially. The model has a parameter to control the uniform or preferential selection of nodes for creating edges in the network. We perform a comprehensive mathematical analysis of our proposed model in the discrete domain and prove that the model exhibits an asymptotically power-law degree distribution after kmin and a flat-ish distribution before kmin. We also develop an algorithm that guides us in determining the model parameters in order to fit the model output to the node degree distribution of a given real network. Our simulation results show that the degree distributions of the graphs generated by this model match well with those of the real-world graphs.

In this paper, we investigate several random structures, namely two classes of random lobster trees (RLTs) and a class of random spider trees (RSTs). The first class of RLTs grow with a fixed probability, whereas those from the second class evolve in a dynamic manner underlying a flavor of semi-opposite reinforcement. For these two classes, we characterize the structure of the random graphs therein via some probabilistic methods. In addition, we look into a class of RSTs that evolve in a preferential attachment manner. We characterize the structure of RSTs by determining the exact and asymptotic distributions of the number of leaves, and by computing two kinds of topological indices.

We examine the structure of risk-sharing networks in developing countries using data from the Tanzanian village of Nyakatoke. We first show that the Nyakatoke network exhibits: (1) the “small-world” phenomenon, where two households who are not themselves risk-sharing partners are separated only by a short chain of intermediaries; (2) preferential attachment, which is a network formation process where the probability of a household receiving a partner is proportional to that household’s existing number of partners; and (3) assortative mixing, as similarly connected households tend to link to each other. We then examine the implications of these features for network performance by comparing the Nyakatoke network to simulated networks with alternative structural traits. Our simulations show that the Nyakatoke network displays optimal or near-optimal performance along multiple dimensions. In particular, the Nyakatoke network has a notable ability to withstand perturbations of multiple types, a property that none of the counterfactual networks possess.

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.

In this paper we consider random trees associated with the genealogy of Crump–Mode–Jagers processes and perform Bernoulli bond-percolation whose parameter depends on the size of the tree. Our purpose is to show the existence of a giant percolation cluster for appropriate regimes as the size grows. We stress that the family trees of Crump–Mode–Jagers processes include random recursive trees, preferential attachment trees, binary search trees for which this question has been answered by Bertoin [7], as well as (more general) m-ary search trees, fragmentation trees, and median-of-( $2\ell+1$ ) binary search trees, to name a few, where to our knowledge percolation has not yet been studied.

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.

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.

We investigate systems of interacting stochastic differential equations with two kinds of heterogeneity: one originating from different weights of the linkages, and one concerning their asymptotic relevance when the system becomes large. To capture these effects, we define a partial mean field system, and prove a law of large numbers with explicit bounds on the mean squared error. Furthermore, a large deviation result is established under reasonable assumptions. The theory will be illustrated by several examples: on the one hand, we recover the classical results of chaos propagation for homogeneous systems, and on the other hand, we demonstrate the validity of our assumptions for quite general heterogeneous networks including those arising from preferential attachment random graph models.

We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the $\alpha^{th}$ power $(\alpha >1)$ of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of $2n-2$ new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, a fine control on this probability may be leveraged to derive a lower tail Large Deviation Principle (LDP) for $L = \sum_{i=1}^{n} \frac{S_i^2}{i^2}$, where $\{S_n : n \geq 0\}$ is a simple symmetric random walk started at zero. We provide an alternate proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous time analogue of $L$. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process., Comment: 44 pages

The diversity of power-law-like degree distribution in social networks has been discovered in a large number of empirical studies. Analyzing the origin of power-law-like the degree distribution diversity is greatly important for understanding the law of human social interaction. In our work, the diversity of power-law-like degree distribution is demonstrated empirically in social networks. The origin of the degree distribution diversity is analyzed from the point of the social stratification and the bidirectional preferential attachment among individuals. We proposed a model to reproduce the diversity of degree distribution in social networks, and the analytic solution of the model was derived. The simulation results indicate that the evolution time of social network and the biggest social hierarchy gap among individuals may be the origin which results in the power-law-like degree distribution diversity. Therefore, the model is helpful to comprehend the law of human social interaction.

We deal with a general preferential attachment graph model with multiple type edges. The types are chosen randomly, in a way that depends on the evolution of the graph. In the $N$-type case, we define the (generalized) degree of a given vertex as $\boldsymbol{d}=(d_{1},d_{2},\dots,d_{N})$, where $d_{k}\in\mathbb{Z}_{0}^{+}$ is the number of type $k$ edges connected to it. We prove the existence of an a.s.\ asymptotic degree distribution for a general family of preferential attachment random graph models with multi-type edges. More precisely, we show that the proportion of vertices with (generalized) degree $\boldsymbol{d}$ tends to some random variable as the number of steps goes to infinity. We also provide recurrence equations for the asymptotic degree distribution. Finally, we generalize the scale-free property of random graphs to the multi-type case., Comment: 20 pages; extended version: v3 generalization for arbitrary number of types

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.

Real complex networks usually have small-world effect, scale-free features and hierarchical modularity, a construction method for deterministic hierarchical network is proposed in this paper. The network model with growth and global preferential attachment characteristic and connected by the copy network modules to establish hierarchical network model. By theoretical calculation and numerical simulation about the deterministic hierarchical complex network model, the results illustrate that the complex network model satisfy the small-world effect, scale-free feature and hierarchical modularity, the calculation results show that the size of the hierarchical network model for exponential growth with the network size increased, and the average degree of nodes is shown as linear growth; at the same time, the model of scale-free feature and the hierarchical modularity with network parameters do not have correlation which is an inherent attribute of network model itself; the clustering-degree correlations in the network model satisfy power-law characteristics and the nodes contact closely together in the modules which are connected by the Hub nodes in the complex network model. .

A spatio-temporal model of particle or star growth is defined, whereby new unit masses arrive sequentially in discrete time. These unit masses are referred to as candidate stars, which tend to arrive in mass-dense regions and then either form a new star or are absorbed by some neighbouring star of high mass. We analyse the system as time increases, and derive the asymptotic growth rate of the number of stars as well as the size of a randomly chosen star. We also prove that the size-biased mass distribution converges to a Poisson–Dirichlet distribution. This is achieved by embedding our model into a continuous-time Markov process, so that new stars arrive according to a marked Poisson process, with locations as marks, whereas existing stars grow as independent Yule processes. Our approach can be interpreted as a Hoppe-type urn scheme with a spatial structure. We discuss its relevance for and connection to models of population genetics, particle aggregation, image segmentation, epidemic spread, and random graphs with preferential attachment.

The last couple of years have witnessed a huge surge in usage of the Internet due to the availability of several interactive applications of Web 2.0. Growth in both web users and varieties of online objects has been observed. In this paper, we propose a growth model for online emerging user–object bipartite networks to investigate selection behaviors of web users. According to model, both sets of users and objects grow constantly but edges arrive only from user set. The network evolves by arrival of external edges brought by new users and/or internal edges from old users. These external and internal edges are attached with a combination of preferential and random attachment mechanism. We have considered different attachment procedures for external edges of new users and internal edges of old users. To validate our model, we have taken nine different real online networks with distinct objects. Our results show good agreement between empirical data and theoretical model. We report mean absolute deviation (MAD), mean square error (MSE) and root mean square error (RMSE) for the proposed growth model. We emphasize on significant inferences about selection behaviors of web users after interpreting parameters’ values of the model. We also report detailed analysis of randomness in selection of new and old users that gives interesting inferences for each of the considered online networks.

Symmetries are ubiquitous in real networks and often characterize network features and functions. Here we present a generalization of network symmetry called \emph{latent symmetry}, which is an extension of the standard notion of symmetry. They are defined in terms of standard symmetries in a reduced version of the network. One unique aspect of latent symmetries is that each one is associated with a \emph{size}, which provides a way of discussing symmetries at multiple scales in a network. We are able to demonstrate a number of examples of networks (graphs) which contain latent symmetry, including a number of real networks. In numerical experiments, we show that latent symmetries are found more frequently in graphs built using preferential attachment, a standard model of network growth, when compared to non-network like (Erd{\H o}s-R\'enyi) graphs. Finally we prove that if vertices in a network are latently symmetric, then they must have the same eigenvector centrality, similar to vertices which are symmetric in the standard sense. This suggests that the latent symmetries present in real-networks may serve the same structural and functional purpose standard symmetries do in these networks. We conclude from these facts and observations that \emph{latent symmetries} are present in real networks and provide useful information about the network potentially beyond standard symmetries as they can appear at multiple scales., Comment: 18 pages

Taylor's power law states that the variance function decays as a power law. It is observed for population densities of species in ecology. For random networks another power law, that is, the power law degree distribution is widely studied. In this paper the original Taylor's power law is considered for random networks. A precise mathematical proof is presented that Taylor's power law is asymptotically true for the $N$-stars network evolution model.

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.

PageRank is a well-known algorithm for measuring centrality in networks. It was originally proposed by Google for ranking pages in the World-Wide Web. One of the intriguing empirical properties of PageRank is the so-called `power-law hypothesis': in a scale-free network the PageRank scores follow a power law with the same exponent as the (in-)degrees. Up to date, this hypothesis has been confirmed empirically and in several specific random graphs models. In contrast, this paper does not focus on one random graph model but investigates the existence of an asymptotic PageRank distribution, when the graph size goes to infinity, using local weak convergence. This may help to identify general network structures in which the power-law hypothesis holds. We start from the definition of local weak convergence for sequences of (random) undirected graphs, and extend this notion to directed graphs. To this end, we define an exploration process in the directed setting that keeps track of in- and out-degrees of vertices. Then we use this to prove the existence of an asymptotic PageRank distribution. As a result, the limiting distribution of PageRank can be computed directly as a function of the limiting object. We apply our results to the directed configuration model and continuous-time branching processes trees, as well as preferential attachment models., 32 pages, 5 figures

Dans une marche aleatoire a pas renforces, a chaque instant entier et avec une probabilite fixee $p\in (0,1)$, le marcheur repete un de ses precedents pas tire uniformement au hasard, et avec probabilite $1-p$ effectue un nouveau pas independant de loi donnee. Comme exemples dans la litterature figurent l’elephant random walk et le shark random swim. Nous nous interessons ici a un analogue en temps continu, c’est-a-dire lorsque la marche aleatoire est remplacee par un processus de Levy. Pour des parametres de memoire sous-critiques (ou encore admissibles) $p

We study randomly growing trees governed by the affine preferential attachment rule. Starting with a seed tree $S$, vertices are attached one by one, each linked by an edge to a random vertex of the current tree, chosen with a probability proportional to an affine function of its degree. This yields a one-parameter family of preferential attachment trees $(T_n^S)_{n\geq|S|}$, of which the linear model is a particular case. Depending on the choice of the parameter, the power-laws governing the degrees in $T_n^S$ have different exponents. We study the problem of the asymptotic influence of the seed $S$ on the law of $T_n^S$. We show that, for any two distinct seeds $S$ and $S'$, the laws of $T_n^S$ and $T_n^{S'}$ remain at uniformly positive total-variation distance as $n$ increases. This is a continuation of Curien et al. (2015), which in turn was inspired by a conjecture of Bubeck et al. (2015). The technique developed here is more robust than previous ones and is likely to help in the study of more general attachment mechanisms., Comment: 31 pages, 1 figure

We explore the tree limits recently defined by Elek and Tardos. In particular, we find tree limits for many classes of random trees. We give general theorems for three classes of conditional Galton-Watson trees and simply generated trees, for split trees and generalized split trees (as defined here), and for trees defined by a continuous-time branching process. These general results include, for example, random labelled trees, ordered trees, random recursive trees, preferential attachment trees, and binary search trees., 50 pages

We show that for many models of random trees, the independence number divided by the size converges almost surely to a constant as the size grows to infinity; the trees that we consider include random recursive trees, binary and $m$-ary search trees, preferential attachment trees, and others. The limiting constant is computed, analytically or numerically, for several examples. The method is based on Crump-Mode-Jagers branching processes., 15 pages (v2: reference added)

Preferential attachment models form a popular class of growing networks, where incoming vertices are preferably connected to vertices with high degree. We consider a variant of this process, where vertices are equipped with a random initial fitness representing initial inhomogeneities among vertices and the fitness influences the attractiveness of a vertex in an additive way. We consider a heavy-tailed fitness distribution and show that the model exhibits a phase transition depending on the tail exponent of the fitness distribution. In the weak disorder regime, one of the old vertices has maximal degree irrespective of fitness, while for strong disorder the vertex with maximal degree has to satisfy the right balance between fitness and age. Our methods use martingale methods to show concentration of degree evolutions as well as extreme value theory to control the fitness landscape., 48 pages

Many real-world systems are profitably described as complex networks that grow over time. Preferential attachment and node fitness are two simple growth mechanisms that not only explain certain structural properties commonly observed in real-world systems, but are also tied to a number of applications in modeling and inference. While there are statistical packages for estimating various parametric forms of the preferential attachment function, there is no such package implementing non-parametric estimation procedures. The non-parametric approach to the estimation of the preferential attachment function allows for comparatively finer-grained investigations of the `rich-get-richer' phenomenon that could lead to novel insights in the search to explain certain nonstandard structural properties observed in real-world networks. This paper introduces the R package PAFit, which implements non-parametric procedures for estimating the preferential attachment function and node fitnesses in a growing network, as well as a number of functions for generating complex networks from these two mechanisms. The main computational part of the package is implemented in C++ with OpenMP to ensure scalability to large-scale networks. We first introduce the main functionalities of PAFit through simulated examples, and then use the package to analyze a collaboration network between scientists in the field of complex networks. The results indicate the joint presence of `rich-get-richer' and `fit-get-richer' phenomena in the collaboration network. The estimated attachment function is observed to be near-linear, which we interpret as meaning that the chance an author gets a new collaborator is proportional to their current number of collaborators. Furthermore, the estimated author fitnesses reveal a host of familiar faces from the complex networks community among the field's topmost fittest network scientists., Comment: Conditionally accepted to Journal of Statistical Software

Many classes of network growth models have been proposed in the literature for capturing real-world complex networks. Existing research primarily focuses on global characteristics of these models, e.g., degree distribution. We aim to shift the focus towards studying the network growth dynamics from the perspective of individual nodes. In this paper, we study how a metric for node influence in network growth models behaves over time as the network evolves. This metric, which we call node visibility, captures the probability of the node to form new connections. First, we conduct an investigation on three popular network growth models -- preferential attachment, additive, and multiplicative fitness models; and primarily look into the "influential nodes" or "leaders" to understand how their visibility evolves over time. Subsequently, we consider a generic fitness model and observe that the multiplicative model strikes a balance between allowing influential nodes to maintain their visibility, while at the same time making it possible for new nodes to gain visibility in the network. Finally, we observe that a spatial growth model with multiplicative fitness can curtail the global reach of influential nodes, thereby allowing the emergence of a multiplicity of "local leaders" in the network., Comment: 4 figures

We investigate spatial random graphs defined on the points of a Poisson process in d-dimensional space, which combine scale-free degree distributions and long-range effects. Every Poisson point is assigned an independent weight. Given the weight and position of the points, we form an edge between any pair of points independently with a probability depending on the two weights of the points and their distance. Preference is given to short edges and connections to vertices with large weights. We characterize the parameter regime where there is a non-trivial percolation phase transition and show that it depends not only on the power-law exponent of the degree distribution but also on a geometric model parameter. We apply this result to characterize robustness of age-based spatial preferential attachment networks.

We prove almost sure convergence of the maximum degree in an evolving graph model combining a growing number of local choices with sublinear preferential attachment. At each step in the growth of the graph, a new vertex is introduced. Then we draw a random number of edges from it to existing vertices, chosen independently by the following rule. For each edge, we consider a sample of the growing size of vertices chosen with probabilities proportional to a sublinear function of their degrees. Then the new vertex attaches to the vertex with the highest degree from the sample. Depending on the growth rate of the sample and the sublinear function, the maximum degree could be of sublinear order, of linear order, or having almost all edges drawing to it. The proof uses various stochastic approximation processes and a large deviation approach.

We consider a generalised d-dimensional model for asymptotically-scale-free geographical networks. Central to many networks of this kind, when considering their growth in time, is the attachment rule, i.e. the probability that a new node is attached to one (or more) preexistent nodes. In order to be more realistic, a fitness parameter $\eta_i \in [0,1]$ for each node $i$ of the network is also taken into account to reflect the ability of the nodes to attract new ones. Our d-dimensional model takes into account the geographical distances between nodes, with different probability distribution for $\eta$ which sensibly modifies the growth dynamics. The preferential attachment rule is assumed to be $\Pi_i\propto k_i \eta_i r_{ij}^{-\alpha_A} $ where $k_i$ is the connectivity of the $i$th pre-existing site and $\alpha_A$ characterizes the importance of the euclidean distance r for the network growth. For special values of the parameters, this model recovers respectively the Bianconi-Barab\'{a}si and the Barab\'{a}si-Albert ones. The present generalised model is asymptotically scale-free in all cases, and its degree distribution is very well fitted with q-exponential distributions, which optimise the nonadditive entropy $S_q$, given by $p(k) \propto e_q^{-k/\kappa} \equiv 1/[1+(q-1)k/\kappa]^{1/(q-1)}$, with $(q,\kappa)$ depending uniquely only on the ratio $\alpha_A/d$ and the fitness distribution. Hence this model constitutes a realization of asymptotically-scale-free geographical networks within nonextensive statistical mechanics, where $k$ plays the role of energy and $\kappa$ plays the role of temperature. General scaling laws are also found for q as a function of the parameters of the model., Comment: 10 pages, 5 figures

Preferential attachment is widely used to model power-law behavior of degree distributions in both directed and undirected networks. Statistical estimates of the tail exponent of the power-law degree distribution often use the Hill estimator as one of the key summary statistics. The consistency of the Hill estimator for network data has not been explored and the major goal in this paper is to prove consistency in certain models. To do this, we first derive the asymptotic behavior of the degree sequence via embedding the degree growth of a fixed node into a birth immigration process and then show the convergence of the tail empirical measure. From these steps, the consistency of the Hill estimator is obtained. Simulations are provided as an illustration for the asymptotic distribution of the Hill estimator.

Considering that some research and development (R&D) networks are becoming increasingly interdependent, risk not only propagates within one R&D network but also spreads to other R&D networks. This paper proposes a model of risk cascading propagation in order to explore the vulnerability of interdependent R&D networks. Firstly, we propose the generation algorithm of individual R&D networks based on the rules of preferential attachment and geographical proximity, and then build the interdependences between two R&D networks by identifying the input interdependence and shared interdependence. Secondly, we propose the model of risk propagation within one R&D network by defining the risk load and risk capacity of each enterprise, and building the rule of conditional triggering among risks. We then propose the four-stage model for describing the process of risk cascading propagation across interdependent R&D networks. Finally, we investigate the vulnerability of interdependent R&D networks to risk cascading propagation through numerical simulation. Simulation results show that the critical tolerance threshold β ∗ can effectively indicate the vulnerability of interdependent R&D networks to risk cascading propagation. When the value of the tolerance parameter β exceeds the critical tolerance threshold β ∗ , the risk cascading propagation can be entirely prevented in interdependent R&D networks. The vulnerability of interdependent R&D networks increases with the increasing heterogeneity degree of all the enterprises’ risk capacities. The interdependences between interdependent R&D networks can increase their vulnerability to risk cascading propagation. Random attack has the least impact on the vulnerability of interdependent R&D networks, whereas high-degree attack and high-capacity attack have the same impact on the vulnerability.

The inconsistent fluctuation behavior of Internet predicted by preferential attachment(PA) and Gibrat’s law requires empirical investigations on the actual system. By using the interval-tunable Gibrat’s law statistics, we find the actual fluctuation, characterized by the conditional standard deviation of the degree growth rate, changes with the interval length and displays a crossover transition from PA type to Gibrat’s law type, which has not yet been captured by any previous models. We characterize the transition dynamics quantitatively and determine the applicative range of PA and Gibrat’s law. The correlation analysis indicates the crossover transition may be attributed to the accumulative correlation between the internal links.

We introduce a variety of network models using a Poisson-based edge localization strategy, which result in clustered scale-free topologies. We first verify the success of our localization strategy by realizing a variant of the well-known Watts–Strogatz model with an inverse approach, implying a small-world regime of rewiring from a random network through a regular one. We then apply the rewiring strategy to a pure Barabasi–Albert model and successfully achieve a small-world regime, with a limited capacity of scale-free property. To imitate the high clustering property of scale-free networks with higher accuracy, we adapted the Poisson-based wiring strategy to a growing network with the ingredients of both preferential attachment and local connectivity. To achieve the collocation of these properties, we used a routine of flattening the edges array, sorting it, and applying a mixing procedure to assemble both global connections with preferential attachment and local clusters. As a result, we achieved clustered scale-free networks with a computational fashion, diverging from the recent studies by following a simple but efficient approach.

Earthquakes as spatio-temporal complex systems have been recently studied using complex network theory. Seismic networks are dynamical networks due to addition of new seismic events over time leading to establishing new nodes and links to the network. Here we have constructed Iran and Italy seismic networks based on Hybrid Model and testified the preferential attachment hypothesis for the connection of new nodes which states that it is more probable for newly added nodes to join the highly connected nodes comparing to the less connected ones. We showed that the preferential attachment is present in the case of earthquakes network and the attachment rate has a linear relationship with node degree. We have also found the seismic passive points, the most probable points to be influenced by other seismic places, using their preferential attachment values.

People’s online rating behavior can be modeled by user–object bipartite networks directly. However, few works have been devoted to reveal the hidden relations between users, especially from the perspective of signed networks. We analyze the signed monopartite networks projected by the signed user–object bipartite networks, finding that the networks are highly clustered with obvious community structure. Interestingly, the positive clustering coefficient is remarkably higher than the negative clustering coefficient. Then, a Signed Growing Network model (SGN) based on local preferential attachment is proposed to generate a user’s signed network that has community structure and high positive clustering coefficient. Other structural properties of the modeled networks are also found to be similar to the empirical networks.

The problem of uncovering the internal operating function of network models is intriguing, demanded and attractive in researches of complex networks. Notice that, in the past two decades, a great number of artificial models are built to try to answer the above mentioned task. Based on the different growth ways, these previous models can be divided into two categories, one type, possessing the preferential attachment, follows a power-law P ( k ) ∼ k − γ , 2 γ 3 . The other has exponential-scaling feature, P ( k ) ∼ α − k . However, there are no models containing above two kinds of growth ways to be presented, even the study of interconnection between these two growth manners in the same model is lacking. Hence, in this paper, we construct a class of planar and self-similar graphs motivated from a new attachment way, vertex–edge-growth network-operation, more precisely, the couple of both them. We report that this model is sparse, small world and hierarchical. And then, not only is scale-free feature in our model, but also lies the degree parameter γ ( ≈ 3 . 242 ) out the typical range. Note that, we suggest that the coexistence of multiple vertex growth ways will have a prominent effect on the power-law parameter γ , and the preferential attachment plays a dominate role on the development of networks over time. At the end of this paper, we obtain an exact analytical expression for the total number of spanning trees of models and also capture spanning trees entropy which we have compared with those of their corresponding component elements.

This paper proposes an evolution model and an analysis of the behavior of music consumers on online music streaming services. While previous studies have observed power-law degree distributions of usage in online music streaming services, the underlying behavior of users has not been well understood. Users and songs can be described using a bipartite network where an edge exists between a user node and a song node when the user has listened that song. The growth mechanism of bipartite networks has been used to understand the evolution of online bipartite networks Zhang et al. (2013). Existing bipartite models are based on a preferential attachment mechanism Laszlo Barabasi and Albert (1999) in which the probability that a user listens to a song is proportional to its current popularity. This mechanism does not allow for two types of real world phenomena. First, a newly released song with high quality sometimes quickly gains popularity. Second, the popularity of songs normally decreases as time goes by. Therefore, this paper proposes a new model that is more suitable for online music services by adding fitness and aging functions to the song nodes of the bipartite network proposed by Zhang et al. (2013). Theoretical analyses are performed for the degree distribution of songs. Empirical data from an online streaming service, Last.fm , are used to confirm the degree distribution of the object nodes. Simulation results show improvements from a previous model. Finally, to illustrate the application of the proposed model, a simplified royalty cost model for online music services is used to demonstrate how the changes in the proposed parameters can affect the costs for online music streaming providers. Managerial implications are also discussed.

We discuss the connection between the theory of motion of substance in a channel and the theory of growth of large random networks. The channel contains nodes connected by edges. The substance is located in the nodes of the channel. It can move between the nodes of the channel through the edges which connect the nodes. We study probability distributions connected to distribution of substance for selected cases of stationary motion of substance in a channel. The corresponding model equations contain as specific cases the model equations for the degree distributions of several classes of growing random networks. We consider two scenarios for stationary motion of substance in the channel. Scenario 1 is connected to stationary motion of substance in direction to nodes labeled by larger numbers. Scenario 2 is connected to stationary motion of substance in the opposite direction. Probability distributions are obtained for different cases connected to the two scenarios. The results for the Scenario 1 are connected to the theory of degree distributions of nodes of a random network growing in presence of preferential attachment (as specific case we obtain also the degree distribution for the Barabasi–Albert case). Corresponding results for Scenario 2 can be connected to the theory of growing random networks too. The kind of attachment for these results can be classified as negative preferential attachment or preferential attachment with preference of attachment to nodes of smaller degree.

We prove the monadic second-order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does not hold for non-tree uniform attachment models.

This paper presents a novel evolutionary model that captures the characteristics and the evolutionary pattern of an international logistics network in the context of the Belt and Road. In this study, the logistics network is considered as a complex self-adapting system, in which a new node is added by preferential attachment, and evolution is an iterative process of interaction among factors, such as the social economy, infrastructure construction and international relations. Grounded in the continuum theory, the model is deduced with rigorous derivation, and the results show that the proposed model can accurately reflect the degree distribution of the international logistics network, which follows a shifted power law. Simulation experiments are conducted to demonstrate the interaction process, and the simulated network presents a hierarchical pattern of “several central nodes and a large number of peripheral nodes”. China, South Korea, India, Indonesia and the Russian Federation are considered central nodes and have a significant influence on the B&R international logistics network.

Spatial structures of urban systems are best described as multifractals. To provide insight on a hidden mechanism responsible for such scaling we investigate the multiplicative random cascade (MRC) model of urban spatial structure. MRC is a multiplicative process capable of producing multifractal 2D patterns, which is expressed in a closed analytical form. We use street intersection points pattern (SIPP) data as a proxy of urban structure. Renyi’s generalized dimensions (RGD) spectra, probability distributions of intersections densities, and urban layouts generated by the MRC model are compared to the same descriptors extracted from SIPP data for six U.S. metropolitan statistical areas (MSAs). We found that the RGD spectrum of the best-fit MRC model closely matches the observed spectrum in all cases. We also found that CDF of models’ density distributions do not match closely observed density distributions, although, in some cases, differences are not large. Observed density distributions have forms that are close to the log-normal distribution which suggests that a hidden process is multiplicative. Finally, we found that the MRC model is broadly compatible with the observed urban layouts. Given our findings, we suggest that the hidden process of urban scaling is the preferential attachment dynamics — development is attracted to areas in proportion to the degree of their existing development.

In this paper, based on growth and preferential attachment mechanism, we give a network generation model aiming at generating networks with community structure. There are three characteristics for the networks generated by the generation model. The first is that the community sizes can be nonuniform. The second is that there are bridge hubs in each community. The third is that the strength of community structure is adjustable. Next, we investigate rumor propagation behavior on the generated networks by performing Monte Carlo simulations to reveal the influence of bridge hubs, nonuniformity of community sizes and the strength of community structure on the dynamic behavior of the rumor propagation. We find that bridge hubs have outstanding performance in propagation speed and propagation size, and larger modularity can reduce rumor propagation. Furthermore, when the decay rate of rumor spreading β is large, the final density of the stiflers is larger if the rumor originates in larger community. Additionally, when on networks with different strengths of community structure, rumor propagation exhibits greater difference in the density of stiflers and in the peak prevalence if the decay rate β is larger.

Novel phenomenon receives similar attention as popular one. Therefore predicting novelty is as important as popularity. Emergence is the side effect of competition and ageing in evolving systems. Recent behaviour or recent link gain in networks plays an important role in emergence. We exploited this wisdom and came up with two models considering different scenarios and systems. Where recent behaviour dominates over total behaviour (total link gain) in the first one, and recent behaviour is as important as total behaviour for future link gain in the second one. It supposes that random walker walks on a network and can jump to any node, the probability of jumping or making a connection to other node is based on which node is recently more active or receiving more links. In our assumption, the random walker can also jump to the node which is already popular but recently not popular. We are able to predict emerging nodes which are generally suppressed under preferential attachment effect. To show the performance of our model we have conducted experiments on four real data sets namely, MovieLens, Netflix, Facebook and Arxiv High Energy Physics paper citation. For testing our model we used four information retrieval indices namely Precision, Novelty, Area Under Receiving Operating Characteristic (AUC) and Kendal’s rank correlation coefficient. We have used four benchmark models for validating our proposed models. Although our model does not perform better in all the cases but, it has theoretical significance in working better for recent behaviour dominated systems.

Given the same two networks and only one-to-one interlinks are allowed, apparently interdependent networks coupled by these two networks has the optimal robustness when we connect every pair of the same nodes in these two networks. According to the structure of this interdependent network with the optimal robustness, we propose a preferential attachment strategy. And by applying this preferential attachment strategy to three existing connectivity link addition strategies RA (random addition strategy), LD (low degree addition strategy) and LIDD (low inter degree–degree difference addition strategy), we find that each improved strategy is obviously better than before in improving the robustness of interdependent networks. Our findings can provide guidance on connectivity link addition strategy to improve robustness of interdependent networks against cascading failures.

Tourism is a complex dynamic system including multiple actors which are related each other composing an evolving social network. This paper presents a growing model that explains how part of the supply components in a tourism system forms a social network. Specifically, the lodgings and services in a destination are the network nodes and a link between them appears if a representative tourist hosted in the lodging visits/consumes the service during his/her stay. The specific link between both categories are determined by a random and preferential attachment rule. The analytic results show that the long-term degree distribution of services follows a shifted power-law distribution. The numerical simulations show slight disagreements with the theoretical results in the case of the one-mode degree distribution of services, due to the low order of convergence to zero of X-motifs. The model predictions are compared with real data coming from a popular tourist destination in Gran Canaria, Spain, showing a good agreement between analytical and empirical data for the degree distribution of services. The theoretical model was validated assuming four type of perturbations in the real data.

A statistical model assuming a preferential attachment network, which is generated by adding nodes sequentially according to a few simple rules, usually describes real-life networks better than a model assuming, for example, a Bernoulli random graph, in which any two nodes have the same probability of being connected, does. Therefore, to study the propogation of "infection" across a social network, we propose a network epidemic model by combining a stochastic epidemic model and a preferential attachment model. A simulation study based on the subsequent Markov Chain Monte Carlo algorithm reveals an identifiability issue with the model parameters. Finally, the network epidemic model is applied to a set of online commissioning data., Comment: 28 pages, 9 figures, 2 tables

We study the joint degree counts in proportional attachment random graphs and find a simple representation for the limit distribution in infinite sequence space. We show weak convergence with respect to the p-norm topology for appropriate p and also provide optimal rates of convergence of the finite dimensional distributions. The results hold for models with any general initial seed graph and any fixed number of initial outgoing edges per vertex; we generate non-tree graphs using both a lumping and a sequential rule. Convergence of the order statistics and optimal rates of convergence to the maximum of the degrees is also established., Comment: 20 pages

Fractal is ubiquitous in many real-world networks. Previous researches showed that the strong disassortativity between the hub-nodes on all length scales was the key principle that gave rise to the fractal architecture of networks. Although fractal property emerged in some models, there were few researches about the fractal growth model and quantitative analyses about the strength of the disassortativity for fractal model. In this paper, we proposed a novel inverse renormalization method, named Box-based Preferential Attachment (BPA), to build the fractal growth models in which the Preferential Attachment was performed at box level. The proposed models provided a new framework that demonstrated small-world-fractal transition. Also, we firstly demonstrated the statistical characteristic of connection patterns of the hubs in fractal networks. The experimental results showed that, given proper growing scale and added edges, the proposed models could clearly show pure small-world or pure fractal or both of them. It also showed that the hub connection ratio showed normal distribution in many real-world networks. At last, the comparisons of connection pattern between the proposed models and the biological and technical networks were performed. The results gave useful reference for exploring the growth principle and for modeling the connection patterns for real-world networks.