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

Abstract

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.

44 pages, 16 figures. The primary version is to appear in Internet Mathematics (2005)

References in corpus (16)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Epidemic spreading in scale-free networks
• Lethality and centrality in protein networks
• Hierarchical organization of modularity in metabolic networks
• Classes of behavior of small-world networks
• Mean-field theory for scale-free random networks
• Modeling the Internet's Large-Scale Topology
• Measuring preferential attachment for evolving networks
• Halting viruses in scale-free networks
• Highly Optimized Tolerance: Robustness and Power Laws in Complex Systems
• The origin of degree correlations in the Internet and other networks
• Unified View of Scaling Laws for River Networks
• Some protein interaction data do not exhibit power law statistics
• Scale-rich metabolic networks: background and introduction

Cited by in corpus (3)

• Biological network comparison using graphlet degree distribution
• Some protein interaction data do not exhibit power law statistics
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency