A scale-free network is a specific kind of complex network that has attracted attention since many real-world networks fall into this category. In scale-free networks, some nodes act as "highly connected hubs" (high degree), although most nodes are of low degree. Complex networks are the backbone of a complex system. ... In the mathematical field of graph theory the degree or valency of a vertex v is the number of edges incident to v (with loops being counted twice). ...

History

The term "scale-free" was first coined by physicist Albert-Laszlo Barabasi and his colleagues at the University of Notre Dame in Indiana. In 1998, they mapped the connectedness of the World Wide Web and found, to their surprise, that the web did not have an even distribution of connectivity (so-called "random connectivity"). Instead, a very few network nodes (called "hubs") were far more connected than other nodes. In general, they found that the probability P(k) that a node in the network connects with k other nodes was, in a given network, proportional to k^−γ. They named this kind of network connectivity "scale-free". Albert-Laszlo Barabasi is a physicist affiliated with the University of Notre Dame. ... Not to be confused with the University of Notre Dame Australia University of Notre Dame du Lac The University of Notre Dame is a Roman Catholic institution of higher learning located adjacent to South Bend, Indiana, USA. Notre Dames picturesque campus sits on 1,250 acres (5 km²) containing... State nickname: The Hoosier State Other U.S. States Capital Indianapolis Largest city Indianapolis Governor Mitch Daniels Official languages English Area 94,321 km² (38th)  - Land 92,897 km²  - Water 1,424 km² (1. ... 1998 is a common year starting on Thursday of the Gregorian calendar, and was designated the International Year of the Ocean. ...

In this form, essentially all graphs with a power law degree distribution were grouped together as "scale-free". Several revisions of this definition have been suggested. (see below) See Also: Watt In physics, a power law relationship between two scalar quantities x and y is any such that the relationship can be written as where a (the constant of proportionality) and k (the exponent of the power law) are constants. ...

Formal Definition

Although no one definition is universally accepted, In 2004 a paper published by Li et al. [1] defined a scale-free metric for a graph g as

where,

and where s_max and s_min are the maximum and minimum values of s(h) for h in the set of all graphs with an identical degree distribution to g. This gives a metric between 0 and 1, such that graphs with low S(g) are "scale-rich", and graphs with S(g) close to 1 are "scale-free".

Characteristics

Scale-free networks tend to contain centrally located, highly connected "hubs", which dramatically influences the way a network operates. For example, random node failures have very little effect on a scale-free network's connectivity or effectiveness, however deliberate attacks on such a network's hubs can dismantle a network with alarming ease. Thus, the realization that certain networks are scale-free is important to security. Computer security is the effort to create a secure computing platform, designed so that agents (users or programs) can only perform actions that have been allowed. ...

These networks also exhibit the Small world phenomenon, in which two average nodes are separated by a very small number of connections. The small world phenomenon (also known as the small world effect) is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances. ...

Scale-free networks generally have high clustering coefficients. Example clustering coefficient on an undirected graph for the shaded node i. ...

Occurrences

A multitude of real-world networks have been shown to be scale-free, including social networks, collaboration networks, protein-interaction networks, the World Wide Web, the dispersal of sexually transmitted diseases, air travel connections, many kinds of computer networks, and others. A social network is a map of the relationships between individuals, indicating the ways in which they are connected through various social familiarities ranging from casual acquaintance to close familial bonds. ... Graphic representation of the World Wide Web around Wikipedia The World Wide Web (WWW, W3, or simply Web) is an information space in which the items of interest, referred to as resources, are identified by global identifiers called Uniform Resource Locators (URL). ... Sexually-transmitted infections (STIs), also known as sexually-transmitted diseases (STDs), are diseases that are commonly transmitted between partners through some form of sexual activity, most commonly vaginal intercourse, oral sex, or anal sex. ... Computer network From Wikipedia, the free encyclopedia. ...

Barabasi also argued that there is a simple explanation for this behavior. Many networks expand through the addition of nodes to an existing network, and those nodes attach preferentially to nodes already well-connected. When this is the case a scale-free network naturally arises, however other procedures will also generate scale-free networks, such as Price's Model and vertex copying.

References

• Alberich, R., J. Miro-Julia, and F. Rossello. "Marvel Universe looks almost like a real social network".
• Barabasi, Albert-Laszlo Linked: How Everything is Connected to Everything Else
• Barabasi, Albert-Laszlo and Reka Albert. "Emergence of scaling in random networks". Science, 286:509-512, October 15, 1999.
• Li, Lun et al. Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)
• Matlis, Jan. Scale-Free Networks. ComputerWorld. November 4, 2002.
• Newman, Mark E. J. The structure and function of complex networks
• Robb, John. Scale-Free Networks and Terrorism