Classes of Small-World Networks

Amaral, Scala, Barthelemy, Stanley

networks scaling scale-free small-world graph theory structure

@article{amaral:pnas-2000,
  title={Classes of Small-World Networks},
  author={Amaral, L.A.N. and Scala, A. and Barthelemy, M. and Stanley, H.E.},
  journal={Proceedings of the National Academy of Sciences},
  pages={11149--11152},
  year={2000},
  volume={97},
  number={21},
  publisher={National Academy of Sciences}
}

Random and regular lattice networks do not approximate real world networks

Small-world networks

• Construction: With probability p, randomly replace links of a d-dimensional lattice
• Based on p this interpolates between a regular lattice (p=0) and a random graph (p=1)
• Several key characteristics
  • Local neighborhood is largely preserved from the lattice
  • The network diameter (as average shortest path) increases only logarithmically due to the "long" links

Scale-free networks are a special case of small-world networks

• Have similarly high clustering coefficient, much larger than random networks
• Diameter increases logarithmically with the number of nodes

Shows empirical evidence from several reasonable real-world networks for three structural classes of small-world networks

• Scale-free, "characterized by connectivity distribution with a tail that decays as a power law"
• Broad-scale (or truncated scale-free), which "has a power law regime followed by a sharp cutoff, like an exponential or Gaussian decay of the tail"
• Single-scale, "characterized by a connectivity distribution with a fast decaying tail, such as exponential or Gaussian"

Scale-free property arises from preferential attachment while growing network

• New node randomly selects m other nodes to attach to, biased by their degree

Two properties of the nodes may hinder that preferential attachment

• Aging: Even well connected nodes eventually stop being connected to new nodes
• Cost/Capacity: Vertices may be constrained in how many links they may have, e.g. due to cost or physical limitations

May model in simulation by classing nodes as "active" or "inactive"

• Inactive nodes may not receive new links
• Simple rules for marking nodes as inactive mimics two previous constraints
  • Aging: At every step, each node goes inactive with some probability
    • Vertex active time decays exponentially
  • Cost/Capacity: Nodes go inactive when they reach a given number of vertices
• Both lead to dropoffs on power law decay of connectivity distribution
  • As the constraints are made tighter (high age probability, lower capacity), power law region disappears

Of interest:

• Disordered networks
• The actor network can be argued to be an economic rather than a social network...
• City growth model of Simon and Bonini: 1958, American Economics Review, 48, 607--617