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

@misc{citeulike:355384, 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.}, author = {Li, Lun and Alderson, David and Tanaka, Reiko and Doyle, John C. and Willinger, Walter }, citeulike-article-id = {355384}, eprint = {cond-mat/0501169}, keywords = {free, graphs, powerlaw, scale}, month = {Oct}, posted-at = {2007-04-14 02:26:43}, priority = {0}, title = {Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)}, url = {http://arxiv.org/abs/cond-mat/0501169}, year = {2005} }

TY - ELEC ID - citeulike:355384 L3 - citeulike-article-id:355384 TI - Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version) N2 - 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. KW - free KW - graphs KW - powerlaw KW - scale AU - Li, Lun AU - Alderson, David AU - Tanaka, Reiko AU - Doyle, John AU - Willinger, Walter PY - 2005/Oct/18/ UR - http://arxiv.org/abs/cond-mat/0501169 ER -