View source for Non-linear preferential attachment

In [[network science]], [[preferential attachment]] means that nodes of a network tend to connect to those nodes which have more links. If the network is growing and new nodes tend to connect to existing ones with linear probability in the degree of the existing nodes then preferential attachment leads to a [[scale-free network]]. If this probability is sub-linear then the network’s degree distribution is [[stretched exponential distribution|stretched exponential]] and hubs are much smaller than in a [[scale-free network]]. If this probability is super-linear then almost all nodes are connected to a few hubs. According to Kunegis, Blattner, and Moser several online networks follow a '''non-linear preferential attachment''' model. Communication networks and online contact networks are sub-linear while interaction networks are super-linear.<ref>{{cite journal|author1=Kunegis, Jérôme|author2=Blattner, Marcel|author3=Moser, Christine|title=Preferential Attachment in Online Networks: Measurement and Explanations|date=2013|arxiv=1303.6271|bibcode=2013arXiv1303.6271K}}</ref> The co-author network among scientists also shows the signs of sub-linear preferential attachment.<ref>{{cite book|last1=Barabási|first1=Albert-László|title=Network Science|pages=19|url=http://barabasi.com/networksciencebook/|chapter= Ch. 5}}</ref>

== Types of preferential attachment ==

For simplicity it can be assumed that the probability with which a new node connects to an existing one follows a power function of the existing nodes’ degree&nbsp;''k'':

: <math> \pi(k) \sim k^\alpha \, </math>

where ''α''&nbsp;>&nbsp;0. This is a good approximation for a lot of real networks such as the Internet, the citation network or the actor network. If ''α''&nbsp;=&nbsp;1 then the preferential attachment is linear. If ''α''&nbsp;<&nbsp;1 then it is sub-linear while if ''α''&nbsp;>&nbsp;1 then it is super-linear.<ref>{{cite book|last1=Barabási|first1=Albert-László|title=Network Science|pages=20–21|url=http://barabasi.com/networksciencebook/|chapter= Ch. 5}}</ref>

In measuring preferential attachment from real networks, the above log-linearity functional form ''k''<sup>''α''</sup> can be relaxed to a free form function, i.e. {{pi}}(''k'') can be measured for each ''k'' without any assumptions on the functional form of {{pi}}(''k''). This is believed to be more flexible, and allows the discovery of non-log-linearity of preferential attachment in real networks.<ref>{{cite journal|last1=Pham|first1=Thong|last2=Sheridan|first2=Paul|last3=Shimodaira|first3=Hidetoshi|title=PAFit: A Statistical Method for Measuring Preferential Attachment in Temporal Complex Networks|journal=PLOS ONE|date=September 17, 2015|volume=10 |issue=9|doi=10.1371/journal.pone.0137796|pages=e0137796|pmid=26378457|pmc=4574777|bibcode=2015PLoSO..1037796P|doi-access=free}}</ref>

== Sub-linear preferential attachment  ==

In this case the new nodes still tend to connect to the nodes with higher degree but this effect is smaller than in the case of linear preferential attachment. There are less hubs and their size is also smaller than in a scale-free network. The size of the largest component logarithmically depends on the number of nodes:

: <math> k_{\max} \sim (\log n)^{1/(1-\alpha)} </math>

so it is smaller than the polynomial dependence.<ref name="Connectivity of Growing Random Networks">{{cite journal|last1=Krapivsky|first1=P. L.|author2=S. Redner|author3=F. Leyvraz|title=Connectivity of Growing Random Networks|journal=Phys. Rev. Lett.|date=2000|volume=85|issue=21|pages=4629–4632|arxiv=cond-mat/0005139|doi=10.1103/physrevlett.85.4629|pmid=11082613|bibcode=2000PhRvL..85.4629K|s2cid=16251662}}</ref>

==  Super-linear preferential attachment  ==

If ''α''&nbsp;>&nbsp;1 then a few nodes tend to connect to every other node in the network. For ''α''&nbsp;>&nbsp;2 this process happens more extremely, the number of connections between other nodes is still finite in the limit when ''n'' goes to infinity. So the degree of the largest hub is proportional to the system size:<ref name="Connectivity of Growing Random Networks"/>

: <math> k_{\max} \sim n. \, </math>

== References ==
{{reflist}}

[[Category:Networks]]
[[Category:Network theory]]