Modelul Barabashi-Albert

Modelul Barabashi-Albert (BA) este un algoritm pentru generarea de rețele aleatoare fără scară folosind principiul atașării preferențiale. Rețelele fără scară sunt răspândite în rețele naturale (lanțuri alimentare) și rețele create de om ( Internet , World Wide Web , rețele de citare , unele rețele sociale ).

Concepte

Multe rețele aflate în studiu se încadrează în clasa rețelelor fără scară. Aceasta înseamnă că au o distribuție a legii puterii în grad de nod, în timp ce modelele grafice aleatoare ( Watts-Stregatzși Erdős-Renyi ) nu au o astfel de distribuție. Modelul Barabasi-Albert este unul dintre câteva modele propuse pentru legea puterii care generează rețele fără scară. Include două concepte generale importante:

creșterea rețelei
Principiul de atașament preferat (PP)

Ambele concepte sunt larg reprezentate în rețelele din lumea reală. Creșterea înseamnă că numărul de noduri de rețea crește în timp.

Principiul atașării preferențiale este că, cu cât un nod are mai multe conexiuni, cu atât este mai preferabil ca acesta să creeze conexiuni noi. Nodurile cu cel mai înalt grad au mai multe oportunități de a prelua legăturile adăugate în rețea. Intuitiv, principiul atașamentului preferențial poate fi înțeles dacă gândim în termeni de rețele sociale care reunesc oamenii. Aici, o conexiune de la A la B înseamnă că persoana A „știe” sau este „familiarizată” cu persoana B. Nodurile puternic conectate sunt reprezentate de oameni cunoscuți cu un număr mare de conexiuni. Când un nou venit intră în comunitate, este mai de preferat ca acesta/ea să contacteze una dintre persoanele cunoscute decât una relativ necunoscută. În mod similar, pe World Wide Web, paginile sunt asociate cu hub-uri, cum ar fi site-uri binecunoscute precum Google sau Wikipedia , mai degrabă decât cu pagini care nu sunt binecunoscute. Dacă o pagină nouă este selectată aleatoriu pentru conectare, atunci probabilitatea de a alege o anumită pagină va fi proporțională cu gradul acesteia. Așa se explică principiul atașamentului preferențial.

Principiul atașării preferențiale este un exemplu de feedback pozitiv, în care variațiile inițial aleatorii (un nod are inițial mai multe legături sau începe să colecteze legături mai devreme decât altele) sunt amplificate automat, crescând astfel foarte mult decalajul. Acesta este uneori numit și efectul Matei , „bogații se îmbogățesc” sau autocataliza în chimie.

Algoritm

Rețeaua începe cu o plasă inițială cu noduri. iar gradul fiecărui nod din rețeaua inițială trebuie să fie de cel puțin 1, altfel acesta va fi întotdeauna separat de restul rețelei. $m_{0}$ $m_{0}>=2$

La fiecare moment, un nou nod este adăugat în rețea. Fiecare nod nou se conectează la nodurile existente cu o probabilitate proporțională cu numărul de conexiuni ale acestor noduri. Formal, probabilitatea ca un nou nod să se conecteze la nodul i este: [1] $p_{i}$

p_{i}={k_{i} \over \sum _{j}k_{j))

unde este gradul nodului i, iar numitorul însumează gradele tuturor nodurilor existente. Cele mai conectate noduri („hubs”) tind să acumuleze și mai multe conexiuni, în timp ce nodurile cu un număr mic de conexiuni este puțin probabil să fie alese pentru a se alătura nodurilor noi. Nodurile noi au o „preferință” de a se conecta cu cele mai conectate noduri. $k_i$

Proprietăți

Distribuția energiei

Distribuția legii puterii în modelul BA este fără scară, mai precis, se supune legii puterii

P\stanga(k\dreapta)\sim k^{-3)

Lungimea medie a căii

Lungimea medie a căii în modelul BA crește în medie ca logaritmul mărimii rețelei. Forma exactă are o corecție dublă logaritmică [1] și arată ca

\ell \sim {\frac {\ln N}{\ln \ln N)).

Modelul BA are o cale medie sistematic mai scurtă decât un grafic aleatoriu.

Corelații de gradul nodului

Corelațiile gradelor de noduri conectate se dezvoltă aleatoriu în modelul BA, datorită particularităților dezvoltării rețelei. Probabilitatea de a găsi o legătură între nodurile cu grade și în modelul BA este prezentată ca

n_{k\ell}={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+) \ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right) \left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.

Desigur, rezultatul va fi diferit dacă distribuția a fost necorelată, . $n_{k\ell}=k^{-3}\ell ^{-3)$

Coeficientul de grupare

Nu există încă valori analitice ale coeficientului de clustering al modelului BA. Coeficienții de clusterizare obținuți empiric sunt în general mult mai mari pentru modelul BA decât pentru rețelele aleatoare. Coeficientul de grupare depinde, de asemenea, de dimensiunea rețelei conform unei legi aproximative a puterii:

C\sim N^{-0,75}.

[unu]

Acest comportament este încă diferit de comportamentul rețelelor mici, unde gruparea nu depinde de dimensiunea rețelei. În cazul rețelelor ierarhice, gruparea în funcție de gradul nodului respectă și o lege a puterii:

C(k)=k^{-1}.

Aceste rezultate au fost obținute analitic de Dorogovtsev, Goltsev și Mendes. [3]

Calități spectrale

Forma densității spectrale a modelului BA diferă de densitatea spectrală semicirculară a unui grafic aleatoriu. Are o formă triunghiulară cu un vârf situat mult mai sus decât un semicerc, iar marginile scad conform unei legi de putere.

Cazuri limită

Model A

Modelul A păstrează creșterea, dar nu include principiul atașamentului preferențial. Probabilitatea de a alătura un nou nod cu cele existente este aceeași peste tot. Distribuția în grade finite în acest caz sugerează că doar creșterea nu este suficientă pentru a obține o structură fără scară.

Model B

Modelul B păstrează principiul atașamentului preferențial, dar exclude creșterea. Modelul începe cu un număr fix de noduri deconectate și adaugă legături, alegând de preferință noduri de grad înalt ca destinații. Deși distribuția de putere pare să fie fără scară la începutul simulării, este instabilă și în cele din urmă devine aproape de Gaussian pe măsură ce rețeaua se apropie de saturație. Astfel, principiul PP în sine nu este suficient pentru a crea o structură fără scară. [unu]

Eșecul modelelor A și B de a obține o distribuție fără scară sugerează că creșterea și PP sunt la fel de necesare pentru a reproduce distribuția staționară a legii puterii văzută în rețelele din lumea reală.

Istorie

Principiul atașamentului preferențial a fost folosit pentru prima dată pentru a explica distribuția legii puterii lui Yule în 1925 [4] , deși analiza matematică a lui Yule este considerată obscură de standardele moderne din cauza lipsei instrumentelor adecvate pentru analiza proceselor aleatorii. Metoda modernă a ecuației cinetice de bază, care dă o concluzie mai transparentă, a fost aplicată problemei de Herbert Simon în 1955 [5] în cursul studierii dimensiunii orașelor și a altor fenomene. A fost aplicat pentru prima dată creșterii rețelelor de către Derek de Solla Price în 1976, [6] care a fost interesat de rețelele de citare între publicațiile științifice. Numele „interconectare preferată” și popularitatea actuală a modelelor de rețea fără scară se datorează muncii lui Albert-Laszlo Barabasi și Reki Albert, care a descoperit independent procesul în 1999 și l-a aplicat distribuției legii puterii pe World Wide Web. [2]

Note

↑ 1 2 3 4 Albert, Reka; R. Albert; A.L. Barabasi. Mecanica statistică a rețelelor complexe (engleză) // Reviews of Modern Physics : journal. - 2002. - Vol. 74 . - P. 47-97 . - doi : 10.1103/RevModPhys.74.47 . - Cod biblic . Arhivat din original pe 24 august 2015.
↑ 1 2 Albert-László Barabási & Reka Albert Apariția scalarii în rețele aleatoare (engleză) // Science : journal. - 1999. - octombrie ( vol. 286 , nr. 5439 ). - P. 509-512 . - doi : 10.1126/science.286.5439.509 . Arhivat din original pe 17 aprilie 2012.
↑ SN Dorogovtsev, AV Goltsev și JFF Mendes, e-print cond-mat/0112143.
↑ Yule, G. Udny . O teorie matematică a evoluției bazată pe concluziile lui Dr. JC Willis, FRS // Jurnalul Societății Regale de Statistică : jurnal. - 1925. - Vol. 88 , nr. 3 . - P. 433-436 . - doi : 10.2307/2341419 . — .
↑ Herbert A. Simon . On a Class of Skew Distribution Functions (în engleză) // Biometrika : journal. - 1955. - Decembrie ( vol. 42 , nr. 3-4 ). - P. 425-440 . - doi : 10.1093/biomet/42.3-4.425 .
↑ DJ de Solla Price . O teorie generală a proceselor bibliometrice și a altor avantaje cumulate (engleză) // Journal of the American Society for Information Science : jurnal. - 1976. - Vol. 27 . - P. 292-306 . - doi : 10.1002/asi.4630270505 .

Link -uri

Rețele complexe