The Magic of Networks Grown by Redirection
Authors:
- P. L. KrapviskyPKP. L. Krapvisky
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 29 references indexed in Scilit:
- Graph Theory2017
- Introduction to Random Graphs2015
- Generalized friendship paradox in complex networks: The case of scientific collaborationScientific Reports, 2014
- Social structure of Facebook networksPhysica A: Statistical Mechanics and its Applications, 2012
- A Kinetic View of Statistical Physics2010
- Random ancestor treesJournal of Statistical Mechanics: Theory and Experiment, 2010
- Random Trees2009
- Finiteness and fluctuations in growing networksJournal of Physics A: General Physics, 2002
- Evolution of networksAdvances in Physics, 2002
- The Web as a Graph: Measurements, Models, and Methods1999