In the analysis of social networks, the uniform-preferential-attachment model, or UPA model is a variation of the Barabási–Albert model in which the preferential attachment is perceived as having a double nature. New nodes joining the network may either attach themselves with high-degree nodes or with most recently added nodes. This behaviour can be noticed in some examples of social networks, such as the citation network of scientific publications.[1]

Model description

edit

For an UPA network with nodes  , we define for an arriving node   a subset of nodes   with  . This subset is called a window, which represents the w last nodes inserted into the network. A new node may link itself either with a node from the window subset, with probability p, or with any other node from   with probability 1-p. In the former case, the node probability distribution is uniform: each node has a probability   of being chosen. In the latter, node selection follows a preferential attachment rule, as in the Barabási–Albert model.

The window size   may be constant during the addition of new nodes, expressed by  , where   is a discrete time variable. It can also grow with time in accord to  , where  , which means that window size growth is linear with the size of the network. The network keeps its asymptotic power law behavior in degree distribution for both cases.

Note that when   and  , the UPA model reduces to the Barabási–Albert model.[1]

Degree distribution

edit

The degree distribution for an UPA network is, considering   and  :

 

And for   we have:

 

Where   is the Beta function and   is:

 

The demonstration of these formulae involves the analysis of recursive functions and the Azuma-Hoeffding Inequality. It is observable that for   and  , the degree distribution follows a power law with exponent  , as expected for the equivalent Barabási–Albert model. It is also proven that for every probability   and window size  , the network asymptotically follows a power law and thus keeps its scale free behavior.[1]

Occurrences in real world

edit

Reddit

edit

An UPA network may be used to model Reddit positive votes (upvotes). Consider each node represented by a post   and the links representing upvotes given by the author after posting  . Whenever a user posts a comment, he or she usually look in the same topic for another post to comment on, which characterizes a uniform attachment. However, this user may also find it more interesting to search for another topic to comment on, possibly a popular one. The latter represent a preferential attachment in the UPA network model.

Citation network

edit

A citation network of scientific publications is usually represented by scientific papers as nodes and citations as links. Considering a network of papers from the same field of knowledge, whenever a new node is inserted into this network, it either attaches itself to the latest publications (uniform attachment) or to the most important papers in its field of expertise (preferential attachment). Thus, the general behavior of these networks can be described by an UPA model.

edit
  • Instead of a double nature involving uniform and preferential attachment, a network may combine preferential and anti-preferential attachments. In this network model, nodes can either be inserted or removed from the network with the passing of time  .[2]

References

edit
  1. ^ a b c Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi. Scale-free behavior of networks with the copresence of preferential and uniform attachment rules. Mathematics Department “G. Peano”, University of Torino, 2017.
  2. ^ de Ambroggio, Umberto; Sacerdote, Laura; Polito, Frederico. On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities. Mathematics Department “G. Peano”, University of Torino, 2019.