The Magic of Networks Grown by Redirection

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.

arXiv comment12 pages, 7 figures. For a special issue on "Statistical Physics and Complex Systems" in the Indian Journal of Physics. Version 2: small changes and additional references included. Version 3: a few minor changes and one reference added

References in corpus (24)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Evolution of networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Organization of Growing Random Networks
• Social Structure of Facebook Networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Are randomly grown graphs really random?
• Degree Distributions of Growing Networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Log-Networks
• Anomalous percolating properties of growing networks
• Finiteness and Fluctuations in Growing Networks
• Generalized friendship paradox in complex networks: The case of scientific collaboration
• Structural Transitions in Dense Networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Sublinear but Never Superlinear Preferential Attachment by Local Network Growth
• Emergent Network Modularity
• Highly Dispersed Networks Generated by Enhanced Redirection
• Random Recursive Hypergraphs
• Popularity-Driven Networking
• Random Ancestor Trees