Scale Free Networks from Self-Organisation

Abstract

We show how scale-free degree distributions can emerge naturally from growing networks by using random walks for selecting vertices for attachment. This result holds for several variants of the walk algorithm and for a wide range of parameters. The growth mechanism is based on using local graph information only, so this is a process of self-organisation. The standard mean-field equations are an excellent approximation for network growth using these rules. We discuss the effects of finite size on the degree distribution, and compare analytical results to simulated networks. Finally, we generalise the random walk algorithm to produce weighted networks with power-law distributions of both weight and degree.

33 Pages. Revised discussion of finite size effects

References in corpus (23)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• The architecture of complex weighted networks
• Evolution of networks
• Analysis of weighted networks
• Network robustness and fragility: Percolation on random graphs
• Mean-field theory for scale-free random networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Intensity and coherence of motifs in weighted complex networks
• Identity and Search in Social Networks
• Organization of Growing Random Networks
• Weighted evolving networks: coupling topology and weights dynamics
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Weighted Evolving Networks
• Degree Distributions of Growing Networks
• Generic scale of the "scale-free" growing networks
• Finiteness and Fluctuations in Growing Networks
• Scale-Free Networks Generated By Random Walkers
• Vertical transmission of culture and the distribution of family names
• Complex Networks
• Knowing a network by walking on it: emergence of scaling
• Preferencial growth: exact solution of the time dependent distributions

Cited by in corpus (29)

• A Model for Social Networks
• Exploring Complex Networks through Random Walks
• Structural Transitions in Dense Networks
• Growing complex network of citations of scientific papers -- measurements and modeling
• Exact Solution for the Time Evolution of Network Rewiring Models
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Ring structures and mean first passage time in networks
• Modelling Citation Networks
• Scale-free networks as an epiphenomenon of memory
• Complex scale-free networks with tunable power-law exponent and clustering
• Emergence of Global Preferential Attachment From Local Interaction
• Identifying time dependence in network growth
• Scale-Free Networks beyond Power-Law Degree Distribution
• Preferential attachment with partial information
• Link-space formalism for network analysis
• The Emergence of Leadership in Social Networks
• Longest Path in the Price Model
• Sculplexity: Sculptures of Complexity using 3D printing
• Complex networks with scale-free nature and hierarchical modularity
• Exact Solutions for Models of Cultural Transmission and Network Rewiring
• A random walker's view of networks whose growth it shapes
• Compressibility of random walker trajectories on growing networks
• Generating Scale-free Networks with Adjustable Clustering Coefficient Via Random Walks
• Co-evolution of networks and quantum dynamics: a generalization of preferential attachment
• Modeling random walkers on growing random networks
• Random walk attachment graphs
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Are Copying and Innovation Enough?
• Traffic Dynamics of Computer Networks