Structural transitions in densifying networks.

Journal article

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<1/2 and dense (average degree increasing with number of nodes N) for p≥1/2. 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=2/3, 3/4, 4/5, 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→∞.

Authors: Lambiotte, R; Krapivsky, P; Bhat, U; Redner, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: American Physical Society
• Journal: Physical Review Letters
• Volume: 117
• Issue: 21
• Pages: 218301
• Publication date: 2016-10-01
• Acceptance date: 2016-11-16
• DOI: 10.1103/physrevlett.117.218301
• EISSN: 1079-7114
• ISSN: 0031-9007
• Pmid: 27911534
• Language: English
• Keywords: physics.soc-ph; cond-mat.stat-mech