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 (4)

• Triadic closure as a basic generating mechanism of communities in complex networks
• Scale Free Networks from Self-Organisation
• Exact Solution for the Time Evolution of Network Rewiring Models
• Emergence of Clustering in an Acquaintance Model without Homophily

Cited by in corpus (2)

• Densification and Structural Transitions in Networks that Grow by Node Copying
• The distribution of shortest path lengths in a class of node duplication network models