Complex network
Scale-free networks
Scale\-free networks
--------------------

[thumb\|An example of complex scale\-free network.A](/wiki/File:Social_Network_Analysis_Visualization.png "Social Network Analysis Visualization.png") network is called scale\-free  if its degree distribution, i.e., the probability that a node selected uniformly at random has a certain number of links (degree), follows a mathematical function called a [power law](/wiki/Power_law "Power law"). The power law implies that the degree distribution of these networks has no characteristic scale. In contrast, networks with a single well\-defined scale are somewhat similar to a lattice in that every node has (roughly) the same degree. Examples of networks with a single scale include the [Erdős–Rényi (ER) random graph](/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model "Erdős–Rényi model"), [random regular graphs](/wiki/Random_regular_graphs "Random regular graphs"), [regular lattices](/wiki/Regular_lattices "Regular lattices"), and [hypercubes](/wiki/Hypercube "Hypercube"). Some models of growing networks that produce scale\-invariant degree distributions are the [Barabási–Albert model](/wiki/Barab%C3%A1si%E2%80%93Albert_model "Barabási–Albert model") and the [fitness model](/wiki/Fitness_model_%28network_theory%29 "Fitness model (network theory)"). In a network with a scale\-free degree distribution, some vertices have a degree that is orders of magnitude larger than the average \- these vertices are often called "hubs", although this language is misleading as, by definition, there is no inherent threshold above which a node can be viewed as a hub. If there were such a threshold, the network would not be scale\-free.

Interest in scale\-free networks began in the late 1990s with the reporting of discoveries of power\-law degree distributions in real world networks such as the [World Wide Web](/wiki/World_Wide_Web "World Wide Web"), the network of [Autonomous systems](/wiki/Autonomous_system_%28Internet%29 "Autonomous system (Internet)") (ASs), some networks of Internet routers, protein interaction networks, email networks, etc. Most of these reported "power laws" fail when challenged with rigorous statistical testing, but the more general idea of heavy\-tailed degree distributions—which many of these networks do genuinely exhibit (before finite\-size effects occur) \-\- are very different from what one would expect if edges existed independently and at random (i.e., if they followed a [Poisson distribution](/wiki/Poisson_distribution "Poisson distribution")). There are many different ways to build a network with a power\-law degree distribution. The [Yule process](/wiki/Yule-Simon_distribution "Yule-Simon distribution") is a canonical generative process for power laws, and has been known since 1925\. However, it is known by many other names due to its frequent reinvention, e.g., The Gibrat principle by [Herbert A. Simon](/wiki/Herbert_A._Simon "Herbert A. Simon"), the [Matthew effect](/wiki/Matthew_effect_%28sociology%29 "Matthew effect (sociology)"), cumulative advantage and, [preferential attachment](/wiki/Preferential_attachment "Preferential attachment") by [Barabási](/wiki/Albert-L%C3%A1szl%C3%B3_Barab%C3%A1si "Albert-László Barabási") and Albert for power\-law degree distributions. Recently, [Hyperbolic Geometric Graphs](/wiki/Hyperbolic_Geometric_Graph "Hyperbolic Geometric Graph") have been suggested as yet another way of constructing scale\-free networks.

Some networks with a power\-law degree distribution (and specific other types of structure) can be highly resistant to the random deletion of vertices—i.e., the vast majority of vertices remain connected together in a giant component. Such networks can also be quite sensitive to targeted attacks aimed at fracturing the network quickly. When the graph is uniformly random except for the degree distribution, these critical vertices are the ones with the highest degree, and have thus been implicated in the spread of disease (natural and artificial) in social and communication networks, and in the spread of fads (both of which are modeled by a [percolation](/wiki/Percolation "Percolation") or [branching process](/wiki/Branching_process "Branching process")). While random graphs (ER) have an average distance of order log N between nodes, where N is the number of nodes, scale free graph can have a distance of log log N.


Why is the concept of hubs misleading in the context of scale-free networks?