Sublinear but Never Superlinear Preferential Attachment by Local Network Growth
arXiv:1212.0518 · doi:10.1088/1742-5468/2013/02/P02043
Abstract
We investigate a class of network growth rules that are based on a redirection algorithm wherein new nodes are added to a network by linking to a randomly chosen target node with some probability 1-r or linking to the parent node of the target node with probability r. For fixed 0<r<1, the redirection algorithm is equivalent to linear preferential attachment. We show that when r is a decaying function of the degree of the parent of the initial target, the redirection algorithm produces sublinear preferential attachment network growth. We also argue that no local redirection algorithm can produce superlinear preferential attachment.
10 pages, 3 figure, IOP style; version2: one reference corrected; version 3 (final version for JSTAT): some minor typos and citation errors fixed
References in corpus (10)
- The structure and function of complex networks
- Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
- Information dynamics shape the networks of Internet-mediated prostitution
- Preferential attachment in the protein network evolution
- Finiteness and Fluctuations in Growing Networks
- Stochastic dynamical model of a growing network based on self-exciting point process
- Scale-free networks as preasymptotic regimes of superlinear preferential attachment
- Parallel Dynamics and Computational Complexity of Network Growth Models
- Designer Nets from Local Strategies
- Random Ancestor Trees