Structural Transitions in Dense Networks

Abstract

We introduce an evolving network model in which a new node attaches to a randomly selected target node and also to each of its neighbors with probability $p$. The resulting network is sparse for $p<\frac{1}{2}$ and dense (average degree increasing with number of nodes $N$) for $p\ge \frac{1}{2}$. In the dense regime, individual networks realizations built by this copying mechanism are disparate and not self-averaging. Further, there is an infinite sequence of structural anomalies at $p=\frac{2}{3}$, $\frac{3}{4}$, $\frac{4}{5}$, etc., where the dependences on $N$ of the number of triangles (3-cliques), 4-cliques, undergo phase transitions. When linking to second neighbors of the target can occur, the probability that the resulting graph is complete---where all nodes are connected---is non-zero as $N\to \infty$.

5 pages, 5 figures, revtex 2-column format

References in corpus (17)

• Statistical mechanics of complex networks
• Growing Scale-Free Networks with Tunable Clustering
• Organization of Growing Random Networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• A Model for Social Networks
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Duplication-divergence model of protein interaction network
• Log-Networks
• Scale Free Networks from Self-Organisation
• Exact Solution for the Time Evolution of Network Rewiring Models
• Logarithmic growth dynamics in software networks
• Achlioptas processes are not always self-averaging
• Cliques and duplication-divergence network growth
• Emergence of Clustering in an Acquaintance Model without Homophily
• Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario

Cited by in corpus (23)

• Percolation on complex networks: Theory and application
• Sparse graphs using exchangeable random measures
• Higher-order clustering in networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• The exploration of the Adjacent Possible explains the emergence and evolution of social networks
• Dense Power-law Networks and Simplicial Complexes
• The distribution of shortest path lengths in a class of node duplication network models
• Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?
• Counterexample: scale-free networked graphs with invariable diameter and density feature
• Dense networks with scale-free feature
• Identifying time dependence in network growth
• 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
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Propinquity drives the emergence of network structure and density
• Random Recursive Hypergraphs
• 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
• Growing Hypergraphs with Preferential Linking
• Clique Densification in Networks
• Trust based attachment
• Nonreciprocal random networks and their percolation properties
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment