Bianconi–Barabási model

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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.

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 [1][2] 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.[2]

Concepts[edit]

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,[1] 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.[3] 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".[4]

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.[5] This model can also show condensation phase transitions in the evolution of complex network.[6][2] The BB model can predict the topological properties of Internet.[7]

Algorithm[edit]

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[edit]

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[edit]

The probability Πi that a new node connects to one of the existing links to a node i in the network depends on the number of edges, , and on the fitness of node i, such that,

Each node’s evolution with time can be predicted using the continuum theory. If initial number of node is m, then the degree of node i 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[edit]

Equal fitnesses[edit]

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 that the new node is connected to node when is the degree of node is,

Degree distribution[edit]

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.[8]

Measuring node fitnesses from empirical network data[edit]

There are various statistical methods to measure node fitnesses in the Bianconi–Barabási model from real-world network data.[9][10] 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.[10]

Variations of the Bianconi–Barabási model[edit]

The Bianconi–Barabási model has been extended to weighted networks [11] displaying linear and superlinear scaling of the strength with the degree of the nodes as observed in real network data.[12] 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.[11] 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 [13] called Network Geometry with Flavor.[14] The Bianconi–Barabási model can be also modified to study static networks where the number of nodes is fixed.[15]

History[edit]

In 1999, Albert-László Barabási requested his student Bianconi to investigate evolving networks where nodes have a fitness parameter. Barabási was interested in finding out how Google, a latecomer in the search engine market, became a top player. Google’s toppling of previous top search engines went against Barabási's BA model, which states that first mover has an advantage. In the scale-free network if a node appears first it will be most connected because it had the longest time to attract links. Bianconi's work showed that when fitness parameter is present, the "early bird" is not always the winner.[16] Bianconi and Barabási's research showed that fitness is what creates or breaks the hub. Google's superior PageRank algorithm helped them to beat other top players. Later on Facebook came and dethroned Google as Internet's most linked website. In all these cases fitness mattered which was first showed in Bianconi and Barabási's research. In 2001, Ginestra Bianconi and Albert-László Barabási published the model in the Europhysics Letters.[1] In another paper,[2] substituting fitness for energy, nodes for energy level and links for particles, Bianconi and Barabási were able to map the fitness model with Bose gas.

See also[edit]

References[edit]

  1. ^ a b c Bianconi, Ginestra; Barabási, Albert-László (2001). "Competition and multiscaling in evolving networks". Europhysics Letters. 54 (4): 436–442. arXiv:cond-mat/0011029. Bibcode:2001EL.....54..436B. doi:10.1209/epl/i2001-00260-6.
  2. ^ a b c d Bianconi, Ginestra; Barabási, Albert-László (2001). "Bose–Einstein condensation in complex networks". Physical Review Letters. 86 (24): 5632–5635. arXiv:cond-mat/0011224. Bibcode:2001PhRvL..86.5632B. doi:10.1103/physrevlett.86.5632. PMID 11415319.
  3. ^ Pastor-Satorras, Romualdo; Vespignani, Alessandro (2007). Evolution and structure of the Internet: A statistical physics approach (1st ed.). Cambridge University Press. p. 100.
  4. ^ Barabási, Albert-László (2002). Linked: The New Science of Networks. Perseus Books Group. p. 95.
  5. ^ Vázquez, Alexei; Pastor-Satorras, Romualdo; Vespignani., Alessandro (2002). "Large-scale topological and dynamical properties of the Internet". Physical Review E. 65 (6): 066130. arXiv:cond-mat/0112400. Bibcode:2002PhRvE..65f6130V. doi:10.1103/physreve.65.066130. PMID 12188806.
  6. ^ Su, Guifeng; Xiaobing, Zhang; Zhang, Yi (2012). "Condensation phase transition in nonlinear fitness networks". EPL. 100 (3): 38003. arXiv:1103.3196. Bibcode:2012EL....10038003S. doi:10.1209/0295-5075/100/38003.
  7. ^ Caldarelli, Guido; Catanzaro, Michele (2012). Networks: A Very Short Introduction. Oxford University Press. p. 78.
  8. ^ Guanrong, Chen; Xiaofan, Wang; Xiang, Li (2014). Fundamentals of Complex Networks: Models, Structures and Dynamics. p. 126.
  9. ^ Kong, Joseph S.; Sarshar, Nima; Roychowdhury, Vwani P. (2008-09-16). "Experience versus talent shapes the structure of the Web". Proceedings of the National Academy of Sciences. 105 (37): 13724–13729. arXiv:0901.0296. Bibcode:2008PNAS..10513724K. doi:10.1073/pnas.0805921105. ISSN 0027-8424. PMC 2544521. PMID 18779560.
  10. ^ a b Pham, Thong; Sheridan, Paul; Shimodaira, Hidetoshi (2016-09-07). "Joint estimation of preferential attachment and node fitness in growing complex networks". Scientific Reports. 6 (1): 32558. Bibcode:2016NatSR...632558P. doi:10.1038/srep32558. ISSN 2045-2322. PMC 5013469. PMID 27601314.
  11. ^ a b Bianconi, Ginestra (2005). "Emergence of weight-topology correlations in complex scale-free networks". Europhysics Letters. 71 (6): 1029–1035. arXiv:cond-mat/0412399. doi:10.1209/epl/i2005-10167-2.
  12. ^ Barrat, Alan; Barthélemy, Marc; Vepsignani, Alessandro (2004). "The architecture of complex weighted networks". Proceedings of the National Academy of Sciences. 101 (11): 3747–3752. doi:10.1073/pnas.0400087101. PMC 374315. PMID 15007165.
  13. ^ Bianconi, Ginestra; Rahmede, Christoph (2017). "Emergent hyperbolic network geometry". Scientific Reports. 7: 41974. doi:10.1038/srep41974.
  14. ^ Bianconi, Ginestra; Rahmede, Christoph (2016). "Network geometry with flavor: from complexity to quantum geometry". Physical Review E. 93 (3): 032315. arXiv:1511.04539. doi:10.1103/PhysRevE.93.032315. PMID 27078374.
  15. ^ Caldarelli, Guido; Catanzaro, Michele (2012). Networks: A Very Short Introduction. Oxford University Press. p. 77.
  16. ^ Barabási, Albert-László (2002). Linked: The New Science of Networks. Perseus Books Group. p. 97.

External links[edit]