Stupeň blízkosti (teorie grafů)

Stupeň blízkosti uzlu (k ostatním uzlům) je mírou centrality v síti, počítá se jako převrácená hodnota součtu délek nejkratších cest mezi uzlem a všemi ostatními uzly v grafu. Čím je tedy uzel centrálnější , tím je blíže všem ostatním uzlům.

Definice

Míru blízkosti definoval Alex Bavelas v roce 1950 jako převrácenou hodnotu vzdálenosti [1] [2] , tzn.

kde se rovná vzdálenosti mezi vrcholy a . Když mluvíme o míře blízkosti, míní obvykle její normalizovanou formu, což jsou průměrné nejkratší cesty místo jejich součtu. Obvykle je dán předchozím vzorcem vynásobeným , kde se rovná počtu uzlů grafu. U velkých grafů se tento rozdíl stává nevýznamným, proto je vynechán:

Tento pozměňovací návrh umožňuje srovnání mezi uzly grafů různých velikostí.

Zvažování vzdáleností od nebo k jiným uzlům nemá význam pro neorientované grafy, zatímco pro orientované grafy může poskytnout zcela odlišné výsledky (např. webová stránka může mít vysokou blízkost pro odchozí spojení, ale nízkou blízkost pro příchozí spojení) .

V nespojených grafech

Pokud graf není silně propojen , je běžnou myšlenkou použít součet převrácených hodnot vzdáleností místo převrácené hodnoty součtu vzdáleností, podle konvence, že :

Nejpřirozenější modifikací Bavelasovy definice blízkosti je následující obecný princip navržený Marchionim a Latorou (2000) [3] : v grafech s neomezenými vzdálenostmi se harmonický průměr chová lépe než aritmetický průměr. Bavelosovu blízkost lze navíc popsat jako nenormalizovanou převrácenou hodnotu aritmetických středních vzdáleností, zatímco harmonická centralita se rovná nenormalizované převrácené hodnotě středních harmonických vzdáleností.

Tuto myšlenku výslovně vyslovili pro orientované grafy Dekker nazvaný hodnotná centralita [ 4] a Rochat nazvaný harmonická centralita (2009) [5] . Garg koncept axiomatizoval (2009) [6] , zatímco Opsal jej navrhl znovu (2010) [7] . Tento koncept byl studován na obecně orientovaných grafech od Baldyho a Vigna (2014) [8] . Tato myšlenka je velmi podobná marketingovému potenciálu navrženému Harrisem (1954) [9] , který je nyní často označován jako přístup na trh [10] .  

Možnosti

Dangalchev (2006) [11] ve své práci o zranitelnosti sítě navrhl další definici pro neorientované grafy:

Tato definice je účinná pro nesouvislé grafy a umožňuje nám používat pohodlnou formulaci operací s grafy. Například:

  1. Pokud je graf vytvořen připojením uzlu grafu k uzlu grafu , pak stupeň blízkosti kombinovaného grafu je:
  2. Pokud je graf trnovým grafem [ 12] grafu , který má uzly, pak je stupeň blízkosti [ 13] : 

Přirozené zobecnění definice [14] :

kde patří intervalu (0,1). Při zvýšení z 0 na 1 se zobecněný stupeň blízkosti změní z lokální charakteristiky (stupeň vrcholu) na globální (počet připojených uzlů).

Informační centrálnost Stephensona a Zelena (1989) je dalším měřítkem blízkosti, které počítá harmonický průměr odporových vzdáleností ve směru k vrcholu x , který je menší, pokud x má mnoho nízkoodporových cest, které jej spojují s jinými vrcholy [15]. .

V klasické definici blízkosti je šíření informace modelováno pomocí nejkratších cest. Tento model nemusí být pro některé typy komunikačních scénářů zcela realistický. Byly diskutovány související definice měření blízkosti, jako je stupeň blízkosti podél náhodných cest navržený Hohem a Riegerem (2004). Tato metrika měří rychlost, s jakou cesty náhodných zpráv dosahují vrcholu odkudkoli v grafu, což je varianta blízkosti založená na náhodných procházkách [16] . Hierarchická centralita Trana a Kwona (2014) [17] je rozšířená míra podobnosti založená na odlišném přístupu k obcházení omezení stupně podobnosti pro grafy, které nejsou silně propojeny. Hierarchická centralita explicitně zahrnuje informace o sadě dalších uzlů, které může daný uzel ovlivnit.

Viz také

Poznámky

  1. ↑ Bavelas, 1950 , s. 725–730.
  2. ↑ Sabidussi, 1966 , s. 581–603.
  3. ↑ Marchiori, Latora, 2000 , str. 539–546.
  4. ↑ Dekker, 2005 .
  5. ↑ Rochat, 2009 .
  6. ↑ Garg, 2009 .
  7. ↑ Opsahl, 2010 .
  8. ↑ Boldi, Vigna, 2014 , str. 222–262.
  9. ↑ Harris, 1954 , str. 315–348.
  10. ↑ Gutberlet, 2014 .
  11. ↑ Dangalchev, 2006 , s. 556.
  12. ↑ Trnový graf grafu G  je graf získaný přidáním určitého počtu dalších zavěšených vrcholů ke každému uzlu grafu G , tedy vrcholů spojených pouze s tímto uzlem ( Azari 2018 ).
  13. ↑ Dangalchev, 2018 , str. 1–15.
  14. ↑ Dangalchev, 2011 , s. 1939–1948
  15. ↑ Stephenson a Zelen 1989 , str. 1–37.
  16. ↑ No, Rieger, 2004 , str. 118701.
  17. ↑ Tran, Kwon, 2014 .

Literatura