Densification and Structural Transitions in Networks that Grow by Node Copying

Abstract

We introduce a growing network model---the copying model---in which a new node attaches to a randomly selected target node and, in addition, independently to each of the neighbors of the target with copying probability $p$. When $p<\frac{1}{2}$, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a non-universal exponent whose value is determined by a transcendental equation in $p$. In the sparse regime, the network is "normal", e.g., the relative fluctuations in the number of links are asymptotically negligible. For $p\ge \frac{1}{2}$, the emergent networks are dense (the average degree increases with the number of nodes $N$) and they exhibit intriguing structural behaviors. In particular, the $N$-dependence of the number of $m$-cliques (complete subgraphs of $m$ nodes) undergoes $m-1$ transitions from normal to progressively more anomalous behavior at a $m$-dependent critical values of $p$. Different realizations of the network, which start from the same initial state, exhibit macroscopic fluctuations in the thermodynamic limit---absence of self averaging. When linking to second neighbors of the target node can occur, the number of links asymptotically grows as $N^2$ as $N\to \infty$, so that the network is effectively complete as $N\to \infty$.

arXiv comment15 pages, 12 figures

References in corpus (19)

• Fast unfolding of communities in large networks
• Finding community structure in very large networks
• Benchmark graphs for testing community detection algorithms
• Organization of Growing Random Networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Triadic closure as a basic generating mechanism of communities in complex networks
• Effect of the accelerating growth of communications networks on their structure
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Duplication-divergence model of protein interaction network
• Log-Networks
• Structural Transitions in Dense Networks
• Scale Free Networks from Self-Organisation
• Exact Solution for the Time Evolution of Network Rewiring Models
• Logarithmic growth dynamics in software networks
• The evolutionary dynamics of protein-protein interaction networks inferred from the reconstruction of ancient networks
• Achlioptas processes are not always self-averaging
• Cliques and duplication-divergence network growth
• Accelerating networks
• Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario

Cited by in corpus (15)

• Percolation on complex networks: Theory and application
• Higher-order clustering in networks
• The distribution of shortest path lengths in a class of node duplication network models
• General expression for the component size distribution in infinite configuration networks
• Dense networks with scale-free feature
• Identifying time dependence in network growth
• Proper network randomization is key to assessing social balance
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Propinquity drives the emergence of network structure and density
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• The Magic of Networks Grown by Redirection
• Clique Densification in Networks
• Trust based attachment
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment