2006/07/31 by Petter Holme
Mathematics · Physics and Astronomy · #Average path length #Combinatorics #Complex Network Analysis Techniques #Complex network #Computer science #Degree (music) #Degree distribution #Graph #Graph theory and applications #Mathematics #Path (computing) #Physics #Power law #Scale (ratio) #Scale-free network #Scaling #Shortest path problem #Small-world network #Statistical physics #Statistics #Stochastic processes and statistical mechanics #cond-mat.dis-nn
paper · pdf · doi:10.1016/j.physa.2006.11.024
published as Physica A 377, 315-322 (2007) · errors fixed, one new figure, to appear in Physica A
arxiv created 2006/11/07 · openalex publication_date 2006/12/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Recently there have been a tremendous interest in models of networks with a power-law distribution of degree -- so called "scale-free networks." It has been observed that such networks, normally, have extremely short path-lengths, scaling logarithmically or slower with system size. As en exotic and unintuitive example we propose a simple stochastic model capable of generating scale-free networks with linearly scaling distances. Furthermore, by tuning a parameter the model undergoes a phase transition to a regime with extremely short average distances, apparently slower than log log N (which we call a hypersmall-world regime). We characterize the degree-degree correlation and clustering properties of this class of networks.