Närhetsgrad (grafteori)

Graden av närhet för en nod (till andra noder) är ett mått på centralitet i nätverket, beräknat som den reciproka summan av längderna av de kortaste vägarna mellan noden och alla andra noder i grafen. Således, ju mer central en nod är, desto närmare är den alla andra noder.

Definition

Graden av närhet definierades av Alex Bavelas 1950 som det ömsesidiga avståndet [1] [2] , dvs.

där är lika med avståndet mellan hörnen och . När man talar om graden av närhet menar de vanligtvis dess normaliserade form, vilket är de genomsnittliga kortaste vägarna istället för deras summa. Det ges vanligtvis av föregående formel multiplicerat med , där är lika med antalet grafnoder. För stora grafer blir denna skillnad obetydlig, så den utelämnas:

Detta ändringsförslag tillåter jämförelser mellan noder av grafer av olika storlekar.

Att ta hänsyn till avstånd från eller till andra noder är meningslöst för oriktade grafer, medan det kan ge ganska olika resultat för riktade grafer (t.ex. en webbplats kan ha hög närhet för utgående anslutningar, men låg närhet för inkommande anslutningar).

I frånkopplade grafer

Om grafen inte är starkt kopplad är det en vanlig idé att använda summan av de reciproka avstånden istället för den reciproka av summan av avstånden, enligt konventionen att :

Den mest naturliga modifieringen av Bavelas definition av närhet är följande allmänna princip som föreslås av Marchioni och Latora (2000) [3] : i grafer med obegränsade avstånd beter sig det harmoniska medelvärdet bättre än det aritmetiska medelvärdet. Dessutom kan Bavelos närhet beskrivas som den onormaliserade reciproka av de aritmetiska medelavstånden , medan harmonisk centralitet är lika med den onormaliserade reciproka av de harmoniska medelavstånden .

Denna idé angavs uttryckligen för riktade grafer av Dekker som kallas värderad centralitet [ 4] och Rochat kallad harmonisk centralitet (2009) [5] . Garg axiomatiserade konceptet (2009) [6] , medan Opsal föreslog det igen (2010) [7] . Konceptet studerades på generella riktade grafer av Baldy och Vigna (2014) [8] . Denna idé är mycket lik marknadsföringspotentialen som föreslås av Harris (1954) [9] som nu ofta kallas för marknadstillträde [10] .  

Alternativ

Dangalchev (2006) [11] föreslog en annan definition för oriktade grafer i sitt arbete om nätverkssårbarhet:

Denna definition är effektiv för osammanhängande grafer och tillåter oss att använda en bekväm formulering av operationer på grafer. Till exempel:

  1. Om en graf skapas genom att koppla en grafnod till en grafnod , är graden av närhet för den kombinerade grafen:
  2. Om grafen är en tagggraf [ 12 ] av en graf som har noder, är närhetsgraden [13] : 

Naturlig generalisering av definitionen [14] :

där tillhör intervallet (0,1). När den ökar från 0 till 1 ändras den generaliserade graden av närhet från en lokal egenskap (grad av ett vertex) till en global (antal anslutna noder).

Informationscentraliteten hos Stephenson och Zelen (1989) är ett annat närhetsmått som beräknar det harmoniska medelvärdet av motståndsavstånden i riktningen för en vertex x , som är mindre om x har många lågresistansvägar som förbinder den med andra hörn [15] .

I den klassiska definitionen av närhet modelleras informationsutbredning med de kortaste vägarna. Denna modell kanske inte är helt realistisk för vissa typer av kommunikationsscenarier. Besläktade definitioner av närhetsmått har diskuterats, såsom graden av närhet längs slumpmässiga vägar som föreslagits av Hoh och Rieger (2004). Detta mått mäter den hastighet med vilken slumpmässiga meddelandevägar når toppen från var som helst i grafen, en variant av närhet baserad på slumpmässiga promenader [16] . Hierarkisk centralitet Tran och Kwon (2014) [17] är ett utökat närhetsmått baserat på ett annat tillvägagångssätt för att kringgå närhetsgradsbegränsningar för grafer som inte är starkt sammankopplade. Hierarkisk centralitet inkluderar explicit information om den uppsättning andra noder som en given nod kan påverka.

Se även

Anteckningar

  1. ↑ Bavelas, 1950 , sid. 725–730.
  2. ↑ Sabidussi, 1966 , sid. 581–603.
  3. ↑ Marchiori, Latora, 2000 , sid. 539–546.
  4. ↑ Dekker, 2005 .
  5. ↑ Rochat, 2009 .
  6. ↑ Garg, 2009 .
  7. ↑ Opsahl, 2010 .
  8. ↑ Boldi, Vigna, 2014 , sid. 222–262.
  9. ↑ Harris, 1954 , sid. 315–348.
  10. ↑ Gutberlet, 2014 .
  11. ↑ Dangalchev, 2006 , sid. 556.
  12. ↑ En tagggraf av en graf G är en graf som erhålls genom att lägga till ett visst antal ytterligare hängande hörn  till varje nod i grafen G , det vill säga hörn som endast är associerade med denna nod ( Azari 2018 ).
  13. ↑ Dangalchev, 2018 , sid. 1–15.
  14. ↑ Dangalchev, 2011 , sid. 1939–1948
  15. ↑ Stephenson och Zelen 1989 , sid. 1–37.
  16. ↑ Noh, Rieger, 2004 , sid. 118701.
  17. ↑ Tran, Kwon, 2014 .

Litteratur