Ideas Seminar: Sid Redner, Boston University and Sante Fe Institute

Title: The Magic of Redirection and Copying in Complex Networks

Abstract: We discuss unusual features of networks that grow by: (a) link redirection and (b) node copying.  Building on the random recursive tree, redirection naturally leads to linear preferential attachment, in spite of the locality of the growth mechanism.  For an isotropic network, redirection leads to a highly modular structure in which individual realizations consist of almost entirely of leaves (nodes of degree 1), with a vanishingly small “core” (nodes of degree greater than 1), and multiple hubs.  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.  Some open problems in these areas will be outlined.