TY - JOUR
T1 - Structural transitions in densifying networks
AU - Lambiotte, R.
AU - Krapivsky, P. L.
AU - Bhat, U.
AU - Redner, S.
PY - 2016/11/16
Y1 - 2016/11/16
N2 - 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→∞.
AB - 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→∞.
UR - http://www.scopus.com/inward/record.url?scp=84995948317&partnerID=8YFLogxK
U2 - 10.1103/PhysRevLett.117.218301
DO - 10.1103/PhysRevLett.117.218301
M3 - Article
AN - SCOPUS:84995948317
SN - 0031-9007
VL - 117
JO - Physical review letters
JF - Physical review letters
IS - 21
M1 - 218301
ER -