Structural transitions in densifying networks

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

Research output: Contribution to journalArticle

1 Downloads (Pure)

Abstract

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
Volume117
Issue number21
DOIs
Publication statusPublished - 16 Nov 2016

Fingerprint

triangles
anomalies

Cite this

Lambiotte, R. ; Krapivsky, P. L. ; Bhat, U. ; Redner, S. / Structural transitions in densifying networks. In: Physical review letters. 2016 ; Vol. 117, No. 21.
@article{139807b189c940eda8f589c3c510bb7e,
title = "Structural transitions in densifying networks",
abstract = "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→∞.",
author = "R. Lambiotte and Krapivsky, {P. L.} and U. Bhat and S. Redner",
year = "2016",
month = "11",
day = "16",
doi = "10.1103/PhysRevLett.117.218301",
language = "English",
volume = "117",
journal = "Physical review letters",
issn = "0031-9007",
publisher = "American Physical Society",
number = "21",

}

Structural transitions in densifying networks. / Lambiotte, R.; Krapivsky, P. L.; Bhat, U.; Redner, S.

In: Physical review letters, Vol. 117, No. 21, 218301, 16.11.2016.

Research output: Contribution to journalArticle

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

VL - 117

JO - Physical review letters

JF - Physical review letters

SN - 0031-9007

IS - 21

M1 - 218301

ER -