Модель УПА

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

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

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

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

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

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

Распределение степеней для сети UPA, учитывая $t\rightarrow \infty$ и $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}}

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

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}}

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

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}}

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

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

Реддит

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

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

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

Связанная работа

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

Ссылки

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

[pachon2017-1] Перейти обратно: ^а ^б ^с Пашон, Анжелика; Сасердот, Лаура; Ян, Шуйи. Безмасштабное поведение сетей при сосуществовании предпочтительных и единых правил присоединения . Математический факультет «Г. Пеано», Туринский университет, 2017.

[ambroggio2019-2] де Амброджо, Умберто; Сасердот, Лаура; Полито, Фредерико. О динамических случайных графах со степенью гомогенизации посредством антипреференциальных вероятностей прикрепления . Математический факультет «Г. Пеано», Туринский университет, 2019.

[1]

[2]