Search

We suggest an underlying mechanism that governs the growth of a network of concepts, a complex network that reflects the connections between different scientific concepts based on their co-occurrences in publications. To this end, we perform empirical analysis of a network of concepts based on the preprints in physics submitted to the arXiv.org. We calculate the network characteristics and show that they cannot follow as a result of several simple commonly used network growth models. In turn, we suggest that a simultaneous account of two factors, i.e., growth by blocks and preferential selection, gives an explanation of empirically observed properties of the concepts network. Moreover, the observed structure emerges as a synergistic effect of these both factors: each of them alone does not lead to a satisfactory picture., Comment: 6 pages, 1 figure, 1 table

The constantly increasing rate at which scientific papers are published makes it difficult for researchers to identify papers that currently impact the research field of their interest. Hence, approaches to effectively identify papers of high impact have attracted great attention in the past. In this work, we present a method that seeks to rank papers based on their estimated short-term impact, as measured by the number of citations received in the near future. Similar to previous work, our method models a researcher as she explores the paper citation network. The key aspect is that we incorporate an attention-based mechanism, akin to a time-restricted version of preferential attachment, to explicitly capture a researcher's preference to read papers which received a lot of attention recently. A detailed experimental evaluation on four real citation datasets across disciplines, shows that our approach is more effective than previous work in ranking papers based on their short-term impact.

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

In this article, we discuss the random graph, Barab\'asi-Albert (BA) model, and lattice networks from a unified view point, with the parameter $\omega$ with values $1,0,-1$ characterizing these networks, respectively. The parameter is related to the preferential attachment of nodes in the networks and has different weights for the incoming and outgoing links. In addition, we discuss the correspondence between quantum statistics and the networks. Positive and negative $\omega$ correspond to Bose and Fermi-like statistics, respectively, and we obtain the distribution that connects the two. When $\omega$ is positive, it is related to the threshold of Bose-Einstein condensation (BEC). As $\omega$ decreases, the area of the BEC phase is narrowed, and disappears in the limit $\omega=0$. When $\omega$ is negative, nodes have limits in the number of attachments for newly added nodes (outgoing links), which corresponds to Fermi statistics. We also observe the Fermi degeneracy of the network. When $\omega=-1$, a standard Fermion-like network is observed. Fermion networks are realized in the cryptocurrency network "Tangle.", Comment: 19 pages, 6 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.

The zero forcing number is the minimum number of black vertices that can turn a white graph black following a single neighbour colour forcing rule. The zero forcing number provides topological information about linear algebra on graphs, with applications to the controllability of linear dynamical systems and quantum walks on graphs among other problems. Here, I investigate the zero forcing number of undirected simple graphs with a power law degree distribution $p_k\sim k^{-\gamma}$. For graphs generated by the preferential attachment model, with a diameter scaling logarithmically with the graph size, the zero forcing number approaches the graph size when $\gamma\rightarrow2$. In contrast, for graphs generated by the deactivation model, with a diameter scaling linearly with the graph size, the zero forcing number is smaller than the graph size independently of $\gamma$. Therefore the scaling of the graph diameter with the graph size is another factor determining the controllability of dynamical systems., Comment: 5 pages, 5 figures

Preferential attachment drives the evolution of many complex networks. Its analytical studies mostly consider the simplest case of a network that grows uniformly in time despite the accelerating growth of many real networks. Motivated by the observation that the average degree growth of nodes is time-invariant in empirical network data, we study the degree dynamics in the relevant class of network models where preferential attachment is combined with heterogeneous node fitness and aging. We propose a novel analytical framework based on the time-invariance of the studied systems and show that it is self-consistent only for two special network growth forms: the uniform and exponential network growth. Conversely, the breaking of such time-invariance explains the winner-takes-all effect in some model settings, revealing the connection between the Bose-Einstein condensation in the Bianconi-Barab\'{a}si model and similar gelation in superlinear preferential attachment. Aging is necessary to reproduce realistic node degree growth curves and can prevent the winner-takes-all effect under weak conditions. Our results are verified by extensive numerical simulations., Comment: 9 pages, 5 figures. Editorially approved for publication in Phys. Rev. E

We analyze a dynamic random undirected graph in which newly added vertices are connected to those already present in the graph either using, with probability p , an anti-preferential attachment mechanism or, with probability 1 − p , a preferential attachment mechanism. We derive the asymptotic degree distribution in the general case and study the asymptotic behavior of the expected degree process in the general and that of the degree process in the pure anti-preferential attachment case. Degree homogenization mainly affects convergence rates for the former case and also the limiting degree distribution in the latter. Lastly, we perform a simulative study of a variation of the introduced model allowing for anti-preferential attachment probabilities given in terms of the current maximum degree of the graph.

Discriminating between competing explanatory models as to which is more likely responsible for the growth of a network is a problem of fundamental importance for network science. The rules governing this growth are attributed to mechanisms such as preferential attachment and triangle closure, with a wealth of explanatory models based on these. These models are deliberately simple, commonly with the network growing according to a constant mechanism for its lifetime, to allow for analytical results. We use a likelihood-based framework on artificial data where the network model changes at a known point in time and demonstrate that we can recover the change point from analysis of the network. We then use real datasets and demonstrate how our framework can show the changing importance of network growth mechanisms over time.

We study two models of growing recursive trees. For both models, initially the tree only contains one vertex $u_1$ and at each time $n\geq 2$ a new vertex $u_n$ is added to the tree and its parent is chosen randomly according to some rule. In the \emph{weighted recursive tree}, we choose the parent $u_k$ of $u_n$ among $\{u_1,u_2,\dots, u_{n-1}\}$ with probability proportional to $w_k$, where $(w_n)_{n\geq1}$ is some deterministic sequence that we fix beforehand. In the \emph{affine preferential attachment tree with fitnesses}, the probability of choosing any $u_k$ is proportional to $a_k+\mathrm{deg}^{+}(u_k)$, where $\mathrm{deg}^{+}(u_k)$ denotes its current number of children, and the sequence of \emph{fitnesses} $(a_n)_{n\geq 1}$ is deterministic and chosen as a parameter of the model. We show that for any sequence $(a_n)_{n\geq 1}$, the corresponding preferential attachment tree has the same distribution as some weighted recursive tree with a \emph{random} sequence of weights (with some explicit distribution). We then prove almost sure scaling limit convergences for some statistics associated with weighted recursive trees as time goes to infinity, such as degree sequence, height, profile and also the weak convergence of some measures carried on the tree. Thanks to the connection between the two models, these results also apply to affine preferential attachment trees., Comment: 49 pages, 1 figure

In this work we prove general bounds for the diameter of random graphs generated by a preferential attachment model whose parameter is a function $f:\mathbb{N}\to[0,1]$ that drives the asymptotic proportion between the numbers of vertices and edges. These results are sharp when $f$ is a \textit{regularly varying function at infinity} with strictly negative index of regular variation~$-\gamma$. For this particular class, we prove a characterization for the diameter that depends only on~$-\gamma$. More specifically, we prove that the diameter of such graphs is of order $1/\gamma$ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of \textit{slowly varying functions} are also obtained., Comment: After referee recommendation, all results not concerning the diameter have been removed to obtain a more streamlined paper. The paper has been published at Random Structures and Algorithms under the new title

Paper proposes a model of large networks based on a random preferential attachment graph with addition of complete subgraphs (cliques). The proposed model refers to models of random graphs following the nonlinear preferential attachment rule and takes into account the possibility of {\guillemotleft}adding{\guillemotright} entire communities of nodes to the network. In the derivation of the relations that determine the vertex degree distribution, the technique of finite-difference equations describing stationary states of a graph is used. The obtained results are tested empirically (by generating large graphs), special cases correspond to known mathematical relations.

Extensive literature demonstrates how the copying of references (links) can lead to the emergence of various structural properties (e.g., power-law degree distribution and bipartite cores) in bibliographic and other similar directed networks. However, it is also well known that the copying process is incapable of mimicking the number of directed triangles in such networks; neither does it have the power to explain the obsolescence of older papers. In this paper, we propose RefOrCite, a new model that allows for copying of both the references from (i.e., out-neighbors of) as well as the citations to (i.e., in-neighbors of) an existing node. In contrast, the standard copying model (CP) only copies references. While retaining its spirit, RefOrCite differs from the Forest Fire (FF) model in ways that makes RefOrCite amenable to mean-field analysis for degree distribution, triangle count, and densification. Empirically, RefOrCite gives the best overall agreement with observed degree distribution, triangle count, diameter, h-index, and the growth of citations to newer papers., Comment: Accepted in Journal of Informetrics

We have constructed a fitness parameter, characterizing the intrinsic attractiveness for patents to be cited, from attributes of the associated inventions known at the time a patent is granted. This exogenously obtained fitness is shown to determine the temporal growth of the citation network in conjunction with mechanisms of preferential attachment and obsolescence-induced ageing that operate without reference to characteristics of individual patents. Our study opens a window on understanding quantitatively the interplay of the rich-gets-richer and fit-gets-richer paradigms that have been suggested to govern the growth dynamics of real-world complex networks., Comment: 6 pages, 3 figures, RevTex4.1, v2: minor changes, version to appear as a Rapid Communication in Phys. Rev. E

We study a general model of random dynamical simplicial complexes and derive a formula for the asymptotic degree distribution. This asymptotic formula encompasses results for a number of existing models, including random Apollonian networks and the weighted random recursive tree. It also confirms results on the scale-free nature of Complex Quantum Network Manifolds in dimensions $d > 2$, and special types of Network Geometry with Flavour models studied in the physics literature by Bianconi, Rahmede [$\mathit{Sci. Rep.} \; \mathbf{5},\text{ 13979 (2015) and }\mathit{Phys. Rev. E} \; \mathbf{93},\text{ 032315 (2016)}$]., 53 pages (main body 45 pages), 4 figures. Accepted version, to appear in Annals of Applied Probability

We investigate two asymptotic properties of a spatial preferential-attachment model introduced by E. Jacob and P. M\"orters (2013). First, in a regime of strong linear reinforcement, we show that typical distances are at most of doubly-logarithmic order. Second, we derive a large deviation principle for the empirical neighbourhood structure and express the rate function as solution to an entropy minimisation problem in the space of stationary marked point processes., Comment: 19 pages, 1 figure

We study the contact process in the regime of small infection rates on finite scale-free networks with stationary dynamics based on simultaneous updating of all connections of a vertex. We allow the update rates of individual vertices to increase with the strength of a vertex, leading to a fast evolution of the network. We first develop an approach for inhomogeneous networks with general kernel and then focus on two canonical cases, the factor kernel and the preferential attachment kernel. For these specific networks we identify and analyse four possible strategies how the infection can survive for a long time. We show that there is fast extinction of the infection when neither of the strategies is successful, otherwise there is slow extinction and the most successful strategy determines the asymptotics of the metastable density as the infection rate goes to zero. We identify the domains in which these strategies dominate in terms of phase diagrams for the exponent describing the decay of the metastable density., Comment: 40 pages, 2 figures

An important way to resolve games of conflict (snowdrift, hawk–dove, chicken) involves adopting a convention: a correlated equilibrium that avoids any conflict between aggressive strategies. Dynamic networks allow individuals to resolve conflict via their network connections rather than changing their strategy. Exploring how behavioural strategies coevolve with social networks reveals new dynamics that can help explain the origins and robustness of conventions. Here, we model the emergence of conventions as correlated equilibria in dynamic networks. Our results show that networks have the tendency to break the symmetry between the two conventional solutions in a strongly biased way. Rather than the correlated equilibrium associated with ownership norms (play aggressive at home, not away), we usually see the opposite host–guest norm (play aggressive away, not at home) evolve on dynamic networks, a phenomenon common to human interaction. We also show that learning to avoid conflict can produce realistic network structures in a way different than preferential attachment models.

A message passing algorithm is derived for recovering communities within a graph generated by a variation of the Barab\'{a}si-Albert preferential attachment model. The estimator is assumed to know the arrival times, or order of attachment, of the vertices. The derivation of the algorithm is based on belief propagation under an independence assumption. Two precursors to the message passing algorithm are analyzed: the first is a degree thresholding (DT) algorithm and the second is an algorithm based on the arrival times of the children (C) of a given vertex, where the children of a given vertex are the vertices that attached to it. Comparison of the performance of the algorithms shows it is beneficial to know the arrival times, not just the number, of the children. The probability of correct classification of a vertex is asymptotically determined by the fraction of vertices arriving before it. Two extensions of Algorithm C are given: the first is based on joint likelihood of the children of a fixed set of vertices; it can sometimes be used to seed the message passing algorithm. The second is the message passing algorithm. Simulation results are given., Comment: arXiv admin note: text overlap with arXiv:1801.06816

Zipf's law is a hallmark of several complex systems with a modular structure, such as books composed by words or genomes composed by genes. In these component systems, Zipf's law describes the empirical power law distribution of component frequencies. Stochastic processes based on a sample-space-reducing (SSR) mechanism, in which the number of accessible states reduces as the system evolves, have been recently proposed as a simple explanation for the ubiquitous emergence of this law. However, many complex component systems are characterized by other statistical patterns beyond Zipf's law, such as a sublinear growth of the component vocabulary with the system size, known as Heap's law, and a specific statistics of shared components. This work shows, with analytical calculations and simulations, that these statistical properties can emerge jointly from a SSR mechanism, thus making it an appropriate parameter-poor representation for component systems. Several alternative (and equally simple) models, for example based on the preferential attachment mechanism, can also reproduce Heaps' and Zipf's laws, suggesting that additional statistical properties should be taken into account to select the most-likely generative process for a specific system. Along this line, we will show that the temporal component distribution predicted by the SSR model is markedly different from the one emerging from the popular rich-gets-richer mechanism. A comparison with empirical data from natural language indicates that the SSR process can be chosen as a better candidate model for text generation based on this statistical property. Finally, a limitation of the SSR model in reproducing the empirical "burstiness" of word appearances in texts will be pointed out, thus indicating a possible direction for extensions of the basic SSR process., Comment: 14 pages, 4 figures

We investigate a class of growing graphs embedded into the d-dimensional torus where new vertices arrive according to a Poisson process in time, are randomly placed in space and connect to existing vertices with a probability depending on time, their spatial distance and their relative birth times. This simple model for a scale-free network is called the age-based spatial preferential attachment network and is based on the idea of preferential attachment with spatially induced clustering. We show that the graphs converge weakly locally to a variant of the random connection model, which we call the age-dependent random connection model. This is a natural infinite graph on a Poisson point process where points are marked by a uniformly distributed age and connected with a probability depending on their spatial distance and both ages. We use the limiting structure to investigate asymptotic degree distribution, clustering coefficients and typical edge lengths in the age-based spatial preferential attachment network.

In this paper, we investigate the degree profile and Gini index of random caterpillar trees (RCTs). We consider RCTs which evolve in two different manners: uniform and nonuniform. The degrees of the vertices on the central path (i.e., the degree profile) of a uniform RCT follows a multinomial distribution. For nonuniform RCTs, we focus on those growing in the fashion of preferential attachment. We develop methods based on stochastic recurrences to compute the exact expectations and the dispersion matrix of the degree variables. A generalized Pólya urn model is exploited to determine the exact joint distribution of these degree variables. We apply the methods from combinatorics to prove that the asymptotic distribution is Dirichlet. In addition, we propose a new type of Gini index to quantitatively distinguish the evolutionary characteristics of the two classes of RCTs. We present the results via several numerical experiments.

Understanding of evolutionary mechanism of online social networks is greatly significant for the development of network science. However, present researches on evolutionary mechanism of online social networks are neither deep nor clear enough. In this study, we empirically showed the essential evolution characteristics of Renren online social network. From the perspective of Pareto wealth distribution and bidirectional preferential attachment, the origin of online social network evolution is analyzed and the evolution mechanism of online social networks is explained. Then a novel model is proposed to reproduce the essential evolution characteristics which are consistent with the ones of Renren online social network, and the evolutionary analytical solution to the model is presented. The model can also well predict the ordinary power-law degree distribution. In addition, the universal bowing phenomenon of the degree distribution in many online social networks is explained and predicted by the model. The results suggest that Pareto wealth distribution and bidirectional preferential attachment can play an important role in the evolution process of online social networks and can help us to understand the evolutionary origin of online social networks. The model has significant implications for dynamic simulation researches of social networks, especially in information diffusion through online communities and infection spreading in real societies., Comment: 19 pages, 8 figures,31 references

A multi-type preferential attachment tree is introduced, and studied using general multi-type branching processes. For the $p$-type case we derive a framework for studying the tree where a type $i$ vertex generates new type $j$ vertices with rate $w_{ij}(n_1,n_2,\ldots, n_p)$ where $n_k$ is the number of type $k$ vertices previously generated by the type $i$ vertex, and $w_{ij}$ is a non-negative function from $\mathbb{N}^p$ to $\mathbb{R}$. The framework is then used to derive results for trees with more specific attachment rates. In the case with linear preferential attachment---where type $i$ vertices generate new type $j$ vertices with rate $w_{ij}(n_1,n_2,\ldots, n_p)=\gamma_{ij}(n_1+n_2+\dots +n_p)+\beta_{ij}$, where $\gamma_{ij}$ and $\beta_{ij}$ are positive constants---we show that under mild regularity conditions on the parameters $\{\gamma_{ij}\}, \{\beta_{ij}\}$ the asymptotic degree distribution of a vertex is a power law distribution. The asymptotic composition of the vertex population is also studied.

Continuous-time branching processes describe the evolution of a population whose individuals generate a random number of children according to a birth process. Such branching processes can be used to understand preferential attachment models in which the birth rates are linear functions. We are motivated by citation networks, where power-law citation counts are observed as well as aging in the citation patterns. To model this, we introduce fitness and age-dependence in these birth processes. The multiplicative fitness moderates the rate at which children are born, while the aging is integrable, so that individuals receives a finite number of children in their lifetime. We show the existence of a limiting degree distribution for such processes. In the preferential attachment case, where fitness and aging are absent, this limiting degree distribution is known to have power-law tails. We show that the limiting degree distribution has exponential tails for bounded fitnesses in the presence of integrable aging, while the power-law tail is restored when integrable aging is combined with fitness with unbounded support with at most exponential tails. In the absence of integrable aging, such processes are explosive., Comment: 41 pages, 10 figures

In this article, we consider the problem of testing whether a graph has bounded arboricity. The class of graphs with bounded arboricity includes many important graph families (e.g., planar graphs and randomly generated preferential attachment graphs). Graphs with bounded arboricity have been studied extensively in the past, particularly because for many problems, they allow for much more efficient algorithms and/or better approximation ratios. We present a tolerant tester in the general-graphs model. The general-graphs model allows access to degree and neighbor queries, and the distance is defined with respect to the actual number of edges. Namely, we say that a graph G is ϵ-close to having arboricity α if by removing at most an ϵ-fraction of its edges, we can obtain a graph G ′ that has arboricity α, and otherwise we say that G is ϵ-far. Our algorithm distinguishes between graphs that are ϵ-close to having arboricity α and graphs that are c ṡ ϵ-far from having arboricity 3α, where c is an absolute small constant. The query complexity and running time of the algorithm are Õ ( n / ϵ√ m ) + (1 / ϵ) O (log(1/ϵ)) , where n denotes the number of vertices and m denotes the number of edges (we use the notation Õ to hide poly-logarithmic factors in n ). In terms of the dependence on n and m , this bound is optimal up to poly-logarithmic factors since Ω( n / √ m ) queries are necessary.

International audience; Network growth models that embody principles such as preferential attachment and local attachment rules have received much attention over the last decade. Among various approaches, random walks have been leveraged to capture such principles. In this paper we consider the No Restart Random Walk (NRRW) model where a walker builds its graph (tree) while moving around. In particular, the walker takes s steps (a parameter) on the current graph. A new node with degree one is added to the graph and connected to the node currently occupied by the walker. The walker then resumes, taking another s steps, and the process repeats. We analyze this process from the perspective of the walker and the network, showing a fundamental dichotomy between transience and recurrence for the walker as well as power law and exponential degree distribution for the network. More precisely, we prove the following results: s = 1: the random walk is transient and the degree of every node is bounded from above by a geometric distribution. s even: the random walk is recurrent and the degree of non-leaf nodes is bounded from below by a power law distribution with exponent decreasing in s. We also provide a lower bound for the fraction of leaves in the graph, and for s = 2 our bound implies that the fraction of leaves goes to one as the graph size goes to infinity. NRRW exhibits an interesting mutual dependency between graph building and random walking that is fundamentally influenced by the parity of s. Understanding this kind of coupled dynamics is an important step towards modeling more realistic network growth processes.

In many social complex systems, in which agents are linked by non-linear interactions, the history of events strongly influences the whole network dynamics. However, a class of "commonly accepted beliefs" seems rarely studied. In this paper, we examine how the growth process of a (social) network is influenced by past circumstances. In order to tackle this cause, we simply modify the well known preferential attachment mechanism by imposing a time dependent kernel function in the network evolution equation. This approach leads to a fractional order Barabasi-Albert (BA) differential equation, generalizing the BA model. Our results show that, with passing time, an aging process is observed for the network dynamics. The aging process leads to a decay for the node degree values, thereby creating an opposing process to the preferential attachment mechanism. On one hand, based on the preferential attachment mechanism, nodes with a high degree are more likely to absorb links; but, on the other hand, a node's age has a reduced chance for new connections. This competitive scenario allows an increased chance for younger members to become a hub. Simulations of such a network growth with aging constraint confirm the results found from solving the fractional BA equation. We also report, as an exemplary application, an investigation of the collaboration network between Hollywood movie actors. It is undubiously shown that a decay in the dynamics of their collaboration rate is found, - even including a sex difference. Such findings suggest a widely universal application of the so generalized BA model., Comment: 13 pages; 5 figures; 71 references; as prepared for submission to PLOS ONE

We consider linear preferential attachment trees, and show that they can be regarded as random split trees in the sense of Devroye (1999), although with infinite potential branching. In particular, this applies to the random recursive tree and the standard preferential attachment tree. An application is given to the sum over all pairs of nodes of the common number of ancestors., Comment: 18 pages

Recent years have seen tremendous growth of many online social networks such as Facebook, LinkedIn and MySpace. People connect to each other through these networks forming large social communities providing researchers rich datasets to understand, model and predict social interactions and behaviors. New contacts in these networks can be formed due to an individual's demographic attributes such as age group, gender, geographic location, or due to a network's structural dynamics such as triadic closure and preferential attachment, or a combination of both demographic and structural characteristics. A number of network generation models have been proposed in the last decade to explain the structure, evolution and processes taking place in different types of networks, and notably social networks. Network generation models studied in the literature primarily consider structural properties, and in some cases an individual's demographic profile in the formation of new social contacts. These models do not present a mechanism to combine both structural and demographic characteristics for the formation of new links. In this paper, we propose a new network generation algorithm which incorporates both these characteristics to model network formation. We use different publicly available Facebook datasets as benchmarks to demonstrate the correctness of the proposed network generation model. The proposed model is flexible and thus can generate networks with varying demographic and structural properties., Comment: arXiv admin note: substantial text overlap with arXiv:1311.3508

Complex networks in different areas exhibit degree distributions with a heavy upper tail. A preferential attachment mechanism in a growth process produces a graph with this feature. We herein investigate a variant of the simple preferential attachment model, whose modifications are interesting for two main reasons: to analyze more realistic models and to study the robustness of the scale-free behavior of the degree distribution. We introduce and study a model which takes into account two different attachment rules: a preferential attachment mechanism (with probability 1 − p ) that stresses the rich get richer system, and a uniform choice (with probability p ) for the most recent nodes, i.e. the nodes belonging to a window of size w to the left of the last born node. The latter highlights a trend to select one of the last added nodes when no information is available. The recent nodes can be either a given fixed number or a proportion ( α n ) of the total number of existing nodes. In the first case, we prove that this model exhibits an asymptotically power-law degree distribution. The same result is then illustrated through simulations in the second case. When the window of recent nodes has a constant size, we herein prove that the presence of the uniform rule delays the starting time from which the asymptotic regime starts to hold. The mean number of nodes of degree k and the asymptotic degree distribution are also determined analytically. Finally, a sensitivity analysis on the parameters of the model is performed.

We study a class of branching processes in which a population consists of immortal individuals equipped with a fitness value. Individuals produce offspring with a rate given by their fitness, and offspring may either belong to the same family, sharing the fitness of their parent, or be founders of new families, with a fitness sampled from a fitness distribution. Examples that can be embedded in this class are stochastic house-of-cards models, urn models with reinforcement, and the preferential attachment tree of Bianconi and Barabasi. Our focus is on the case when the fitness distribution has bounded support and regularly varying tail at the essential supremum. In this case there exists a condensation phase, in which asymptotically a proportion of mass in the empirical fitness distribution of the overall population condenses in the maximal fitness value. Our main results describe the asymptotic behaviour of the size and fitness of the largest family at a given time. In particular, we show that as time goes to infinity the size of the largest family is always negligible compared to the overall population size. This implies that condensation, when it arises, is non-extensive and emerges as a collective effort of several families none of which can create a condensate on its own. Our result disproves claims made in the physics literature in the context of preferential attachment trees., Comment: 1 figure

Preferential attachment models have been widely studied in complex networks, because they can explain the formation of many networks like social networks, citation networks, power grids, and biological networks, to name a few. Motivated by the application of key predistribution in wireless sensor networks (WSN), we initiate the study of preferential attachment with degree bound. Our paper has two important contributions to two different areas. The first is a contribution in the study of complex networks. We propose preferential attachment model with degree bound for the first time. In the normal preferential attachment model, the degree distribution follows a power law, with many nodes of low degree and a few nodes of high degree. In our scheme, the nodes can have a maximum degree $d_{\max}$, where $d_{\max}$ is an integer chosen according to the application. The second is in the security of wireless sensor networks. We propose a new key predistribution scheme based on the above model. The important features of this model are that the network is fully connected, it has fewer keys, has larger size of the giant component and lower average path length compared with traditional key predistribution schemes and comparable resilience to random node attacks. We argue that in many networks like key predistribution and Internet of Things, having nodes of very high degree will be a bottle-neck in communication. Thus, studying preferential attachment model with degree bound will open up new directions in the study of complex networks, and will have many applications in real world scenarios., Comment: Published in the proceedings of IEEE International Conference on Advanced Information Networking and Applications (AINA) 2016

In this paper, we analyze assortativity of preferential attachment models. We deal with a wide class of preferential attachment models (PA-class). It was previously shown that the degree distribution in all models of the PA-class follows a power law. Also, the global and the average local clustering coefficients were analyzed. We expand these results by analyzing the assortativity property of the PA-class of models. Namely, we analyze the behavior of $d_{nn}(d)$ which is the average degree of a neighbor of a vertex of degree $d$.

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$, and connected to each previous vertex $u \leq t$ with probability $\frac{d_u(t)}{t}$ where $d_u(t)$ is the degree of $u$ at time $t$. We analyse the graph obtained as the infinite limit of this process, and show that so 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., Comment: arXiv admin note: text overlap with arXiv:1502.05618

A dynamic model for a random network evolving in continuous time is defined, where new vertices are born and existing vertices may die. The fitness of a vertex is defined as the accumulated in-degree of the vertex and a new vertex is connected to an existing vertex with probability proportional to a function b of the fitness of the existing vertex. Furthermore, a vertex dies at a rate given by a function d of its fitness. Using results from the theory of general branching processes, an expression for the asymptotic empirical fitness distribution {pk} is derived and analyzed for a number of specific choices of b and d. When b(i) = i + α and d(i) = β, that is, linear preferential attachment for the newborn and random deaths, then pk ∼ k-(2+α). When b(i) = i + 1 and d(i) = β(i + 1), with β < 1, then pk ∼ (1 + β)−k, that is, if the death rate is also proportional to the fitness, then the power-law distribution is lost. Furthermore, when b(i) = i + 1 and d(i) = β(i + 1)γ, with β, γ < 1, then logpk ∼ -kγ, a stretched exponential distribution. The momentaneous in-degrees are also studied and simulations suggest that their behaviour is qualitatively similar to that of the fitnesses.

In this paper, we analyze the local clustering coefficient of preferential attachment models. A general approach to preferential attachment was introduced in earlier, where a wide class of models (PA-class) was defined in terms of constraints that are sufficient for the study of the degree distribution and the clustering coefficient. It was previously shown that the degree distribution in all models of the PA-class follows a power law. Also, the global clustering coefficient was analyzed and a lower bound for the average local clustering coefficient was obtained. We expand the results by analyzing the local clustering coefficient for the PA-class of models. Namely, we analyze the behavior of C(d) which is the average local clustering for the vertices of degree d.

Prediction and control of network dynamics are grand-challenge problems in network science. The lack of understanding of fundamental laws driving the dynamics of networks is among the reasons why many practical problems of great significance remain unsolved for decades. Here we study the dynamics of networks evolving according to preferential attachment, known to approximate well the large-scale growth dynamics of a variety of real networks. We show that this dynamics is Hamiltonian, thus casting the study of complex networks dynamics to the powerful canonical formalism, in which the time evolution of a dynamical system is described by Hamilton's equations. We derive the explicit form of the Hamiltonian that governs network growth in preferential attachment. This Hamiltonian turns out to be nearly identical to graph energy in the configuration model, which shows that the ensemble of random graphs generated by preferential attachment is nearly identical to the ensemble of random graphs with scale-free degree distributions. In other words, preferential attachment generates nothing but random graphs with power-law degree distribution. The extension of the developed canonical formalism for network analysis to richer geometric network models with non-degenerate groups of symmetries may eventually lead to a system of equations describing network dynamics at small scales., Comment: 16 pages, 5 figures

We consider a directed Barab��si-Albert scale-free network model with symmetric preferential attachment with the same in- and out-degrees, and study emergence of sparsely synchronized rhythms for a fixed attachment degree in an inhibitory population of fast spiking Izhikevich interneurons. For a study on the fast sparsely synchronized rhythms, we fix $J$ (synaptic inhibition strength) at a sufficiently large value, and investigate the population states by increasing $D$ (noise intensity). For small $D$, full synchronization with the same population-rhythm frequency $f_p$ and mean firing rate (MFR) $f_i$ of individual neurons occurs, while for sufficiently large $D$ partial synchronization with $f_p > {\langle f_i \rangle}$ ($\langle f_i \rangle$: ensemble-averaged MFR) appears due to intermittent discharge of individual neurons; particularly, the case of $f_p > 4 {\langle f_i \rangle}$ is referred to as sparse synchronization. Only for the partial and sparse synchronization, MFRs and contributions of individual neuronal dynamics to population synchronization change depending on their degrees, unlike the case of full synchronization. Consequently, dynamics of individual neurons reveal the inhomogeneous network structure for the case of partial and sparse synchronization, which is in contrast to the case of statistically homogeneous random graphs and small-world networks. Finally, we investigate the effect of network architecture on sparse synchronization in the following three cases: (1) variation in the degree of symmetric attachment (2) asymmetric preferential attachment of new nodes with different in- and out-degrees (3) preferential attachment between pre-existing nodes (without addition of new nodes). In these three cases, both relation between network topology and sparse synchronization and contributions of individual dynamics to the sparse synchronization are discussed., 54 pages, 13 figures. arXiv admin note: text overlap with arXiv:1403.1034

In this paper, we propose a growing random complex network model, which we call context dependent preferential attachment model (CDPAM), when the preference of a new node to get attached to old nodes is determined by the local and global property of the old nodes. We consider that local and global properties of a node as the degree and relative average degree of the node respectively. We prove that the degree distribution of complex networks generated by CDPAM follow power law with exponent lies in the interval [2, 3] and the expected diameter grows logarithmically with the size of new nodes added in the initial small network. Numerical results show that the expected diameter stabilizes when alike weights to the local and global properties are assigned by the new nodes. Computing various measures including clustering coefficient, assortativity, number of triangles, algebraic connectivity, spectral radius, we show that the proposed model replicates properties of real networks better than BA model for all these measures when alike weights are given to local and global property. Finally, we observe that the BA model is a limiting case of CDPAM when new nodes tend to give large weight to the local property compared to the weight given to the global property during link formation., Comment: 07 pages

We prove the existence of a large complete subgraph w.h.p. in a preferential attachment random graph process with an edge-step. That is, we prove that the random graph $G_{t}$ produced by the so-called GLP model at time $t$ contains a complete subgraph of order $t^\alpha$, where $\alpha = (1-\varepsilon)\frac{1-p}{2-p}$, $\varepsilon$ is any number such that $0, Comment: 14 pages. Updated version

Inspired by empirical data on real world complex networks, the last few years have seen an explosion in proposed generative models to understand and explain observed properties of real world networks, including power law degree distribution and "small world" distance scaling. In this context, a natural question is the phenomenon of {\it change point}, understanding how abrupt changes in parameters driving the network model change structural properties of the network. We study this phenomenon in one popular class of dynamically evolving networks: preferential attachment models. We derive asymptotic properties of various functionals of the network including the degree distribution as well as maximal degree asymptotics, in essence showing that the change point does effect the degree distribution but does {\bf not} change the degree exponent. This provides further evidence for long range dependence and sensitive dependence of the evolution of the process on the initial evolution of the process in such self-reinforced systems. We then propose an estimator for the change point and prove consistency properties of this estimator. The methodology developed highlights the effect of the non-ergodic nature of the evolution of the network on classical change point estimators., Comment: 35 pages, 6 figures

Many real networks such as the World Wide Web, financial, biological, citation and social networks have a power-law degree distribution. Networks with this feature are also called scale-free. Several models for producing scale-free networks have been obtained by now and most of them are based on the preferential attachment approach. We will offer the model with another scale-free property explanation. The main idea is to approximate the network's adjacency matrix by multiplication of the matrices $V$ and $V^T$, where $V$ is the matrix of vertices' latent features. This approach is called matrix factorization and is successfully used in the link prediction problem. To create a generative model of scale-free networks we will sample latent features $V$ from some probabilistic distribution and try to generate a network's adjacency matrix. Entries in the generated matrix are dot products of latent features which are real numbers. In order to create an adjacency matrix, we approximate entries with the Boolean domain $\{0, 1\}$. We have incorporated the threshold parameter $\theta$ into the model for discretization of a dot product. Actually, we have been influenced by the geographical threshold models which were recently proven to have good results in a scale-free networks generation. The overview of our results is the following. First, we will describe our model formally. Second, we will tune the threshold $\theta$ in order to generate sparse growing networks. Finally, we will show that our model produces scale-free networks with the fixed power-law exponent which equals two. In order to generate oriented networks with tunable power-law exponents and to obtain other model properties, we will offer different modifications of our model. Some of our results will be demonstrated using computer simulation.

Simple growth mechanisms have been proposed to explain the emergence of seemingly universal network structures. The widely-studied model of preferential attachment assumes that new nodes are more likely to connect to highly connected nodes. Preferential attachment explains the emergence of scale-free degree distributions within complex networks. Yet, it is incompatible with many network systems, particularly bipartite systems in which two distinct types of agents interact. For example, the addition of new links in a host-parasite system corresponds to the infection of hosts by parasites. Increasing connectivity is beneficial to a parasite and detrimental to a host. Therefore, the overall network connectivity is subject to conflicting pressures. Here, we propose a stochastic network growth model of conflicting attachment, inspired by a particular kind of parasite-host interactions: that of viruses interacting with microbial hosts. The mechanism of network growth includes conflicting preferences to network density as well as costs involved in modifying the network connectivity according to these preferences. We find that the resulting networks exhibit realistic patterns commonly observed in empirical data, including the emergence of nestedness, modularity, and nested-modular structures that exhibit both properties. We study the role of conflicting interests in shaping network structure and assess opportunities to incorporate greater realism in linking growth process to pattern in systems governed by antagonistic and mutualistic interactions., Comment: 24 pages, 7 figures

Since their inception about a decade ago, dynamic networks which adapt to the state of the nodes have attracted much attention. One simple case of such an adaptive dynamics is a model of social networks in which individuals are typically comfortable with a certain number of contacts, i.e., preferred degrees. This paper is partly a review of earlier work of single homogeneous systems and ones with two interacting networks, and partly a presentation of some new results. In general, the dynamics does not obey detailed balance and the stationary distributions are not known analytically. A particular limit of the latter is a system of extreme introverts and extroverts - the XIE model. Remarkably, in this case, the detailed balance condition is satisfied, the exact distribution and an effective Hamiltonian can be found explicitly. Further, the model exhibits a phase transition in which the total number of links in the system - a macroscopically interesting quantity, displays an extreme Thouless effect. We show that in the limit of large populations and away from the transition, the model reduces to one with non-interacting agents of the majority subgroup. We determine the nature of fluctuations near the transition. We also introduce variants of the model where the agents show preferential attachment or detachment. There are significant changes to the degree distributions in the steady state, some of which can be understood by theoretical arguments and some remain to be explored. Many intriguing questions are posed, providing some food for thought and avenues for future research., Comment: 38 pages, 18 figures (some with multiple parts), to appear in JSTAT

Spectra of real world networks exhibit properties which are different from the random networks. One such property is the existence of a very high degeneracy at zero eigenvalues. In this work, we provide possible reasons behind occurrence of the zero degeneracy in various networks spectra. Comparison of zero degeneracy in protein-protein interaction networks of six different species and in their corresponding model networks sheds light in understanding the evolution of complex biological systems., Comment: 5 pages, 3 figures

We study the influence of the seed graph in the preferential attachment model, focusing on the case of trees. We first show that the seed has no effect from a weak local limit point of view. On the other hand, we conjecture that different seeds lead to different distributions of limiting trees from a total variation point of view. We take a first step in proving this conjecture by showing that seeds with different degree profiles lead to different limiting distributions for the (appropriately normalized) maximum degree, implying that such seeds lead to different (in total variation) limiting trees.

Centrality of a node measures its relative importance within a network. There are a number of applications of centrality, including inferring the influence or success of an individual in a social network, and the resulting social network dynamics. While we can compute the centrality of any node in a given network snapshot, a number of applications are also interested in knowing the potential importance of an individual in the future. However, current centrality is not necessarily an effective predictor of future centrality. While there are different measures of centrality, we focus on degree centrality in this paper. We develop a method that reconciles preferential attachment and triadic closure to capture a node's prominence profile. We show that the proposed node prominence profile method is an effective predictor of degree centrality. Notably, our analysis reveals that individuals in the early stage of evolution display a distinctive and robust signature in degree centrality trend, adequately predicted by their prominence profile. We evaluate our work across four real-world social networks. Our findings have important implications for the applications that require prediction of a node's future degree centrality, as well as the study of social network dynamics., Comment: arXiv admin note: text overlap with arXiv:1409.0285

We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three-fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank-based selection model, the Aiello-Chung-Lu models, the generalized linear preference model, directed scale-free graphs, the Cooper-Frieze model, and random unordered increasing $k$-trees. Our results shed light on why the small-world phenomenon is observed in so many real-world graphs., Comment: 30 pages

We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global "balancedness" properties of such trees. Our paper follows recent results on the same question for the preferential attachment model., Comment: 26 pages, 5 figures