Densification, Emergent Modularity, and Related Mysteries of Complex Networks*

We discuss unusual features of networks that grow by: (a) node copying and (b) link redirection. In copying, a new node attaches to a randomly selected target node and to each of its neighbors with probability p. The resulting network is sparse for p<1/2 and dense (average degree increasing with number of nodes N) for p>1/2. In the dense regime, there is an infinite sequence of transitions at p = 2/3, 3/4, 4/5, etc., where the N dependences of the number of triangles (3-cliques), 4-cliques, etc., change. When second-neighbor linking to the target occurs, the resulting graph is effectively complete as N → ∞. Redirection leads to highly modular networks for redirection probability equal to 1. Individual realizations consist of almost entirely of leaves (nodes of degree 1), with a vanishingly small "nucleus" (nodes of degree greater than 1), and multiple hubs.