Nærhedsgrad (grafteori)

Graden af ​​nærhed af en knude (til andre knudepunkter) er et mål for centralitet i netværket, beregnet som den gensidige af summen af ​​længderne af de korteste veje mellem knudepunktet og alle andre knudepunkter i grafen. Jo mere central en node er, jo tættere er den på alle andre noder.

Definition

Graden af ​​nærhed blev defineret af Alex Bavelas i 1950 som den gensidige afstand [1] [2] , dvs.

hvor er lig med afstanden mellem hjørnerne og . Når man taler om graden af ​​nærhed, mener de normalt dens normaliserede form, som er den gennemsnitlige korteste vej i stedet for deres sum. Det er normalt givet ved den foregående formel ganget med , hvor er lig med antallet af grafnoder. For store grafer bliver denne forskel ubetydelig, så den udelades:

Dette ændringsforslag tillader sammenligning mellem knudepunkter af grafer af forskellig størrelse.

At overveje afstande fra eller til andre knudepunkter er meningsløst for urettede grafer, mens det kan give ret forskellige resultater for rettede grafer (f.eks. kan et websted have høj nærhed til udgående forbindelser, men lav nærhed for indgående forbindelser).

I afbrudte grafer

Hvis grafen ikke er stærkt forbundet , er det en almindelig idé at bruge summen af ​​de reciproke afstande i stedet for den reciproke af summen af ​​afstandene, under konventionen, at :

Den mest naturlige modifikation af Bavelas' definition af nærhed er følgende generelle princip foreslået af Marchioni og Latora (2000) [3] : i grafer med ubegrænsede afstande opfører den harmoniske middelværdi sig bedre end den aritmetiske middelværdi. Desuden kan Bavelos nærhed beskrives som den unormaliserede gensidige af de aritmetiske middelafstande , mens harmonisk centralitet er lig med den unormaliserede gensidige af de harmoniske middelafstande .

Denne idé blev eksplicit angivet for dirigerede grafer af Dekker kaldet værdisat centralitet [ 4] og Rochat kaldet harmonisk centralitet (2009) [5] . Garg aksiomatiserede konceptet (2009) [6] , mens Opsal foreslog det igen (2010) [7] . Konceptet blev undersøgt på generelle rettede grafer af Baldy og Vigna (2014) [8] . Denne idé minder meget om markedsføringspotentialet foreslået af Harris (1954) [9] , som nu ofte omtales som markedsadgang [10] .  

Indstillinger

Dangalchev (2006) [11] foreslog en anden definition for urettede grafer i sit arbejde med netværkssårbarhed:

Denne definition er effektiv for uforbundne grafer og giver os mulighed for at bruge en bekvem formulering af operationer på grafer. For eksempel:

  1. Hvis en graf oprettes ved at forbinde en grafknude til en grafknude , så er graden af ​​nærhed af den kombinerede graf:
  2. Hvis grafen er en torngraf [ 12 ] af en graf , der har noder, så er nærhedsgraden [ 13] : 

Naturlig generalisering af definitionen [14] :

hvor hører til intervallet (0,1). Når den øges fra 0 til 1, ændres den generaliserede grad af nærhed fra en lokal karakteristik (grad af et vertex) til en global (antal forbundne noder).

Informationscentraliteten af ​​Stephenson og Zelen (1989) er et andet nærhedsmål, der beregner den harmoniske middelværdi af modstandsafstandene i retning af et toppunkt x , som er mindre, hvis x har mange lavmodstandsveje, der forbinder det med andre toppunkter [15] .

I den klassiske definition af nærhed modelleres informationsudbredelse ved hjælp af korteste veje. Denne model er muligvis ikke helt realistisk for nogle typer kommunikationsscenarier. Beslægtede definitioner af nærhedsmålinger er blevet diskuteret, såsom graden af ​​nærhed langs tilfældige stier foreslået af Hoh og Rieger (2004). Denne metrik måler den hastighed, hvormed tilfældige beskedstier når toppen fra et hvilket som helst sted i grafen, en variant af nærhed baseret på tilfældige ture [16] . Hierarkisk centralitet Tran og Kwon (2014) [17] er et udvidet nærhedsmål baseret på en anden tilgang til at omgå nærhedsgradsbegrænsninger for grafer, der ikke er stærkt forbundne. Hierarkisk centralitet inkluderer eksplicit information om det sæt af andre noder, som en given node kan påvirke.

Se også

Noter

  1. ↑ Bavelas, 1950 , s. 725-730.
  2. ↑ Sabidussi, 1966 , s. 581-603.
  3. ↑ Marchiori, Latora, 2000 , s. 539-546.
  4. ↑ Dekker, 2005 .
  5. ↑ Rochat, 2009 .
  6. ↑ Garg, 2009 .
  7. ↑ Opsahl, 2010 .
  8. ↑ Boldi, Vigna, 2014 , s. 222-262.
  9. ↑ Harris, 1954 , s. 315-348.
  10. ↑ Gutberlet, 2014 .
  11. ↑ Dangalchev, 2006 , s. 556.
  12. ↑ En torngraf af en graf G  er en graf opnået ved at tilføje til hver knude på grafen G et vist antal yderligere hængende knudepunkter, det vil sige knudepunkter, der kun er knyttet til denne knude ( Azari 2018 ).
  13. ↑ Dangalchev, 2018 , s. 1-15.
  14. ↑ Dangalchev, 2011 , s. 1939-1948
  15. ↑ Stephenson og Zelen 1989 , s. 1-37.
  16. ↑ Noh, Rieger, 2004 , s. 118701.
  17. ↑ Tran, Kwon, 2014 .

Litteratur