Gradul de proximitate (teoria graficelor)

Gradul de proximitate a unui nod (față de alte noduri) este o măsură a centralității în rețea, calculată ca reciproca sumei lungimilor celor mai scurte căi dintre nod și toate celelalte noduri din grafic. Astfel, cu cât un nod este mai central , cu atât este mai aproape de toate celelalte noduri.

Definiție

Gradul de proximitate a fost definit de Alex Bavelas în 1950 ca reciproca distanței [1] [2] , i.e.

unde este egală cu distanța dintre vârfuri și . Când se vorbește despre gradul de apropiere, de obicei se referă la forma sa normalizată, care este cea mai scurtă cale medie în loc de suma lor. Este de obicei dat de formula anterioară înmulțită cu , unde este egal cu numărul de noduri ale graficului. Pentru graficele mari, această diferență devine nesemnificativă, așa că este omisă:

Acest amendament permite compararea între nodurile de grafice de diferite dimensiuni.

Luarea în considerare a distanțelor de la sau față de alte noduri este lipsită de sens pentru graficele nedirecționate, în timp ce poate da rezultate destul de diferite pentru graficele direcționate (de exemplu, un site web poate avea o proximitate mare pentru conexiunile de ieșire, dar proximitate scăzută pentru conexiunile de intrare).

În graficele deconectate

Dacă graficul nu este puternic conectat , este o idee comună să folosiți suma reciprocelor distanțelor în loc de reciproca sumei distanțelor, conform convenției că :

Cea mai firească modificare a definiției lui Bavelas a proximității este următorul principiu general propus de Marchioni și Latora (2000) [3] : în graficele cu distanțe nelimitate, media armonică se comportă mai bine decât media aritmetică. Mai mult, proximitatea Bavelos poate fi descrisă ca reciproca nenormalizată a distanțelor medii aritmetice , în timp ce centralitatea armonică este egală cu reciproca nenormalizată a distanțelor medii armonice .

Această idee a fost enunțată în mod explicit pentru graficele direcționate de către Dekker numită centralitate valoroasă [ 4] și Rochat numită centralitate armonică (2009) [5] . Garg a axiomatizat conceptul (2009) [6] , în timp ce Opsal l-a propus din nou (2010) [7] . Conceptul a fost studiat pe grafice generale direcționate de Baldy și Vigna (2014) [8] . Această idee este foarte asemănătoare cu potențialul de marketing propus de Harris (1954) [9] care acum este adesea denumit acces pe piață [10] .  

Opțiuni

Dangalchev (2006) [11] a propus o altă definiție pentru graficele nedirecționate în lucrarea sa despre vulnerabilitatea rețelei:

Această definiție este eficientă pentru graficele neconectate și ne permite să folosim o formulare convenabilă a operațiilor pe grafice. De exemplu:

  1. Dacă un grafic este creat prin conectarea unui nod de grafic la un nod de grafic , atunci gradul de proximitate al graficului combinat este:
  2. Dacă graficul este un graf spin [ 12] al unui graf care are noduri, atunci gradul de proximitate este [13] : 

Generalizarea naturală a definiției [14] :

unde aparține intervalului (0,1). Când crește de la 0 la 1, gradul generalizat de proximitate se schimbă de la o caracteristică locală (gradul unui vârf) la una globală (număr de noduri conectate).

Centralitatea informațională a lui Stephenson și Zelen (1989) este o altă măsură de proximitate care calculează media armonică a distanțelor de rezistență în direcția unui vârf x , care este mai mică dacă x are multe căi de rezistență scăzută care îl conectează la alte vârfuri [15] .

În definiția clasică a apropierii, propagarea informațiilor este modelată folosind cele mai scurte căi. Acest model poate să nu fie complet realist pentru anumite tipuri de scenarii de comunicare. Au fost discutate definiții înrudite ale măsurilor de proximitate, cum ar fi gradul de proximitate pe căi aleatorii propus de Hoh și Rieger (2004). Această măsurătoare măsoară rata la care căile aleatorii ale mesajelor ajung în partea de sus de oriunde în grafic, o variantă de proximitate bazată pe plimbări aleatorii [16] . Centralitatea ierarhică Tran și Kwon (2014) [17] este o măsură extinsă de apropiere bazată pe o abordare diferită pentru a evita limitările gradului de apropiere pentru graficele care nu sunt puternic conectate. Centralitatea ierarhică include în mod explicit informații despre setul de alte noduri pe care le poate afecta un anumit nod.

Vezi și

Note

  1. ↑ Bavelas, 1950 , p. 725–730.
  2. ↑ Sabidussi, 1966 , p. 581–603.
  3. ↑ Marchiori, Latora, 2000 , p. 539–546.
  4. ↑ Dekker, 2005 .
  5. ↑ Rochat, 2009 .
  6. ↑ Garg, 2009 .
  7. ↑ Opsahl, 2010 .
  8. ↑ Boldi, Vigna, 2014 , p. 222–262.
  9. ↑ Harris, 1954 , p. 315–348.
  10. ↑ Gutberlet, 2014 .
  11. ↑ Dangalchev, 2006 , p. 556.
  12. ↑ Un graf spin al unui graf G  este un graf obținut prin adăugarea fiecărui nod al grafului G a unui anumit număr de vârfuri suspendate suplimentare , adică vârfuri asociate doar cu acest nod ( Azari 2018 ).
  13. ↑ Dangalchev, 2018 , p. 1–15.
  14. ↑ Dangalchev, 2011 , p. 1939–1948
  15. ↑ Stephenson și Zelen 1989 , p. 1–37.
  16. ↑ Noh, Rieger, 2004 , p. 118701.
  17. ↑ Tran, Kwon, 2014 .

Literatură