UPA model

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

For an UPA network with nodes $\{v_{1}...v_{t}\}$ , we define for an arriving node $v_{t+1}$ a subset of nodes $\{v_{t-w+1}...v_{t}\}$ with $w\in \mathbb {N}$ . 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 $\{v_{1}...v_{t}\}$ with probability 1-p. In the former case, the node probability distribution is uniform: each node has a probability $1/w$ of being chosen. In the latter, node selection follows a preferential attachment rule, as in the Barabási–Albert model.

The window size $l$ may be constant during the addition of new nodes, expressed by $w:=w(t)=l$ , where $t$ is a discrete time variable. It can also grow with time in accord to $w:=w(t)=\lceil \alpha t\rceil$ , where $0<\alpha <1$ , 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 $l=1$ and $p=0$ , the UPA model reduces to the Barabási–Albert model.^[1]

Degree distribution

The degree distribution for an UPA network is, considering $t\rightarrow \infty$ and $l=1$ :

P(k)={\begin{cases}{\dfrac {2(1-p)}{3-p}}&{\mbox{ if }}k=1\\{\dfrac {(1-p)^{2}}{(2-p)(3-p)}}+{\dfrac {p}{2-p}}&{\mbox{ if }}k=2\\({\dfrac {2}{1-p}}+2)({\dfrac {2}{1-p}}+1)B(k,1+{\dfrac {2}{1-p}}){\bar {P}}(2)&{\mbox{ if }}k>2\end{cases}}

And for $l>1$ we have:

P(k)={\begin{cases}{\dfrac {2}{(3-p)}}(1-{\dfrac {p}{l}})^{l}&{\mbox{ if }}k=1\\{\dfrac {2}{2+k(1-p)}}({\dfrac {p}{l}}(H_{k-1}-H_{k})+{\dfrac {(1-p)(k-1)}{2}}P(k-1)&{\mbox{ if }}2\leq k\leq l+1\\{\dfrac {B(k,l+2+{\dfrac {2}{1-p}})}{B(l+1,k+1+{\dfrac {2}{1-p}})}}P(l+1)&{\mbox{ if }}k>l+1\end{cases}}

Where $B(x,y)$ is the Beta function and $H_{k}$ is:

H_{k}={\begin{cases}({\dfrac {p}{l}})^{k-1})\sum _{m=1}^{l-(k-1)}{\binom {l-m}{l-m-(k-1)}}(1-{\dfrac {p}{l}})^{l-m-(k-1)}&{\mbox{ if }}1\leq k\leq l\\0&{\mbox{ if }}k>l\end{cases}}

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

Occurrences in real world

Reddit

An UPA network may be used to model Reddit positive votes (upvotes). Consider each node represented by a post $\mathbb {P}$ and the links representing upvotes given by the author after posting $\mathbb {P}$ . 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

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.

Related work

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 $t$ .^[2]

References

^ ^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.
^ 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.

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

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

[1]

[2]