Model UPA - UPA model

V analýze sociální sítě, Uniform-Preference-Attachment modelnebo Model UPA je variace Barabási – Albertův model ve kterém je preferenční vazba vnímána jako dvojí. Nové uzly připojující se k síti se mohou buď připojit k uzlům vysokého stupně, nebo k naposledy přidaným uzlům. Toto chování lze zaznamenat na některých příkladech sociálních sítí, jako je citační síť vědeckých publikací. ^[1]

Popis modelu

Pro síť UPA s uzly ${ displaystyle {v_ {1} ... v_ {t} }}$ , definujeme pro přicházející uzel ${ displaystyle v_ {t + 1}}$ podmnožina uzlů ${ displaystyle {v_ {t-w + 1} ... v_ {t} }}$ s ${ displaystyle w in mathbb {N}}$ . Tato podmnožina se nazývá a okno, což představuje w poslední uzly vložené do sítě. Nový uzel se může s pravděpodobností propojit buď s uzlem z podmnožiny okna p, nebo s jakýmkoli jiným uzlem z ${ displaystyle {v_ {1} ... v_ {t} }}$ s pravděpodobností 1-p. V prvním případě je rozdělení pravděpodobnosti uzlu jednotné: každý uzel má pravděpodobnost ${ displaystyle 1 / w}$ být vyvolen. V druhém případě se výběr uzlu řídí preferenčním pravidlem přílohy, jako v Barabási – Albertův model.

Velikost okna ${ displaystyle l}$ může být konstantní během přidávání nových uzlů, vyjádřeno ${ displaystyle w: = w (t) = l}$ , kde ${ displaystyle t}$ je diskrétní časová proměnná. Může také růst s časem podle ${ displaystyle w: = w (t) = lceil alpha t rceil}$ , kde ${ displaystyle 0 < alpha <1}$ , což znamená, že růst velikosti okna je lineární s velikostí sítě. Síť je stále asymptotická mocenský zákon chování v rozdělení stupňů pro oba případy.

Všimněte si, že když ${ displaystyle l = 1}$ a ${ displaystyle p = 0}$ , model UPA se redukuje na Barabási – Albertův model. ^[1]

Distribuce stupňů

The rozdělení stupňů pro síť UPA je, s ohledem ${ displaystyle t rightarrow infty}$ a ${ 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}}) { lišta {P}} (2) & { mbox {if}} k> 2 end {případy}}}

A pro ${ displaystyle l> 1}$ my máme:

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

Kde ${ displaystyle B (x, y)}$ je Funkce Beta a ${ displaystyle H_ {k}}$ je:

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

Demonstrace těchto vzorců zahrnuje analýzu rekurzivních funkcí a Azuma-Hoeffding Nerovnost. Je vidět, že pro ${ displaystyle l = 1}$ a ${ displaystyle p = 0}$ , rozdělení stupňů následuje a mocenský zákon s exponentem ${ displaystyle gamma = -3}$ , jak se u ekvivalentu očekávalo Barabási – Albertův model. Je také dokázáno, že pro každou pravděpodobnost ${ displaystyle p}$ a velikost okna ${ displaystyle l}$ , síť asymptoticky dodržuje zákon o moci a zachovává si tak své volné chování v měřítku. ^[1]

Výskyty v reálném světě

Reddit

K modelování lze použít síť UPA Reddit kladné hlasy (hlasy proti). Zvažte každý uzel představovaný příspěvkem ${ displaystyle mathbb {P}}$ a odkazy představující upvotes dané autorem po zveřejnění ${ displaystyle mathbb {P}}$ . Kdykoli uživatel přidá komentář, obvykle hledá ve stejném tématu jiný příspěvek, který by mohl komentovat, což charakterizuje jednotnou přílohu. Tento uživatel však může také považovat za zajímavější hledat jiné téma ke komentování, možná populární. Ty představují preferenční přílohu v modelu sítě UPA.

Citační síť

A citační síť vědeckých publikací obvykle představují vědecké práce jako uzly a citace jako odkazy. Pokud vezmeme v úvahu síť příspěvků ze stejné oblasti znalostí, kdykoli je do této sítě vložen nový uzel, připojí se buď k nejnovějším publikacím (jednotná příloha), nebo k nejdůležitějším příspěvkům ve své oblasti odbornosti (preferenční příloha). Obecné chování těchto sítí lze tedy popsat modelem UPA.

Související práce

Namísto dvojí povahy zahrnující uniformní a preferenční přílohu může síť kombinovat preferenční a anti-preferenční přílohy. V tomto síťovém modelu lze uzly s postupem času buď vkládat, nebo odebírat ze sítě ${ displaystyle t}$ . ^[2]

Reference

^ ^A ^b ^C Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi. Bezškálové chování sítí s výskytem preferenčních a jednotných pravidel připojení. Katedra matematiky „G. Peano “, University of Torino, 2017.
^ de Ambroggio, Umberto; Sacerdote, Laura; Polito, Frederico. Na dynamických náhodných grafech s homogenizací stupně pomocí anti-preferenčních pravděpodobností připojení. Katedra matematiky „G. Peano “, University of Torino, 2019.

[pachon2017-1] A ^b ^C Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi. Bezškálové chování sítí s výskytem preferenčních a jednotných pravidel připojení. Katedra matematiky „G. Peano “, University of Torino, 2017.

[ambroggio2019-2] Ambroggio, Umberto; Sacerdote, Laura; Polito, Frederico. Na dynamických náhodných grafech s homogenizací stupně pomocí anti-preferenčních pravděpodobností připojení. Katedra matematiky „G. Peano “, University of Torino, 2019.

[1]

[2]