A Caltech Library Service

Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)

Li, Lun and Alderson, David and Tanaka, Reiko and Doyle, John C. and Willinger, Walter (2005) Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version). . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Although the "scale-free: literature is large and growing, it gives neither a precise definition of scale-free graphs nor rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and verifiably false claims. In this paper, we propose a new, mathematically precise, and structural definition of the extent to which a graph is scale-free, and prove a series of results that recover many of the claimed properties while suggesting the potential for a rich and interesting theory. With this definition, scale-free (or its opposite, scale-rich) is closely related to other structural graph properties such as various notions of self-similarity (or respectively, self-dissimilarity). Scale-free graphs are also shown to be the likely outcome of random construction processes, consistent with the heuristic definitions implicit in existing random graph approaches. Our approach clarifies much of the confusion surrounding the sensational qualitative claims in the scale-free literature, and offers rigorous and quantitative alternatives.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Doyle, John C.0000-0002-1828-2486
Additional Information:The primary version of this paper is forthcoming from Internet Mathematics, 2005. The authors are indebted to several colleagues for ongoing conversations and valuable feedback, particularly David Aldous, Jean Carlson, Steven Low, Chris Magee, Matt Roughan, Stanislav Shalunov. This work was supported by Boeing, AFOSR URI 49620-01-1-0365 “Architectures for Secure and Robust Distributed Infrastructures”, the Army Institute for Collaborative Biotechnologies, NSF Award: CCF-0326635 “ITR COLLAB: Theory and Software Infrastructure for a Scalable Systems Biology,” AFOSR Award: FA9550-05-1-0032 “Bio Inspired Networks,” and Caltech’s Lee Center for Advanced Networking. Parts of this work were done at the Institute of Pure and Applied Mathematics (IPAM) at UCLA as part of the 2002 annual program on “Large-scale communication networks.”
Funding AgencyGrant Number
Boeing CorporationUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)49620-01-1-0365
Air Force Office of Scientific Research (AFOSR)FA9550-05-1-0032
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20190627-100025027
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96777
Deposited By: Tony Diaz
Deposited On:27 Jun 2019 18:54
Last Modified:03 Oct 2019 21:25

Repository Staff Only: item control page