The Magic of Networks Grown by Redirection
Authors:
Preprint
Abstract
We highlight intriguing features of complex networks that are grown by \emph{redirection}. In this mechanism, a target node is chosen uniformly at random from the pre-existing network nodes and the new node attaches either to this initial target or to a neighbor of this target. This exceedingly simple algorithm generates preferential attachment networks in an algorithmic time that is linear in the number of network nodes $N$. Even though preferential attachment ostensibly requires \emph{global knowledge} of the network, redirection requires only \emph{local knowledge}. We also show that changing just a \emph{single} attachment rate in linear preferential attachment leads to a non-universal degree distribution. Finally, we present unexpected consequences of redirection in networks with undirected links, where highly modular and non-sparse networks arise.
Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Graph Theory2017
- Introduction to Random Graphs2015
- Social structure of Facebook networksPhysica A: Statistical Mechanics and its Applications, 2012
- A Kinetic View of Statistical Physics2010
- Random Trees2009
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- The Web as a Graph: Measurements, Models, and Methods1999
- The birth of the giant componentRandom Structures & Algorithms, 1993
- Molecular Size Distribution in Three Dimensional Polymers. I. Gelation1Journal of the American Chemical Society, 1941
- Intramolecular Reaction between Neighboring Substituents of Vinyl PolymersJournal of the American Chemical Society, 1939