Model Price'a

Model Price'a (nazwany na cześć fizyka Dereka J. de Solli Price'a ) to matematyczny model rozwoju sieci cytowań . Był to pierwszy model, który uogólnił model Simona do zastosowania w sieciach, zwłaszcza w przypadku sieci rozwijających się. Model Price'a należy do szerszej klasy modeli rozwoju sieci (wraz z modelem Barabásiego-Alberta ), których głównym celem jest wyjaśnienie pochodzenia sieci o silnie skośnych rozkładach stopni. Model przejął idee modelu Simona odzwierciedlając koncepcję bogaci stają się bogatsi , znany również jako efekt Mateusza . Price wziął przykład sieci cytowań pomiędzy artykułami naukowymi i przedstawił jej właściwości. Jego pomysł polegał na tym, że sposób, w jaki stary wierzchołek (istniejący artykuł) otrzymuje nowe krawędzie (nowe cytaty), powinien być proporcjonalny do liczby istniejących krawędzi (istniejących cytatów), które już ma wierzchołek. Nazywano to skumulowaną korzyścią , obecnie znaną również jako preferencyjne przywiązanie . Praca Price'a jest również znacząca, ponieważ dostarczyła pierwszy znany przykład sieci bezskalowej (choć termin ten wprowadzono później). Jego pomysły posłużyły do ​​opisania wielu sieci w świecie rzeczywistym, takich jak Internet .

Model

Podstawy

Biorąc pod uwagę graf skierowany z n węzłami. Niech oznaczą ułamek węzłów o stopniu $k,$${\ displaystyle \ suma _ {k} {p_ {k}} =$ że ∑ . Każdy nowy węzeł ma określony stopień out-stopnia (mianowicie te dokumenty, które cytuje) i jest on ustalony w dłuższej perspektywie. Nie oznacza to, że stopnie wyjścia nie mogą różnić się w poszczególnych węzłach, po prostu zakładamy, że średni stopień wyjścia m jest stały w czasie. Jasne jest, że ${\ displaystyle \ suma _ {k} {kp_ {k}} = m}$ , w konsekwencji m nie ogranicza się do liczb całkowitych. Najbardziej trywialna forma preferencyjnego dołączenia oznacza, że ​​nowy węzeł łączy się z istniejącym węzłem proporcjonalnie do jego stopni. Innymi słowy, nowy artykuł cytuje istniejący artykuł proporcjonalnie do jego stopnia. Zastrzeżeniem takiego pomysłu jest to, że po przyłączeniu do sieci nie jest cytowana żadna nowa praca, zatem prawdopodobieństwo jej cytowania w przyszłości będzie zerowe (co niekoniecznie się zdarza). Aby temu zaradzić, Price zaproponował, aby przywiązanie było proporcjonalne dla niektórych $displaystyle k + k_$${0} }$ ze stałą. Ogólnie rzecz biorąc $być$$może$ dowolne, ale Price proponuje, aby w ten sposób początkowy był powiązany z samym artykułem (więc współczynnik wynosi teraz k + 1 zamiast k ). Prawdopodobieństwo, że nowa krawędź połączy się z dowolnym węzłem o stopniu k , wynosi

${\ Displaystyle {\ Frac {(k + 1) p_ {k}} {\ suma _ {k }(k+1)p_{k}}}={\frac {(k+1)p_{k}}{m+1}}}$

Ewolucja sieci

Kolejnym pytaniem jest zmiana netto liczby węzłów o stopniu k po dodaniu nowych węzłów do sieci. Naturalnie liczba ta maleje, ponieważ niektóre k -stopnia mają nowe krawędzie, stając się w ten sposób węzłami ( k + 1) -stopnia; ale z drugiej strony liczba ta również rośnie, ponieważ niektóre węzły ( k - 1) stopnia mogą uzyskać nowe krawędzie, stając się węzłami k stopnia. Aby formalnie wyrazić tę zmianę netto, oznaczmy ułamek k -stopniowych węzłów w sieci n wierzchołków za pomocą ${\ displaystyle p_ {k, n}}$ :

${\ displaystyle ( n+1)p_{k,n+1}-np_{k,n}=[kp_{k-1,n}-(k+1)p_{k,n}]{\frac {m}{m +1}}{\text{ dla }}k\geq 1,}$

I

${\ Displaystyle (n+1) p_ {0, n+1} -np_ {0 ,n}=1-p_{0,n}{\frac {m}{m+1}}{\text{ for }}k=0.}$

Aby otrzymać stacjonarne rozwiązanie dla , najpierw wyrażmy ${\ displaystyle p_ {k, n+1} = p_ {k, n} = p_ {k}$${\ displaystyle p_ {k}}$ stosując dobrze znaną metodę równania głównego , as.

${\ displaystyle p_ {k} = {\ początek {przypadki }[kp_{k-1}-(k+1)p_{k}]{\frac {m}{m+1}}&{\text{for }}k\geq 1\\1-p_{0 }{\frac {m}{m+1}}&{\text{for }}k=0\end{przypadki}}}$

Po pewnych manipulacjach powyższe wyrażenie ulega

${\ Displaystyle p_ {0} = {\ Frac {m + 1} {2m + 1}}}$

I

${\ Displaystyle p_ {k} = {\ Frac {k!}{(k+2+1/m)\cdots (3+1/m)}}p_{0}=(1+1/m)\mathbf {B} (k+1,2+1 /M),}$

gdzie ${\ displaystyle \ mathbf {B} (a, b)}$ jest funkcją Beta . W rezultacie ${\ Displaystyle p_ {k} \ sim k ^ {- (2 + 1 / m)}$ } Jest to identyczne ze stwierdzeniem, $następuje$ rozkład potęgowy z ${\ displaystyle \ alfa = 2 + 1 / m}$ . Zazwyczaj powoduje to umieszczenie wykładnika pomiędzy 2 a 3, co ma miejsce w przypadku wielu sieci w świecie rzeczywistym. Price przetestował swój model, porównując dane z sieci cytowań i doszedł do wniosku, że uzyskane m jest wykonalne w celu uzyskania wystarczająco dobrego rozkładu potęgowego .

Uogólnienie

$gdy$ przypadek, . Pokazują to podstawowe obliczenia

${\ Displaystyle p_ {k} = {\ Frac {m +k_{0}}{m(k_{0}+1)+k_{0}}}{\frac {\mathbf {B} (k+k_{0},2+k_{0}/m)} {\ mathbf {B} (k_{0},2+k_{0}/m)}},}$

co ponownie prowadzi do rozkładu prawa potęgowego z $}$ samym wykładnikiem $p_ {k$ k p naprawiono $displaystyle k_ {0}}$ \

Nieruchomości

Kluczowa różnica w stosunku do nowszego modelu Barabásiego – Alberta polega na tym, że model Price'a tworzy wykres z skierowanymi krawędziami, podczas gdy model Barabásiego – Alberta jest tym samym modelem, ale z nieskierowanymi krawędziami. Kierunek jest kluczowy dla sieci cytowań , która zmotywowała Price'a. Oznacza to, że model Price'a tworzy skierowany graf acykliczny , a sieci te mają charakterystyczne właściwości.

Na przykład w skierowanym grafie acyklicznym dobrze zdefiniowane są zarówno najdłuższe , jak i najkrótsze ścieżki . W modelu Price długość najdłuższej ścieżki od n-tego węzła dodanego do sieci do pierwszego węzła w sieci jest skalowana w następujący sposób. ${\ displaystyle \ ln (n)}$

Notatki

Dalsze omówienie można znaleźć w sekcjach i. Price był w stanie wyprowadzić te wyniki, ale tylko tyle mógł osiągnąć, bez zapewnienia zasobów obliczeniowych. Na szczęście niedawny postęp technologiczny umożliwił wiele pracy poświęconej preferencyjnym przyłączeniom i rozwojowi sieci .

Źródła

•    Newmana, MEJ (2003). „Struktura i funkcja sieci złożonych”. Przegląd SIAM . 45 (2): 167–256. arXiv : cond-mat/0303516 . Kod Bib : 2003SIAMR..45..167N . doi : 10.1137/s003614450342480 . ISSN 0036-1445 . S2CID 221278130 .