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 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.[1] The co-author network among scientists also shows the signs of sub-linear preferential attachment.[2]
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 k:
where α > 0. This is a good approximation for a lot of real networks such as the Internet, the citation network or the actor network. If α = 1 then the preferential attachment is linear. If α < 1 then it is sub-linear while if α > 1 then it is super-linear.[3]
In measuring preferential attachment from real networks, the above log-linearity functional form kα can be relaxed to a free form function, i.e. π(k) can be measured for each k without any assumptions on the functional form of π(k). This is believed to be more flexible, and allows the discovery of non-log-linearity of preferential attachment in real networks.[4]
Sub-linear preferential attachmentedit
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:
so it is smaller than the polynomial dependence.[5]
Super-linear preferential attachmentedit
If α > 1 then a few nodes tend to connect to every other node in the network. For α > 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:[5]
^ abKrapivsky, P. L.; S. Redner; F. Leyvraz (2000). "Connectivity of Growing Random Networks". Phys. Rev. Lett. 85 (21): 4629–4632. arXiv:cond-mat/0005139. Bibcode:2000PhRvL..85.4629K. doi:10.1103/physrevlett.85.4629. PMID 11082613. S2CID 16251662.
December 14, 2023
linear, preferential, attachment, network, science, preferential, attachment, means, that, nodes, network, tend, connect, those, nodes, which, have, more, links, network, growing, nodes, tend, connect, existing, ones, with, linear, probability, degree, existin. 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 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 1 The co author network among scientists also shows the signs of sub linear preferential attachment 2 Contents 1 Types of preferential attachment 2 Sub linear preferential attachment 3 Super linear preferential attachment 4 ReferencesTypes of preferential attachment editFor 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 k p k k a displaystyle pi k sim k alpha nbsp where a gt 0 This is a good approximation for a lot of real networks such as the Internet the citation network or the actor network If a 1 then the preferential attachment is linear If a lt 1 then it is sub linear while if a gt 1 then it is super linear 3 In measuring preferential attachment from real networks the above log linearity functional form ka can be relaxed to a free form function i e p k can be measured for each k without any assumptions on the functional form of p k This is believed to be more flexible and allows the discovery of non log linearity of preferential attachment in real networks 4 Sub linear preferential attachment editIn 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 k max log n 1 1 a displaystyle k max sim log n 1 1 alpha nbsp so it is smaller than the polynomial dependence 5 Super linear preferential attachment editIf a gt 1 then a few nodes tend to connect to every other node in the network For a gt 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 5 k max n displaystyle k max sim n nbsp References edit Kunegis Jerome Blattner Marcel Moser Christine 2013 Preferential Attachment in Online Networks Measurement and Explanations arXiv 1303 6271 Bibcode 2013arXiv1303 6271K a href Template Cite journal html title Template Cite journal cite journal a Cite journal requires journal help Barabasi Albert Laszlo Ch 5 Network Science p 19 Barabasi Albert Laszlo Ch 5 Network Science pp 20 21 Pham Thong Sheridan Paul Shimodaira Hidetoshi September 17 2015 PAFit A Statistical Method for Measuring Preferential Attachment in Temporal Complex Networks PLOS ONE 10 9 e0137796 Bibcode 2015PLoSO 1037796P doi 10 1371 journal pone 0137796 PMC 4574777 PMID 26378457 a b Krapivsky P L S Redner F Leyvraz 2000 Connectivity of Growing Random Networks Phys Rev Lett 85 21 4629 4632 arXiv cond mat 0005139 Bibcode 2000PhRvL 85 4629K doi 10 1103 physrevlett 85 4629 PMID 11082613 S2CID 16251662 Retrieved from https en wikipedia org w index php title Non linear preferential attachment amp oldid 1043748125, wikipedia, wiki, book, books, library,
