View source for Bianconi–Barabási model

{{multiple issues|
{{COI|date=June 2019}}
{{third-party|date=June 2019}}
}}
[[Image:Bec5555.jpg|thumb|350px|right| Bose–Einstein Condensate: The Bianconi–Barabási model's fitness concept can be used to explain the [[Bose–Einstein condensate]]. Here the peaks show that as the temperature goes down, more and more atoms condense to the same energy level. At lower temperature when the "fitness" is higher, this model predicts that more atoms will be connected to the same energy level.]]

{{Network_Science}}

The '''Bianconi–Barabási model''' is a model in [[network science]] 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 <ref name="BB_model">{{cite journal|last1=Bianconi|first1=Ginestra|last2=Barabási|first2=Albert-László|title=Competition and multiscaling in evolving networks.|journal=Europhysics Letters|date=2001|doi=10.1209/epl/i2001-00260-6|volume=54|issue=4|pages=436–442|bibcode=2001EL.....54..436B|arxiv=cond-mat/0011029|s2cid=250871164 }}<!--|accessdate=4 June 2015--></ref><ref name="BB_Bose">{{cite journal|last1=Bianconi|first1=Ginestra|last2=Barabási|first2=Albert-László|title=Bose–Einstein condensation in complex networks|journal=Physical Review Letters|date=2001|doi=10.1103/physrevlett.86.5632|pmid=11415319|volume=86|issue=24|pages=5632–5635|bibcode=2001PhRvL..86.5632B|arxiv=cond-mat/0011224|s2cid=18375451}}</ref> is named after its inventors [[Ginestra Bianconi]] and [[Albert-László Barabási]]. This model is a variant of the  [[Barabási–Albert model]]. 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.<ref name="BB_Bose"/>

==Concepts==
The Barabási–Albert (BA) model uses two concepts: growth and [[preferential attachment]]. 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,<ref name="BB_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.<ref>{{cite book|last1=Pastor-Satorras|first1=Romualdo|last2=Vespignani|first2=Alessandro|title=Evolution and structure of the Internet: A statistical physics approach.|date=2007|publisher=Cambridge University Press.|page=100|edition=1st}}</ref> 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".<ref>{{cite book|last1=Barabási|first1=Albert-László|title=Linked: The New Science of Networks|url=https://archive.org/details/newsciencenetwor00albe_370|url-access=limited|date=2002|publisher=Perseus Books Group|page=[https://archive.org/details/newsciencenetwor00albe_370/page/n99 95]}}</ref>

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.<ref>{{cite journal|last1=Vázquez|first1=Alexei|last2=Pastor-Satorras|first2=Romualdo|last3=Vespignani.|first3=Alessandro|title=Large-scale topological and dynamical properties of the Internet|journal=Physical Review E|date=2002|doi=10.1103/physreve.65.066130|pmid=12188806|volume=65|issue=6|pages=066130|arxiv=cond-mat/0112400|bibcode=2002PhRvE..65f6130V|s2cid=9944774}}</ref> This model can also show condensation phase transitions in the evolution of complex network.<ref>{{cite journal|last1=Su|first1=Guifeng|last2=Xiaobing|first2=Zhang|last3=Zhang|first3=Yi|title=Condensation phase transition in nonlinear fitness networks|journal=EPL|date=2012|doi=10.1209/0295-5075/100/38003|volume=100|issue=3|pages=38003|arxiv=1103.3196|bibcode=2012EL....10038003S|s2cid=14821593}}<!--|accessdate=4 June 2015--></ref><ref name="BB_Bose"/>
The BB model can predict the topological properties of Internet.<ref name="Oxford University Press">{{cite book|last1=Caldarelli|first1=Guido|last2=Catanzaro|first2=Michele|title=Networks: A Very Short Introduction|date=2012|publisher=Oxford University Press|page=78}}</ref>

==Algorithm==
The fitness network begins with a fixed number of interconnected nodes. They have different fitness, which can be described with fitness parameter,  <math>\eta_j</math> which is chosen from a fitness distribution&nbsp;<math>\rho(\eta)</math>.

=== 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  <math>\eta_j</math> is added with each time-step.

===[[Preferential attachment]]===

The probability <math>\Pi_i</math> that a new node connects to one of the existing links to a node <math>i</math> in the network depends on the number of edges, <math>k_{i}</math>, and on the fitness <math>\eta_{i}</math> of node <math>i</math>, such that,

: <math>\Pi_i = \frac{\eta_i  k_i}{\sum_j \eta_j k_j}.</math>

Each node’s evolution with time can be predicted using the continuum theory. If initial number of node is <math>m</math>, then the degree of node <math>i</math> changes at the rate:

: <math>\frac{\partial k_i}{\partial t} = m\frac{\eta_i k_i}{\sum_j \eta_j k_j}</math>

Assuming the evolution of <math>k_i</math> follows a power law with a fitness exponent <math>\beta(\eta_i)</math>

: <math>k(t,t_i,\eta_i) = m\left(\frac{t}{t_i}\right)^{\beta(\eta_i)}</math>,

where <math>t_i</math> is the time since the creation of node <math>i</math>.

Here, <math>\beta(\eta) = \frac{\eta}{C}\text{ and }C = \int \rho(\eta)\frac{\eta}{1-\beta(\eta)} \, d\eta. </math>

==Properties==

===Equal fitnesses===
If all fitnesses are equal in a fitness network, the Bianconi–Barabási model reduces to the [[Barabási–Albert model]], when the degree is not considered, the model reduces to the [[fitness model (network theory)]].

When fitnesses are equal, the probability <math>\Pi_i</math> that the new node is connected to node <math>i</math> when <math>k_i</math> is the degree of node <math>i</math> is,

: <math>\Pi_i = \frac{k_i}{\sum_j k_j}.</math>

===[[Degree distribution]]===
Degree distribution of the Bianconi–Barabási model depends on the fitness distribution <math>\rho(\eta)</math>. 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.<ref>{{cite book|last1=Guanrong|first1=Chen|last2=Xiaofan|first2=Wang|last3=Xiang|first3=Li|title=Fundamentals of Complex Networks: Models, Structures and Dynamics|date=2014|page=126}}</ref>

===Measuring node fitnesses from empirical network data===

There are various statistical methods to measure node fitnesses <math>\eta_i</math> in the Bianconi–Barabási model from real-world network data.<ref>{{Cite journal|last1=Kong|first1=Joseph S.|last2=Sarshar|first2=Nima|last3=Roychowdhury|first3=Vwani P.|date=2008-09-16|title=Experience versus talent shapes the structure of the Web|journal=Proceedings of the National Academy of Sciences|language=en|volume=105|issue=37|pages=13724–13729|doi=10.1073/pnas.0805921105|issn=0027-8424|pmid=18779560|pmc=2544521|bibcode=2008PNAS..10513724K|arxiv=0901.0296|doi-access=free}}</ref><ref name=":0">{{Cite journal|last1=Pham|first1=Thong|last2=Sheridan|first2=Paul|last3=Shimodaira|first3=Hidetoshi|date=2016-09-07|title=Joint estimation of preferential attachment and node fitness in growing complex networks|journal=Scientific Reports|language=en|volume=6|issue=1|pages=32558|doi=10.1038/srep32558|pmid=27601314|issn=2045-2322|bibcode=2016NatSR...632558P|pmc=5013469}}</ref>  From the measurement, one can investigate the fitness distribution <math>\rho(\eta)</math> or compare the Bianconi–Barabási model with various competing network models in that particular network.<ref name=":0" />

===Variations of the Bianconi–Barabási model===
The Bianconi–Barabási model has been extended to weighted networks <ref name="Bia_weighted">{{cite journal|last1=Bianconi|first1=Ginestra|title=Emergence of weight-topology correlations in complex scale-free networks.|journal=Europhysics Letters|date=2005|doi=10.1209/epl/i2005-10167-2|volume=71|issue=6|pages=1029–1035|arxiv=cond-mat/0412399|bibcode=2005EL.....71.1029B|s2cid=119038738}}</ref> displaying linear and superlinear scaling of the strength with the degree of the nodes as observed in real network data.<ref name="Vesp_weighted">{{cite journal|last1=Barrat|first1=Alan|last2=Barthélemy|first2=Marc|last3=Vepsignani|first3=Alessandro|title=The architecture of complex weighted networks.|journal=Proceedings of the National Academy of Sciences|date=2004|doi=10.1073/pnas.0400087101 |arxiv=cond-mat/0311416|pmid=15007165|volume=101|issue=11|pages=3747–3752|pmc=374315|bibcode=2004PNAS..101.3747B|doi-access=free}}</ref> 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.<ref name=Bia_weighted/>
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 <ref name="Bia_Hyperbolic">{{cite journal|last1=Bianconi|first1=Ginestra|last2=Rahmede|first2=Christoph|title=Emergent hyperbolic network geometry.|journal=Scientific Reports|date=2017|doi=10.1038/srep41974|volume=7|pages=41974|pmid=28167818 |pmc=5294422 |arxiv=1607.05710|bibcode=2017NatSR...741974B|doi-access=free}}</ref> called Network Geometry with Flavor.<ref name="Bia_NGF">{{cite journal|last1=Bianconi|first1=Ginestra|last2=Rahmede|first2=Christoph|title=Network geometry with flavor: from complexity to quantum geometry.|journal=Physical Review E|date=2016|doi=10.1103/PhysRevE.93.032315|pmid=27078374|volume=93|issue=3|pages=032315|arxiv=1511.04539|bibcode=2016PhRvE..93c2315B|s2cid=13056697}}</ref> 
The Bianconi–Barabási model can be also modified to study  static networks where the number of nodes is fixed.<ref>{{cite book|last1=Caldarelli|first1=Guido|last2=Catanzaro|first2=Michele|title=Networks: A Very Short Introduction|date=2012|publisher=Oxford University Press|page=77}}</ref>

==Bose-Einstein condensation==

Bose–Einstein condensation in networks is a [[phase transition]] observed in [[complex network]]s that can be described by the Bianconi–Barabási model.<ref name="BB_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]] in physics.

===Background===
In [[physics]], a [[Bose–Einstein condensate]] 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]] or a [[fermion]]. For example, an electron is a fermion, while a photon or a [[helium]] atom is a boson.  In [[quantum mechanics]], 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]], 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]] 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]] are governed by the [[Bose–Einstein statistics]]. In Bose–Einstein statistics, any number of identical bosons can be in the same state. In particular, given an energy state {{mvar|ε}}, the number of non-interacting bosons in thermal equilibrium at temperature {{math|''T'' {{=}} {{sfrac|1|''β''}}}} is given by the Bose occupation number

: <math>n(\varepsilon)=\frac{1}{e^{\beta(\varepsilon-\mu)}-1}</math>

where the constant {{mvar|μ}} is determined by an equation describing the conservation of the number of particles

:<math>N=\int d\varepsilon \, g(\varepsilon) \, n(\varepsilon)</math>

with {{math|''g''(''ε'')}} being the density of states of the system.

This last equation may lack a solution at low enough temperatures when {{math|''g''(''ε'') → 0}} for {{math|''ε'' → 0}}. In this case a critical temperature {{math|''T<sub>c</sub>''}} is found such that for {{math|''T'' < ''T<sub>c</sub>''}} 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 {{math|''g''(''ε'')}} depends on the dimensionality of the space.  In particular <math>g(\varepsilon)\sim \varepsilon^{\frac{d-2}{2}}</math> therefore {{math|''g''(''ε'') → 0}} for {{math|''ε'' → 0}} only in dimensions {{math|''d'' > 2}}. Therefore, a Bose-Einstein condensation of an ideal Bose gas can only occur for dimensions {{math|''d'' > 2}}.

===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 (network theory)|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.<ref name="BB_Bose"/>

[[File:Schematic illustration of mapping between network model and Bose-Einstein Condensate.jpg|thumb|450px|left|Schematic illustration of the mapping between the network model and the Bose gas.<ref name=BB_Bose/>]]

===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 {{math|''ε<sub>i</sub>''}} to each node, determined by its fitness through the relation<ref name="BB_Bose"/><ref name=bara>{{cite journal | last1=Albert | first1=Réka | last2=Barabási | first2=Albert-László | title=Statistical mechanics of complex networks | journal=Reviews of Modern Physics | volume=74 | issue=1 | date=2002-01-30 | issn=0034-6861 | doi=10.1103/revmodphys.74.47 | pages=47–97| arxiv=cond-mat/0106096 | bibcode=2002RvMP...74...47A | s2cid=60545 }}</ref>

: <math>\varepsilon_i=-\frac{1}{\beta}\ln{\eta_i}</math>

where {{math|''β'' {{=}} 1 / T}} <!-- plays the role of inverse temperature -->. In particular when {{math|''β'' {{=}} 0}} all the nodes have equal fitness, when instead {{math|''β'' ≫ 1}} nodes with different "energy" have very different fitness. We assume that the network evolves through a modified [[preferential attachment]] mechanism. At each time a new node {{mvar|i}} with energy {{math|''ε<sub>i</sub>''}} drawn from a probability distribution {{math|''p''(''ε'')}} enters in the network and attach a new link to a node {{mvar|j}} chosen with probability:

: <math>\Pi_j=\frac{e^{-\beta\varepsilon_j}k_j}{\sum_r e^{-\beta\varepsilon_r}k_r}.</math>

In the mapping to a Bose gas, we assign to every new link linked by preferential attachment to node {{mvar|j}} a particle in the energy state {{math|''ε<sub>j</sub>''}}.

The continuum theory predicts that the rate at which links accumulate on node {{mvar|i}} with "energy" {{math|''ε<sub>i</sub>''}} is given by

: <math>\frac{\partial k_i(\varepsilon_i,t,t_i)}{\partial t}=m\frac{e^{-\beta\varepsilon_i}k_i(\varepsilon_i,t,t_i)}{Z_t}</math>

where <math>k_i(\varepsilon_i,t, t_i)</math> indicating the number of links attached to node {{mvar|i}} that was added to the network at the time step <math>t_i</math>. <math>Z_t</math> is the [[Partition function (statistical mechanics)|partition function]], defined as:

: <math>Z_t=\sum_i  e^{-\beta\varepsilon_i}k_i(\varepsilon_i,t,t_i).</math>

The solution of this differential equation is:

: <math>k_i(\varepsilon_i,t,t_i)=m\left(\frac{t}{t_i}\right)^{f(\varepsilon_i)}</math>

where the dynamic exponent <math>f(\varepsilon)</math> satisfies <math>f(\varepsilon)=e^{-\beta(\varepsilon-\mu)}</math>, {{mvar|μ}} plays the role of the chemical potential, satisfying the equation

: <math>\int d\varepsilon \, p(\varepsilon) \frac{1}{e^{\beta(\varepsilon-\mu)}-1}=1</math>

where {{math|''p''(''ε'')}} is the probability that a node has "energy" {{mvar|ε}} and "fitness" {{math|''η'' {{=}} ''e<sup>−βε</sup>''}}. In the limit, {{math|''t'' → ∞}}, the occupation number, giving the number of links linked to nodes with "energy" {{mvar|ε}}, follows the familiar Bose statistics

: <math>n(\varepsilon)=\frac{1}{e^{\beta(\varepsilon -\mu)}-1}.</math>

The definition of the constant {{mvar|μ}} in the network models is surprisingly similar to the definition of the chemical potential in a Bose gas. In particular for probabilities {{math|''p''(''ε'')}} such that {{math|''p''(''ε'') → 0}} for {{math|''ε'' → 0}} at high enough value of {{mvar|β}} 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 [[network topology|topological]] phase transition after which the network has a star-like dominant structure.

===Bose–Einstein phase transition in complex networks===
[[Image:Bec2222.jpg|thumb|350px|right|Numerical evidence for Bose–Einstein condensation in a network model.<ref name=BB_Bose/>]]
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 {{math|''T'' < ''T<sub>BE</sub>''}}, 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 model (network theory)|fitness distribution]] <math>\rho(\eta)</math> that leads to condensation is given by

:<math>\rho(\eta)=(\lambda+1)(1-\eta)^\lambda,</math>

where <math>\lambda=1</math>.

However, the existence of the Bose–Einstein condensation or the fit-get-rich phase does not depend on the temperature or {{mvar|β}} of the system but depends only on the functional form of the fitness distribution <math>\rho(\eta)</math> of the system. In the end, {{mvar|β}} 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.<ref name=dor>{{cite journal | last1=Dorogovtsev | first1=S. N. | last2=Mendes | first2=J. F. F. | title=Scaling properties of scale-free evolving networks: Continuous approach | journal=Physical Review E | volume=63 | issue=5 | date=2001-04-26 | issn=1063-651X | doi=10.1103/physreve.63.056125 | page=056125| pmid=11414979 | arxiv=cond-mat/0012009 | bibcode=2001PhRvE..63e6125D | s2cid=11295775 }}</ref> A similar gelation can be seen in models with [[Non-linear preferential attachment|superlinear preferential attachment]],<ref name=kra>{{cite journal | last1=Krapivsky | first1=P. L. | last2=Redner | first2=S. | last3=Leyvraz | first3=F. | title=Connectivity of Growing Random Networks | journal=Physical Review Letters | publisher=American Physical Society (APS) | volume=85 | issue=21 | date=2000-11-20 | issn=0031-9007 | doi=10.1103/physrevlett.85.4629 | pages=4629–4632| pmid=11082613 | arxiv=cond-mat/0005139 | bibcode=2000PhRvL..85.4629K | s2cid=16251662 }}</ref> 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]]

== References ==
<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags, these references will then appear here automatically -->
{{Reflist}}

== External links ==
* [https://books.google.com/books?id=aOb5kq5RPr4C Networks: A Very Short Introduction ]
* [https://web.archive.org/web/20220123073834/https://www.cs.upc.edu/~csn/slides/09advanced_network_dynamics.pdf Advance Network Dynamics]

{{DEFAULTSORT:Bianconi-Barabasi model}}
<!--- Categories --->
[[Category:Social network analysis]]
[[Category:Graph algorithms]]
[[Category:Random graphs]]