Structural transitions in densifying networks

R. Lambiotte, P. L. Krapivsky, U. Bhat, S. Redner

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)


We introduce a minimal generative model for densifying networks in which a new node attaches to a randomly selected target node and also to each of its neighbors with probability p. The networks that emerge from this copying mechanism are sparse for p<12 and dense (average degree increasing with number of nodes N) for p≥12. The behavior in the dense regime is especially rich; for example, individual network realizations that are built by copying are disparate and not self-averaging. Further, there is an infinite sequence of structural anomalies at p=23, 34, 45, etc., where the N dependences 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 - all nodes are connected - is nonzero as N→∞.

Original languageEnglish
Article number218301
JournalPhysical review letters
Issue number21
Publication statusPublished - 16 Nov 2016


Dive into the research topics of 'Structural transitions in densifying networks'. Together they form a unique fingerprint.

Cite this