The Bianconi–Barabási model is a model in
network science
Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors rep ...
that explains the growth of complex evolving networks. This model can explain that nodes with different characteristics acquire links at different rates. It predicts that a node's growth depends on its fitness and can calculate the degree distribution. The Bianconi–Barabási model
is named after its inventors
Ginestra Bianconi
Ginestra Bianconi is a network scientist and mathematical physicist, known for her work on statistical mechanics, network theory, multilayer and higher-order networks, and in particular for the Bianconi–Barabási model of growing of complex n ...
and
Albert-László Barabási
Albert-László Barabási (born March 30, 1967) is a Romanian-born Hungarian-American physicist, best known for his discoveries in network science and network medicine.
He is Distinguished University Professor and Robert Gray Professor of Netw ...
. This model is a variant of the
Barabási–Albert model
The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and s ...
. The model can be mapped to a Bose gas and this mapping can predict a topological phase transition between a "rich-get-richer" phase and a "winner-takes-all" phase.
Concepts
The Barabási–Albert (BA) model uses two concepts: growth and
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 ...
. Here, growth indicates the increase in the number of nodes in the network with time, and preferential attachment means that more connected nodes receive more links. The Bianconi–Barabási model,
on top of these two concepts, uses another new concept called the fitness. This model makes use of an analogy with evolutionary models. It assigns an intrinsic fitness value to each node, which embodies all the properties other than the degree. The higher the fitness, the higher the probability of attracting new edges. Fitness can be defined as the ability to attract new links – "a quantitative measure of a node's ability to stay in front of the competition".
While the Barabási–Albert (BA) model explains the "first mover advantage" phenomenon, the Bianconi–Barabási model explains how latecomers also can win. In a network where fitness is an attribute, a node with higher fitness will acquire links at a higher rate than less fit nodes. This model explains that age is not the best predictor of a node's success, rather latecomers also have the chance to attract links to become a hub.
The Bianconi–Barabási model can reproduce the degree correlations of the Internet Autonomous Systems. This model can also show condensation phase transitions in the evolution of complex network.
The BB model can predict the topological properties of Internet.
Algorithm
The fitness network begins with a fixed number of interconnected nodes. They have different fitness, which can be described with fitness parameter,
which is chosen from a fitness distribution
.
Growth
The assumption here is that a node’s fitness is independent of time, and is fixed.
A new node ''j'' with ''m'' links and a fitness
is added with each time-step.
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 ...
The probability
that a new node connects to one of the existing links to a node
in the network depends on the number of edges,
, and on the fitness
of node
, such that,
:
Each node’s evolution with time can be predicted using the continuum theory. If initial number of node is
, then the degree of node
changes at the rate:
:
Assuming the evolution of
follows a power law with a fitness exponent
:
,
where
is the time since the creation of node
.
Here,
Properties
Equal fitnesses
If all fitnesses are equal in a fitness network, the Bianconi–Barabási model reduces to the
Barabási–Albert model
The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and s ...
, when the degree is not considered, the model reduces to the
fitness model (network theory) In complex network theory, the fitness model is a model of the evolution of a network: how the links between nodes change over time depends on the fitness of nodes. Fitter nodes attract more links at the expense of less fit nodes.
It has been used ...
.
When fitnesses are equal, the probability
that the new node is connected to node
when
is the degree of node
is,
:
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
The degre ...
Degree distribution of the Bianconi–Barabási model depends on the fitness distribution
. There are two scenarios that can happen based on the probability distribution. If the fitness distribution has a finite domain, then the degree distribution will have a power-law just like the BA model. In the second case, if the fitness distribution has an infinite domain, then the node with the highest fitness value will attract a large number of nodes and show a winners-take-all scenario.
Measuring node fitnesses from empirical network data
There are various statistical methods to measure node fitnesses
in the Bianconi–Barabási model from real-world network data.
From the measurement, one can investigate the fitness distribution
or compare the Bianconi–Barabási model with various competing network models in that particular network.
Variations of the Bianconi–Barabási model
The Bianconi–Barabási model has been extended to weighted networks
displaying linear and superlinear scaling of the strength with the degree of the nodes as observed in real network data.
This weighted model can lead to condensation of the weights of the network when few links acquire a finite fraction of the weight of the entire network.
[
Recently it has been shown that the Bianconi–Barabási model can be interpreted as a limit case of the model for emergent hyperbolic network geometry ] called Network Geometry with Flavor.
The Bianconi–Barabási model can be also modified to study static networks where the number of nodes is fixed.
Bose-Einstein condensation
Bose–Einstein condensation in networks is a phase transition
In chemistry, thermodynamics, and other related fields, a phase transition (or phase change) is the physical process of transition between one state of a medium and another. Commonly the term is used to refer to changes among the basic states o ...
observed in complex network
In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real ...
s that can be described by the Bianconi–Barabási model. This phase transition predicts a "winner-takes-all" phenomena in complex networks and can be mathematically mapped to the mathematical model explaining Bose–Einstein condensation Bose–Einstein may refer to:
* Bose–Einstein condensate
** Bose–Einstein condensation (network theory)
* Bose–Einstein correlations
* Bose–Einstein statistics
In quantum statistics, Bose–Einstein statistics (B–E statistics) describe ...
in physics.
Background
In physics
Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which r ...
, a Bose–Einstein condensate
In condensed matter physics, a Bose–Einstein condensate (BEC) is a state of matter that is typically formed when a gas of bosons at very low densities is cooled to temperatures very close to absolute zero (−273.15 °C or −459.6 ...
is a state of matter that occurs in certain gases at very low temperatures. Any elementary particle, atom, or molecule, can be classified as one of two types: a boson
In particle physics, a boson ( ) is a subatomic particle whose spin quantum number has an integer value (0,1,2 ...). Bosons form one of the two fundamental classes of subatomic particle, the other being fermions, which have odd half-integer spi ...
or a fermion. For example, an electron is a fermion, while a photon or a helium
Helium (from el, ἥλιος, helios, lit=sun) is a chemical element with the symbol He and atomic number 2. It is a colorless, odorless, tasteless, non-toxic, inert, monatomic gas and the first in the noble gas group in the periodic table. ...
atom is a boson. In quantum mechanics
Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistr ...
, the energy of a (bound) particle is limited to a set of discrete values, called energy levels. An important characteristic of a fermion is that it obeys the Pauli exclusion principle
In quantum mechanics, the Pauli exclusion principle states that two or more identical particles with half-integer spins (i.e. fermions) cannot occupy the same quantum state within a quantum system simultaneously. This principle was formulat ...
, which states that no two fermions may occupy the same state. Bosons, on the other hand, do not obey the exclusion principle, and any number can exist in the same state. As a result, at very low energies (or temperatures), a great majority of the bosons in a Bose gas
An ideal Bose gas is a quantum-mechanical phase of matter, analogous to a classical ideal gas. It is composed of bosons, which have an integer value of spin, and abide by Bose–Einstein statistics. The statistical mechanics of bosons were deve ...
can be crowded into the lowest energy state, creating a Bose–Einstein condensate.
Bose and Einstein have established that the statistical properties of a Bose gas
An ideal Bose gas is a quantum-mechanical phase of matter, analogous to a classical ideal gas. It is composed of bosons, which have an integer value of spin, and abide by Bose–Einstein statistics. The statistical mechanics of bosons were deve ...
are governed by the Bose–Einstein statistics
In quantum statistics, Bose–Einstein statistics (B–E statistics) describes one of two possible ways in which a collection of non-interacting, indistinguishable particles may occupy a set of available discrete energy states at thermodynamic ...
. In Bose–Einstein statistics, any number of identical bosons can be in the same state. In particular, given an energy state , the number of non-interacting bosons in thermal equilibrium at temperature is given by the Bose occupation number
:
where the constant is determined by an equation describing the conservation of the number of particles
:
with being the density of states of the system.
This last equation may lack a solution at low enough temperatures when for . In this case a critical temperature is found such that for the system is in a Bose-Einstein condensed phase and a finite fraction of the bosons are in the ground state.
The density of states depends on the dimensionality of the space. In particular therefore for only in dimensions . Therefore, a Bose-Einstein condensation of an ideal Bose gas can only occur for dimensions .
The concept
The evolution of many complex systems, including the World Wide Web, business, and citation networks, is encoded in the dynamic web describing the interactions between the system’s constituents. The evolution of these networks is captured by the Bianconi-Barabási model, which includes two main characteristics of growing networks: their constant growth by the addition of new nodes and links and the heterogeneous ability of each node to acquire new links described by the node fitness. Therefore the model is also known as fitness model.
Despite their irreversible and nonequilibrium nature, these networks follow the Bose statistics and can be mapped to a Bose gas.
In this mapping, each node is mapped to an energy state determined by its fitness and each new link attached to a given node is mapped to a Bose particle occupying the corresponding energy state. This mapping predicts that the Bianconi–Barabási model can undergo a topological phase transition in correspondence to the Bose–Einstein condensation of the Bose gas. This phase transition is therefore called Bose-Einstein condensation in complex networks.
Consequently addressing the dynamical properties of these nonequilibrium systems within the framework of equilibrium quantum gases predicts that the “first-mover-advantage,” “fit-get-rich (FGR),” and “winner-takes-all” phenomena observed in a competitive systems are thermodynamically distinct phases of the underlying evolving networks.
The mathematical mapping of the network evolution to the Bose gas
Starting from the Bianconi-Barabási model, the mapping of a Bose gas to a network can be done by assigning an energy to each node, determined by its fitness through the relation
:
where . In particular when all the nodes have equal fitness, when instead nodes with different "energy" have very different fitness. We assume that the network evolves through a modified 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 ...
mechanism. At each time a new node with energy drawn from a probability distribution enters in the network and attach a new link to a node chosen with probability:
:
In the mapping to a Bose gas, we assign to every new link linked by preferential attachment to node a particle in the energy state .
The continuum theory predicts that the rate at which links accumulate on node with "energy" is given by
:
where indicating the number of links attached to node that was added to the network at the time step . is the partition function, defined as:
:
The solution of this differential equation is:
:
where the dynamic exponent satisfies , plays the role of the chemical potential, satisfying the equation
:
where is the probability that a node has "energy" and "fitness" . In the limit, , the occupation number, giving the number of links linked to nodes with "energy" , follows the familiar Bose statistics
:
The definition of the constant in the network models is surprisingly similar to the definition of the chemical potential in a Bose gas. In particular for probabilities such that for at high enough value of we have a condensation phase transition in the network model. When this occurs, one node, the one with higher fitness acquires a finite fraction of all the links. The Bose–Einstein condensation in complex networks is, therefore, a topological
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
phase transition after which the network has a star-like dominant structure.
Bose–Einstein phase transition in complex networks
The mapping of a Bose gas predicts the existence of two distinct phases as a function of the energy distribution. In the fit-get-rich phase, describing the case of uniform fitness, the fitter nodes acquire edges at a higher rate than older but less fit nodes. In the end the fittest node will have the most edges, but the richest node is not the absolute winner, since its share of the edges (i.e. the ratio of its edges to the total number of edges in the system) reduces to zero in the limit of large system sizes (Fig.2(b)). The unexpected outcome of this mapping is the possibility of Bose–Einstein condensation for , when the fittest node acquires a finite fraction of the edges and maintains this share of edges over time (Fig.2(c)).
A representative fitness distribution that leads to condensation is given by
:
where .
However, the existence of the Bose–Einstein condensation or the fit-get-rich phase does not depend on the temperature or of the system but depends only on the functional form of the fitness distribution of the system. In the end, falls out of all topologically important quantities. In fact, it can be shown that Bose–Einstein condensation exists in the fitness model even without mapping to a Bose gas. A similar gelation can be seen in models with superlinear preferential attachment, however, it is not clear whether this is an accident or a deeper connection lies between this and the fitness model.
See also
*Barabási–Albert model
The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and s ...
References
External links
Networks: A Very Short Introduction
Advance Network Dynamics
{{DEFAULTSORT:Bianconi-Barabasi model
Social network analysis
Graph algorithms
Random graphs