TY - JOUR
T1 - Densification and structural transitions in networks that grow by node copying
AU - Bhat, U.
AU - Krapivsky, P. L.
AU - Lambiotte, R.
AU - Redner, S.
PY - 2016/12/8
Y1 - 2016/12/8
N2 - We introduce a growing network model, the copying model, in which a new node attaches to a randomly selected target node and, in addition, independently to each of the neighbors of the target with copying probability p. When p<12, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a nonuniversal exponent whose value is determined by a transcendental equation in p. In the sparse regime, the network is "normal," e.g., the relative fluctuations in the number of links are asymptotically negligible. For p≥12, the emergent networks are dense (the average degree increases with the number of nodes N), and they exhibit intriguing structural behaviors. In particular, the N dependence of the number of m cliques (complete subgraphs of m nodes) undergoes m-1 transitions from normal to progressively more anomalous behavior at an m-dependent critical values of p. Different realizations of the network, which start from the same initial state, exhibit macroscopic fluctuations in the thermodynamic limit: absence of self-averaging. When linking to second neighbors of the target node can occur, the number of links asymptotically grows as N2 as N→∞, so that the network is effectively complete as N→∞.
AB - We introduce a growing network model, the copying model, in which a new node attaches to a randomly selected target node and, in addition, independently to each of the neighbors of the target with copying probability p. When p<12, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a nonuniversal exponent whose value is determined by a transcendental equation in p. In the sparse regime, the network is "normal," e.g., the relative fluctuations in the number of links are asymptotically negligible. For p≥12, the emergent networks are dense (the average degree increases with the number of nodes N), and they exhibit intriguing structural behaviors. In particular, the N dependence of the number of m cliques (complete subgraphs of m nodes) undergoes m-1 transitions from normal to progressively more anomalous behavior at an m-dependent critical values of p. Different realizations of the network, which start from the same initial state, exhibit macroscopic fluctuations in the thermodynamic limit: absence of self-averaging. When linking to second neighbors of the target node can occur, the number of links asymptotically grows as N2 as N→∞, so that the network is effectively complete as N→∞.
UR - http://www.scopus.com/inward/record.url?scp=85006102732&partnerID=8YFLogxK
U2 - 10.1103/PhysRevE.94.062302
DO - 10.1103/PhysRevE.94.062302
M3 - Article
AN - SCOPUS:85006102732
SN - 1539-3755
VL - 94
JO - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics
JF - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics
IS - 6
M1 - 062302
ER -