Модель УПА - UPA model

При анализе социальные сети, то Модель Uniform-Preferential-Attachment, или же Модель УПА это вариант Модель Барабаши – Альберта в котором предпочтительная привязанность воспринимается как имеющая двойную природу. Новые узлы, присоединяющиеся к сети, могут либо присоединяться к узлам высокого уровня, либо к недавно добавленным узлам. Такое поведение можно заметить на некоторых примерах социальных сетей, таких как сеть цитирования научных публикаций. ^[1]

Описание модели

Для сети UPA с узлами ${\displaystyle \{v_{1}...v_{t}\}}$, определим для приходящего узла ${\displaystyle v_{t+1}}$ подмножество узлов ${\displaystyle \{v_{t-w+1}...v_{t}\}}$ с ${\displaystyle w\in \mathbb {N} }$. Это подмножество называется окно, который представляет собой ш последние узлы, вставленные в сеть. Новый узел может связать себя либо с узлом из подмножества окон, с вероятностью п, или с любым другим узлом из ${\displaystyle \{v_{1}...v_{t}\}}$ с вероятностью 1-п. В первом случае распределение вероятностей узлов равномерно: каждый узел имеет вероятность ${\displaystyle 1/w}$ быть выбранным. В последнем случае выбор узла следует правилу предпочтительного присоединения, как в Модель Барабаши – Альберта.

Размер окна ${\displaystyle l}$ может быть постоянным при добавлении новых узлов, что выражается ${\displaystyle w:=w(t)=l}$, куда ${\displaystyle t}$ дискретная временная переменная. Он также может со временем расти в соответствии с ${\displaystyle w:=w(t)=\lceil \alpha t\rceil }$, куда ${\displaystyle 0<\alpha <1}$, что означает, что рост размера окна линейно зависит от размера сети. Сеть сохраняет асимптотику сила закона поведение в распределение степеней для обоих случаев.

Обратите внимание, что когда ${\displaystyle l=1}$ и ${\displaystyle p=0}$, модель UPA сводится к Модель Барабаши – Альберта. ^[1]

Распределение степеней

В распределение степеней для сети UPA, учитывая ${\displaystyle t\rightarrow \infty }$ и ${\displaystyle l=1}$:

${\displaystyle 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}}}$

И для ${\displaystyle l>1}$ у нас есть:

${\displaystyle 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}}}$

Где ${\displaystyle B(x,y)}$ это Бета-функция и ${\displaystyle H_{k}}$ является:

${\displaystyle 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}}}$

Демонстрация этих формул включает анализ рекурсивных функций и Неравенство Адзумы-Хёффдинга. Наблюдается, что для ${\displaystyle l=1}$ и ${\displaystyle p=0}$, распределение степеней следует сила закона с показателем ${\displaystyle \gamma =-3}$, как и ожидалось для эквивалентного Модель Барабаши – Альберта. Также доказано, что при любой вероятности ${\displaystyle p}$ и размер окна ${\displaystyle l}$, сеть асимптотически следует степенному закону и, таким образом, сохраняет свое безмасштабное поведение. ^[1]

События в реальном мире

Reddit

Сеть UPA может использоваться для моделирования Reddit положительные голоса (upvotes). Рассмотрим каждый узел, представленный сообщением ${\displaystyle \mathbb {P} }$ и ссылки, представляющие голоса за, данные автором после публикации ${\displaystyle \mathbb {P} }$. Каждый раз, когда пользователь публикует комментарий, он или она обычно ищет в той же теме другой пост, чтобы прокомментировать, что характеризует однообразное вложение. Однако этому пользователю может быть интереснее поискать другую тему для комментариев, возможно, популярную. Последние представляют собой предпочтительное присоединение в сетевой модели UPA.

Сеть цитирования

А сеть цитирования научных публикаций обычно представлены научными статьями в виде узлов и цитатами в виде ссылок. Рассматривая сеть статей из одной и той же области знаний, всякий раз, когда в эту сеть вставляется новый узел, он либо присоединяется к последним публикациям (единообразное прикрепление), либо к наиболее важным статьям в своей области знаний (предпочтительное прикрепление). Таким образом, общее поведение этих сетей можно описать моделью UPA.

Связанных с работой

• Вместо двойной природы, включающей единообразные и предпочтительные привязки, сеть может сочетать предпочтительные и антипреференциальные привязанности. В этой сетевой модели узлы могут быть вставлены или удалены из сети с течением времени. ${\displaystyle t}$. ^[2]

Рекомендации

1. Пахон, Анжелика; Сакердот, Лаура; Ян, Шуйи. Безмасштабное поведение сетей при одновременном наличии льготных и единых правил присоединения. Математический факультет «Г. Пеано », Туринский университет, 2017.
2. де Амброджио, Умберто; Сакердот, Лаура; Полито, Фредерико. На динамических случайных графах со степенью гомогенизации через антипреференциальные вероятности прикрепления. Математический факультет «Г. Пеано », Туринский университет, 2019.