Scale-free network
Encyclopedia
A scale-free network is a network
whose degree distribution
follows a power law
, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as
where
is a normalization constant and 
is a parameter whose value is typically in the range 2 < 
< 3, although occasionally it may lie outside these bounds.
showed in 1965 that the number of links to papers—i.e., the number of citations they receive—had a heavy-tailed distribution
following a Pareto distribution or power law
, and thus that the citation network is scale-free. He did not however use the term "scale-free network", which was not coined until some decades later. In a later paper in 1976, Price also proposed a mechanism to explain the occurrence of power laws in citation networks, which he called "cumulative advantage" but which is today more commonly known under the name preferential attachment
.
Recent interest in scale-free networks started in 1999 with work by Albert-László Barabási
and colleagues at the University of Notre Dame
who mapped the topology of a portion of the World Wide Web, finding that some nodes, which they called "hubs", had many more connections than others and that the network as a whole had a power-law distribution of the number of links connecting to a node. After finding that a few other networks, including some social and biological networks, also had heavy-tailed degree distributions, Barabási and collaborators coined the term "scale-free network" to describe the class of networks that exhibit a power-law degree distribution. Amaral et al. showed that most of the real-world networks can be classified into two large categories according to the decay of degree distribution P(k) for large k.
Barabási and Albert proposed a generative mechanism to explain the appearance of power-law distributions, which they called "preferential attachment
" and which is essentially the same as that proposed by Price. Analytic solutions for this mechanism (also similar to the solution of Price) were presented in 2000 by Dorogovtsev, Mendes
and Samukhin and independently by Krapivsky, Redner
, and Leyvraz, and later rigorously proved by mathematician Béla Bollobás
. Notably, however, this mechanism only produces a specific subset of networks in the scale-free class, and many alternative mechanisms have been discovered since.
The history of scale-free networks also includes some disagreement. On an empirical level, the scale-free nature of several networks has been called into question. For instance, the three brothers Faloutsos believed that the Internet
had a power law degree distribution on the basis of traceroute
data; however, it has been suggested that this is a layer 3
illusion created by routers, which appear as high-degree nodes while concealing the internal layer 2
structure of the ASes
they interconnect.
On a theoretical level, refinements to the abstract definition of scale-free have been proposed. For example, Li et al. (2005) recently offered a potentially more precise "scale-free metric". Briefly, let g be a graph with edge-set ε, and let the degree (number of edges) at a vertex i be
. Define
This is maximized when high-degree nodes are connected to other high-degree nodes. Now define
where smax is the maximum value 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". This definition captures the notion of self-similarity
implied in the name "scale-free".
The most notable characteristic in a scale-free network is the relative commonness of vertices with a degree that greatly exceeds the average. The highest-degree nodes are often called "hubs", and are thought to serve specific purposes in their networks, although this depends greatly on the domain.
The scale-free property strongly correlates with the network's robustness to failure. It turns out that the major hubs are closely followed by smaller ones. These ones, in turn, are followed by other nodes with an even smaller degree and so on. This hierarchy allows for a fault tolerant behavior. If failures occur at random and the vast majority of nodes are those with small degree, the likelihood that a hub would be affected is almost negligible. Even if a hub-failure occurs, the network will generally not lose its connectedness
, due to the remaining hubs. On the other hand, if we choose a few major hubs and take them out of the network, the network is turned into a set of rather isolated graphs. Thus, hubs are both a strength and a weakness of scale-free networks. These properties have been studied analytically using percolation theory
by Cohen et al. and by Callaway et al.
Another important characteristic of scale-free networks is the clustering coefficient
distribution, which decreases as the node degree increases. This distribution also follows a power law. This implies that the low-degree nodes belong to very dense sub-graphs and those sub-graphs are connected to each other through hubs. Consider a social network in which nodes are people and links are acquaintance relationships between people. It is easy to see that people tend to form communities, i.e., small groups in which everyone knows everyone (one can think of such community as a complete graph
). In addition, the members of a community also have a few acquaintance relationships to people outside that community. Some people, however, are connected to a large number of communities (e.g., celebrities, politicians). Those people may be considered the hubs responsible for the small-world phenomenon.
At present, the more specific characteristics of scale-free networks vary with the generative mechanism used to create them. For instance, networks generated by preferential attachment typically place the high-degree vertices in the middle of the network, connecting them together to form a core, with progressively lower-degree nodes making up the regions between the core and the periphery. The random removal of even a large fraction of vertices impacts the overall connectedness of the network very little, suggesting that such topologies could be useful for security
, while targeted attacks destroys the connectedness very quickly. Other scale-free networks, which place the high-degree vertices at the periphery, do not exhibit these properties. Similarly, the clustering coefficient of scale-free networks can vary significantly depending on other topological details.
A final characteristic concerns the average distance between two vertices in a network. As with most disordered networks, such as the small world network model, this distance is very small relative to a highly ordered network such as a lattice graph
. Notably, an uncorrelated power-law graph having 2 < γ < 3 will have ultrasmall diameter d ~ ln ln N where N is the number of nodes in the network, as proved by Cohen and Havlin. The diameter of a growing scale-free network might be considered almost constant in practice.
Scale free topology has been also found in high temperature superconductors. The qualities of a high-temperature superconductor — a compound in which electrons obey the laws of quantum physics, and flow in perfect synchrony, without friction — appear linked to the fractal arrangements of seemingly random oxygen atoms.
and Rényi (1960) studied a model of growth for graphs in which, at each step, two nodes are chosen uniformly at random and a link is inserted between them. The properties of these random graph
s are different from the properties found in scale-free networks, and therefore a model for this growth process is needed.
The mostly widely known generative model for a subset of scale-free networks is Barabási and Albert's (1999) rich get richer generative model in which each new Web page creates links to existing Web pages with a probability distribution which is not uniform, but
proportional to the current in-degree of Web pages. This model was originally discovered by Derek J. de Solla Price
in 1965 under the term cumulative advantage, but did not reach popularity until Barabási rediscovered the results under its current name (BA Model
). According to this process, a page with many in-links will attract more in-links than a regular page. This generates a power-law but the resulting graph differs
from the actual Web graph in other properties such as the presence of small
tightly connected communities. More general models and networks characteristics have been proposed and studied (for a review see the book by Dorogovtsev and Mendes
).
A somewhat different generative model for Web links has been suggested by Pennock et al. (2002). They examined communities with interests in a specific topic such as the home pages of universities, public companies, newspapers or scientists, and discarded the major hubs of the Web. In this case, the distribution of links was no longer a power law but resembled a normal distribution. Based on these observations, the authors proposed a generative model that mixes preferential attachment with a baseline probability of gaining a link.
Another generative model is the copy model studied by Kumar et al. (2000),
in which new nodes choose an existent node at random and copy a fraction of the links of the existent node. This also generates a power law.
Interestingly, the growth of the networks (adding new nodes) is not a necessary condition for creating a scale-free network. Dangalchev (2004) gives examples of generating static scale-free networks. Another possibility (Caldarelli et al. 2002) is to consider the structure as static and draw a link between vertices according to a particular property of the two vertices involved. Once specified the statistical distribution for these vertices properties (fitnesses), it turns out that in some circumstances also static networks develop scale-free properties.
a scale-free ideal network is a random network with a degree distribution
following the scale-free ideal gas
density distribution
. These networks have the special property of reproducing the city-size distribution and electoral results unravelling the size distribution of social groups with information theory on complex networks,
when a competitive cluster growth process is applied to the network. In models of scale-free ideal networks it is possible to demonstrate that Dunbar's number
is the cause of the phenomenon known as the 'six degrees of separation
' .
Complex network
In the context of network theory, a complex network is a graph with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in real graphs...
whose degree distribution
Degree distribution
In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.-Definition:...
follows a power law
Power law
A power law is a special kind of mathematical relationship between two quantities. When the frequency of an event varies as a power of some attribute of that event , the frequency is said to follow a power law. For instance, the number of cities having a certain population size is found to vary...
, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as
where
is a normalization constant and is a parameter whose value is typically in the range 2 < < 3, although occasionally it may lie outside these bounds.Highlights
- Many networks are conjectured to be scale-free, including World Wide Web links, biological networks, and social networks, although the scientific community is still discussing these claims as more sophisticated data analysis techniques become available.
- The mechanism of preferential attachmentPreferential attachmentA preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who are already wealthy receive more than those who are not...
and the fitness model have been proposed as a mechanisms to explain conjectured power law degree distributions in real networks.
History
In studies of the networks of citations between scientific papers, Derek de Solla PriceDerek J. de Solla Price
Derek John de Solla Price was a physicist, historian of science, and information scientist,credited as the father of scientometrics.-Biography:...
showed in 1965 that the number of links to papers—i.e., the number of citations they receive—had a heavy-tailed distribution
Heavy-tailed distribution
In probability theory, heavy-tailed distributions are probability distributions whose tails are not exponentially bounded: that is, they have heavier tails than the exponential distribution...
following a Pareto distribution or power law
Power law
A power law is a special kind of mathematical relationship between two quantities. When the frequency of an event varies as a power of some attribute of that event , the frequency is said to follow a power law. For instance, the number of cities having a certain population size is found to vary...
, and thus that the citation network is scale-free. He did not however use the term "scale-free network", which was not coined until some decades later. In a later paper in 1976, Price also proposed a mechanism to explain the occurrence of power laws in citation networks, which he called "cumulative advantage" but which is today more commonly known under the name preferential attachment
Preferential attachment
A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who are already wealthy receive more than those who are not...
.
Recent interest in scale-free networks started in 1999 with work by Albert-László Barabási
Albert-Laszlo Barabasi
Albert-László Barabási is a physicist, best known for his work in the research of network theory. He is the former Emil T...
and colleagues at the University of Notre Dame
University of Notre Dame
The University of Notre Dame du Lac is a Catholic research university located in Notre Dame, an unincorporated community north of the city of South Bend, in St. Joseph County, Indiana, United States...
who mapped the topology of a portion of the World Wide Web, finding that some nodes, which they called "hubs", had many more connections than others and that the network as a whole had a power-law distribution of the number of links connecting to a node. After finding that a few other networks, including some social and biological networks, also had heavy-tailed degree distributions, Barabási and collaborators coined the term "scale-free network" to describe the class of networks that exhibit a power-law degree distribution. Amaral et al. showed that most of the real-world networks can be classified into two large categories according to the decay of degree distribution P(k) for large k.
Barabási and Albert proposed a generative mechanism to explain the appearance of power-law distributions, which they called "preferential attachment
Preferential attachment
A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who are already wealthy receive more than those who are not...
" and which is essentially the same as that proposed by Price. Analytic solutions for this mechanism (also similar to the solution of Price) were presented in 2000 by Dorogovtsev, Mendes
José Fernando Ferreira Mendes
José F.F. Mendes is a Portuguese physicist and professor of physics at University of Aveiro .Was Head of Physics Department from December 2004 to February 2010...
and Samukhin and independently by Krapivsky, Redner
Sidney Redner
Sidney Redner is a Canadian-born physicist and professor of physics at Boston University. Redner has published over 200 journal articles, authored a book titled A Guide to First-Passage Processes , and coauthored a book titled A Kinetic View of Statistical Physics with Pavel L. Krapivsky and Eli...
, and Leyvraz, and later rigorously proved by mathematician Béla Bollobás
Béla Bollobás
Béla Bollobás FRS is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory and percolation. As a student, he took part in the first three International Mathematical Olympiads, winning two gold medals...
. Notably, however, this mechanism only produces a specific subset of networks in the scale-free class, and many alternative mechanisms have been discovered since.
The history of scale-free networks also includes some disagreement. On an empirical level, the scale-free nature of several networks has been called into question. For instance, the three brothers Faloutsos believed that the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
had a power law degree distribution on the basis of traceroute
Traceroute
traceroute is a computer network diagnostic tool for displaying the route and measuring transit delays of packets across an Internet Protocol network. Traceroute is available on most operating systems....
data; however, it has been suggested that this is a layer 3
Network Layer
The network layer is layer 3 of the seven-layer OSI model of computer networking.The network layer is responsible for packet forwarding including routing through intermediate routers, whereas the data link layer is responsible for media access control, flow control and error checking.The network...
illusion created by routers, which appear as high-degree nodes while concealing the internal layer 2
Data link layer
The data link layer is layer 2 of the seven-layer OSI model of computer networking. It corresponds to, or is part of the link layer of the TCP/IP reference model....
structure of the ASes
Autonomous system (Internet)
Within the Internet, an Autonomous System is a collection of connected Internet Protocol routing prefixes under the control of one or more network operators that presents a common, clearly defined routing policy to the Internet....
they interconnect.
On a theoretical level, refinements to the abstract definition of scale-free have been proposed. For example, Li et al. (2005) recently offered a potentially more precise "scale-free metric". Briefly, let g be a graph with edge-set ε, and let the degree (number of edges) at a vertex i be
. Define
This is maximized when high-degree nodes are connected to other high-degree nodes. Now define
where smax is the maximum value 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". This definition captures the notion of self-similarity
Self-similarity
In mathematics, a self-similar object is exactly or approximately similar to a part of itself . Many objects in the real world, such as coastlines, are statistically self-similar: parts of them show the same statistical properties at many scales...
implied in the name "scale-free".
Characteristics
The scale-free property strongly correlates with the network's robustness to failure. It turns out that the major hubs are closely followed by smaller ones. These ones, in turn, are followed by other nodes with an even smaller degree and so on. This hierarchy allows for a fault tolerant behavior. If failures occur at random and the vast majority of nodes are those with small degree, the likelihood that a hub would be affected is almost negligible. Even if a hub-failure occurs, the network will generally not lose its connectedness
Connectedness
In mathematics, connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected...
, due to the remaining hubs. On the other hand, if we choose a few major hubs and take them out of the network, the network is turned into a set of rather isolated graphs. Thus, hubs are both a strength and a weakness of scale-free networks. These properties have been studied analytically using percolation theory
Percolation theory
In mathematics, percolation theory describes the behavior of connected clusters in a random graph. The applications of percolation theory to materials science and other domains are discussed in the article percolation.-Introduction:...
by Cohen et al. and by Callaway et al.
Another important characteristic of scale-free networks is the clustering coefficient
Clustering coefficient
In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties...
distribution, which decreases as the node degree increases. This distribution also follows a power law. This implies that the low-degree nodes belong to very dense sub-graphs and those sub-graphs are connected to each other through hubs. Consider a social network in which nodes are people and links are acquaintance relationships between people. It is easy to see that people tend to form communities, i.e., small groups in which everyone knows everyone (one can think of such community as a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
). In addition, the members of a community also have a few acquaintance relationships to people outside that community. Some people, however, are connected to a large number of communities (e.g., celebrities, politicians). Those people may be considered the hubs responsible for the small-world phenomenon.
At present, the more specific characteristics of scale-free networks vary with the generative mechanism used to create them. For instance, networks generated by preferential attachment typically place the high-degree vertices in the middle of the network, connecting them together to form a core, with progressively lower-degree nodes making up the regions between the core and the periphery. The random removal of even a large fraction of vertices impacts the overall connectedness of the network very little, suggesting that such topologies could be useful for security
Network security
In the field of networking, the area of network security consists of the provisions and policies adopted by the network administrator to prevent and monitor unauthorized access, misuse, modification, or denial of the computer network and network-accessible resources...
, while targeted attacks destroys the connectedness very quickly. Other scale-free networks, which place the high-degree vertices at the periphery, do not exhibit these properties. Similarly, the clustering coefficient of scale-free networks can vary significantly depending on other topological details.
A final characteristic concerns the average distance between two vertices in a network. As with most disordered networks, such as the small world network model, this distance is very small relative to a highly ordered network such as a lattice graph
Lattice graph
The terms lattice graph, mesh graph, or grid graph refer to a number of categories of graphs whose drawing corresponds to some grid/mesh/lattice, i.e., its vertices correspond to the nodes of the mesh and its edges correspond to the ties between the nodes.-Square grid graph:A common type of a...
. Notably, an uncorrelated power-law graph having 2 < γ < 3 will have ultrasmall diameter d ~ ln ln N where N is the number of nodes in the network, as proved by Cohen and Havlin. The diameter of a growing scale-free network might be considered almost constant in practice.
Examples
Although many real-world networks are thought to be scale-free, the evidence often remains inconclusive, primarily due to the developing awareness of more rigorous data analysis techniques. As such, the scale-free nature of many networks is still being debated by the scientific community. A few examples of networks claimed to be scale-free include:- Social networkSocial networkA social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s, including collaboration networks. An example that has been studied extensively is the collaboration of movie actors in filmsSix Degrees of Kevin BaconSix Degrees of Kevin Bacon is a trivia game based on the concept of the small world phenomenon and rests on the assumption that any individual involved in the Hollywood, California film industry can be linked through his or her film roles to actor Kevin Bacon within six steps. The name of the game...
. - Sexual partners in humans, which affects the dispersal of sexually transmitted diseaseSexually transmitted diseaseSexually transmitted disease , also known as a sexually transmitted infection or venereal disease , is an illness that has a significant probability of transmission between humans by means of human sexual behavior, including vaginal intercourse, oral sex, and anal sex...
s. - Many kinds of computer networkComputer networkA computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
s, including the internetInternetThe Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
and the webgraphWebgraphThe webgraph describes the directed links between pages of the World Wide Web. A graph, in general, consists of several vertices, some pairs connected by edges. In a directed graph, edges are directed lines or arcs...
of the World Wide WebWorld Wide WebThe World Wide Web is a system of interlinked hypertext documents accessed via the Internet...
. - ProteinProteinProteins are biochemical compounds consisting of one or more polypeptides typically folded into a globular or fibrous form, facilitating a biological function. A polypeptide is a single linear polymer chain of amino acids bonded together by peptide bonds between the carboxyl and amino groups of...
-Protein interaction networks. - Semantic networks.
- Airline networks.
Scale free topology has been also found in high temperature superconductors. The qualities of a high-temperature superconductor — a compound in which electrons obey the laws of quantum physics, and flow in perfect synchrony, without friction — appear linked to the fractal arrangements of seemingly random oxygen atoms.
Generative models
These scale-free networks do not arise by chance alone. ErdősPaul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Rényi (1960) studied a model of growth for graphs in which, at each step, two nodes are chosen uniformly at random and a link is inserted between them. The properties of these random graph
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
s are different from the properties found in scale-free networks, and therefore a model for this growth process is needed.
The mostly widely known generative model for a subset of scale-free networks is Barabási and Albert's (1999) rich get richer generative model in which each new Web page creates links to existing Web pages with a probability distribution which is not uniform, but
proportional to the current in-degree of Web pages. This model was originally discovered by Derek J. de Solla Price
Derek J. de Solla Price
Derek John de Solla Price was a physicist, historian of science, and information scientist,credited as the father of scientometrics.-Biography:...
in 1965 under the term cumulative advantage, but did not reach popularity until Barabási rediscovered the results under its current name (BA Model
BA model
The Barabási–Albert model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Scale-free networks are widely observed in natural and man-made systems, including the Internet, the world wide web, citation networks, and some social...
). According to this process, a page with many in-links will attract more in-links than a regular page. This generates a power-law but the resulting graph differs
from the actual Web graph in other properties such as the presence of small
tightly connected communities. More general models and networks characteristics have been proposed and studied (for a review see the book by Dorogovtsev and Mendes
José Fernando Ferreira Mendes
José F.F. Mendes is a Portuguese physicist and professor of physics at University of Aveiro .Was Head of Physics Department from December 2004 to February 2010...
).
A somewhat different generative model for Web links has been suggested by Pennock et al. (2002). They examined communities with interests in a specific topic such as the home pages of universities, public companies, newspapers or scientists, and discarded the major hubs of the Web. In this case, the distribution of links was no longer a power law but resembled a normal distribution. Based on these observations, the authors proposed a generative model that mixes preferential attachment with a baseline probability of gaining a link.
Another generative model is the copy model studied by Kumar et al. (2000),
in which new nodes choose an existent node at random and copy a fraction of the links of the existent node. This also generates a power law.
Interestingly, the growth of the networks (adding new nodes) is not a necessary condition for creating a scale-free network. Dangalchev (2004) gives examples of generating static scale-free networks. Another possibility (Caldarelli et al. 2002) is to consider the structure as static and draw a link between vertices according to a particular property of the two vertices involved. Once specified the statistical distribution for these vertices properties (fitnesses), it turns out that in some circumstances also static networks develop scale-free properties.
Scale-free ideal network
In the context of network theoryNetwork theory
Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
a scale-free ideal network is a random network with a degree distribution
Degree distribution
In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.-Definition:...
following the scale-free ideal gas
Scale-Free Ideal Gas
The scale-free ideal gas is a physical model assuming a collection of non-interacting elements with an stochastic proportional growth. It is the scale-invariant version of an ideal gas...
density distribution
Probability density function
In probability theory, a probability density function , or density of a continuous random variable is a function that describes the relative likelihood for this random variable to occur at a given point. The probability for the random variable to fall within a particular region is given by the...
. These networks have the special property of reproducing the city-size distribution and electoral results unravelling the size distribution of social groups with information theory on complex networks,
when a competitive cluster growth process is applied to the network. In models of scale-free ideal networks it is possible to demonstrate that Dunbar's number
Dunbar's number
Dunbar's number is suggested to be a theoretical cognitive limit to the number of people with whom one can maintain stable social relationships. These are relationships in which an individual knows who each person is, and how each person relates to every other person...
is the cause of the phenomenon known as the 'six degrees of separation
Six degrees of separation
Six degrees of separation refers to the idea that everyone is on average approximately six steps away, by way of introduction, from any other person on Earth, so that a chain of, "a friend of a friend" statements can be made, on average, to connect any two people in six steps or fewer...
' .
See also
- Social-circles network modelSocial-circles network modelThe generative model of feedback networks , studied by White, Kejžar, Tsallis, Farmer, or social-circles network model, defines a class of random graphs generated by simple processes that are common to edge formation and feedback loops in social circles...
- a more generalized generative model for many "real-world networks" of which the scale-free network is a special case - Random graphRandom graphIn mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
- Erdős–Rényi modelErdos–Rényi modelIn graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
- Bose-Einstein condensation: a network theory approachBose-Einstein condensation: a network theory approachBose–Einstein condensation in networks is a phase transition observed in complex networks that can be described with the same mathematical model as that explaining Bose–Einstein condensation in physics.-Background:...
- Scale invarianceScale invarianceIn physics and mathematics, scale invariance is a feature of objects or laws that do not change if scales of length, energy, or other variables, are multiplied by a common factor...
- Complex networkComplex networkIn the context of network theory, a complex network is a graph with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in real graphs...
- WebgraphWebgraphThe webgraph describes the directed links between pages of the World Wide Web. A graph, in general, consists of several vertices, some pairs connected by edges. In a directed graph, edges are directed lines or arcs...
External links
- snGraph Optimal software to manage scale-free networks.
- The Erdős Webgraph Server describing the hyperlinkHyperlinkIn computing, a hyperlink is a reference to data that the reader can directly follow, or that is followed automatically. A hyperlink points to a whole document or to a specific element within a document. Hypertext is text with hyperlinks...
structure of a weekly updated, constantly increasing portion of the WWW.