title: Densification and structural transitions in networks that grow by node copying.
abstract: 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<1/2, 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≥1/2, 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 N^{2} as N→∞, so that the network is effectively complete as N→∞.
authors.affiliation: Department of Physics, Boston University, Boston, Massachusetts 02215, USA and Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA.
authors.forename: U
authors.initials: U
authors.lastname: Bhat
authors.affiliation: Department of Physics, Boston University, Boston, Massachusetts 02215, USA.
authors.forename: P L
authors.initials: PL
authors.lastname: Krapivsky
authors.affiliation: naXys, Namur Center for Complex Systems, University of Namur, rempart de la Vierge 8, B 5000 Namur, Belgium.
authors.forename: R
authors.initials: R
authors.lastname: Lambiotte
authors.affiliation: Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA.
authors.forename: S
authors.initials: S
authors.lastname: Redner