Läheisyysaste (graafiteoria)

Solmun (muiden solmujen) läheisyysaste on verkon keskeisyyden mitta , joka lasketaan solmun ja kaavion kaikkien muiden solmujen välisten lyhimpien reittien pituuksien summan käänteislukuna. Siten mitä keskeisempi solmu on, sitä lähempänä se on kaikkia muita solmuja.

Määritelmä

Alex Bavelas määritteli läheisyysasteen vuonna 1950 etäisyyden käänteisarvoksi [1] [2] , ts.

C(x)={\frac {1}{\sum _{y}d(y,x))).

jossa on yhtä suuri kuin pisteiden välinen etäisyys ja . Läheisyysasteesta puhuttaessa ne tarkoittavat yleensä sen normalisoitua muotoa, joka on keskimääräinen lyhin polku niiden summan sijaan. Se annetaan yleensä edellisellä kaavalla kerrottuna , jossa on yhtä suuri kuin graafin solmujen lukumäärä. Suurissa kaavioissa tämä ero tulee merkityksettömäksi, joten se jätetään pois: ${\näyttötyyli d(y,x)}$ $x$ $y$ $N-1$ $N$ $-yksi$

C(x)={\frac {N}{\sum _{y}d(y,x))).

Tämä muutos mahdollistaa erikokoisten kaavioiden solmujen vertailun.

Etäisyyksien huomioon ottaminen muista solmuista on merkityksetöntä ohjaamattomille kaavioille, kun taas se voi antaa melko erilaisia tuloksia suunnatuille kaavioille (esim. verkkosivustolla voi olla suuri läheisyys lähteville yhteyksille, mutta pieni läheisyys saapuville yhteyksille).

Irrotetuissa kaavioissa

Jos kuvaaja ei ole vahvasti kytketty , on yleinen ajatus käyttää etäisyyksien käänteislukujen summaa etäisyyksien summan käänteissumman sijaan, sillä sopimuksella : $1/\infty =0$

H(x)=\sum _{y\neq x}{\frac {1}{d(y,x))).

Luonnollisin muunnos Bavelasin läheisyyden määritelmästä on seuraava Marchionin ja Latoran (2000) [3] ehdottama yleinen periaate : graafisissa, joissa on rajoittamaton etäisyys, harmoninen keskiarvo käyttäytyy paremmin kuin aritmeettinen keskiarvo. Lisäksi Bavelos-läheisyys voidaan kuvata aritmeettisten keskietäisyyksien normalisoimattomana käänteislukuna, kun taas harmoninen keskeisyys on yhtä suuri kuin harmonisten keskietäisyyksien normalisoimaton käänteisluku.

Tämän ajatuksen esittivät nimenomaan suunnatut graafit Dekker, jota kutsutaan arvostetuksi keskeisyydeksi [ 4 ] ja Rochat kutsui harmoniseksi keskeisyydeksi (2009) [5] . Garg aksiomatisoi konseptin (2009) [6] , kun taas Opsal ehdotti sitä uudelleen (2010) [7] . Baldy ja Vigna (2014) tutkivat käsitettä yleisillä suunnatuilla graafilla [8] . Tämä ajatus on hyvin samanlainen kuin Harrisin (1954) [9] ehdottama markkinointipotentiaali , jota nykyään usein kutsutaan markkinoille pääsyksi [10] .

Vaihtoehdot

Dangalchev (2006) [11] ehdotti toista määritelmää ohjaamattomille graafille työssään verkon haavoittuvuudesta:

D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)))}.

Tämä määritelmä on tehokas yhdistämättömille kaavioille ja antaa meille mahdollisuuden käyttää kätevää toimintojen muotoilua kaavioille. Esimerkiksi:

Jos graafi luodaan yhdistämällä graafin solmu graafin solmuun , yhdistetyn graafin läheisyysaste on: $G_{1}+G_{2}$ $s$ $G_{1}$ $q$ $G_{2}$ $D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q)).$
Jos graafi on solmuja sisältävän graafin piikkigraafi [ 12] , niin läheisyysaste on [13] : $T(G)$ $G$ $n$ $T(G)$ $D(T(G))={\frac {9}{4}}D(G)+n.$

Määritelmän luonnollinen yleistys [14] :

D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x))),

jossa kuuluu väliin (0,1). Nollasta 1:een kasvattaessa yleinen läheisyysaste muuttuu paikallisesta ominaisuudesta (pisteen aste) globaaliksi (kytkettyjen solmujen lukumäärä). $\alpha$ $\alpha$

Stephensonin ja Zelenin (1989) informaatiokeskeisyys on toinen läheisyysmitta, joka laskee resistanssietäisyyksien harmonisen keskiarvon kärjen x suunnassa , joka on pienempi, jos x :llä on monia matalaresistanssisia polkuja, jotka yhdistävät sen muihin pisteisiin [15] .

Klassisessa läheisyyden määritelmässä informaation etenemistä mallinnetaan lyhimpiä polkuja käyttäen. Tämä malli ei ehkä ole täysin realistinen tietyntyyppisissä viestintäskenaarioissa. Läheisyysmittauksiin liittyvistä määritelmistä on keskusteltu, kuten Hohin ja Riegerin (2004) ehdottama läheisyysaste satunnaisia polkuja pitkin Tämä mittari mittaa nopeutta, jolla satunnaiset viestipolut saavuttavat huipulle mistä tahansa kaaviosta, mikä on satunnaisiin kävelyihin perustuva läheisyysmuunnelma [16] . Hierarchical centrality Tran ja Kwon (2014) [17] on laajennettu läheisyysmitta, joka perustuu erilaiseen lähestymistapaan läheisyysasteen rajoitusten kiertämiseen graafisille, jotka eivät ole vahvasti yhteydessä toisiinsa. Hierarkkinen keskeisyys sisältää eksplisiittisesti tietoa muiden solmujen joukosta, joihin tietty solmu voi vaikuttaa.

Katso myös

Keskeisyys
Suhinan aste satunnaisilla reiteillä
sovitteluaste

Muistiinpanot

↑ Bavelas, 1950 , s. 725–730.
↑ Sabidussi, 1966 , s. 581–603.
↑ Marchiori, Latora, 2000 , s. 539–546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Garg, 2009 .
↑ Opsahl, 2010 .
↑ Boldi, Vigna, 2014 , s. 222–262.
↑ Harris, 1954 , s. 315–348.
↑ Gutberlet, 2014 .
↑ Dangalchev, 2006 , s. 556.
↑ Graafin G piikkigraafi on graafi, joka saadaan lisäämällä graafin G jokaiseen solmuun tietty määrä ylimääräisiä riippuvia pisteitä, eli vain tähän solmuun liittyviä kärkipisteitä ( Azari 2018 ).
↑ Dangalchev, 2018 , s. 1–15.
↑ Dangalchev, 2011 , s. 1939-1948
↑ Stephenson ja Zelen 1989 , s. 1–37.
↑ Noh, Rieger, 2004 , s. 118701.
↑ Tran, Kwon, 2014 .

Kirjallisuus

Mahdieh Azari. ON THE GUTMAN INDEX OF THORN GRAPHS // Kragujevac J. Sci .. - 2018. - T. 40 . - S. 33-48 .
Chavdar Dangalchev. Jäljellä oleva läheisyys verkostoissa // Physica A. - 2006. - T. 365 .
Chavdar Dangalchev. Yleistettyjen piikkikaavioiden jäännösläheisyys // Fundamenta Informaticae. - 2018. - T. 162 , nro 1 .
Chavdar Dangalchev. Jäännösläheisyys ja yleinen läheisyys // IJFCS. - 2011. - T. 22 , no. 8 .
Massimo Marchiori, Vito Latora. Harmonia pienessä maailmassa // Physica A: Tilastollinen mekaniikka ja sen sovellukset. - 2000. - T. 285 , no. 3-4 . - doi : 10.1016/s0378-4371(00)00311-3 . - . - arXiv : cond-mat/0008357 .
Anthony Decker. Käsitteellinen etäisyys sosiaalisen verkoston analyysissä // Journal of Social Structure. - 2005. - T. 6 , no. 3 .
Yannick Rochat. Läheisyyskeskeisyys laajennettu liittämättömiin kaavioihin: Harmoninen keskeisyysindeksi // Applications of Social Network Analysis, ASNA 2009 . – 2009.
Manuj Garg. Keskustelun aksiomaattiset perusteet verkostoissa. - 2009. - doi : 10.2139/ssrn.1372441 .
Tore Opsahl. Läheisyyskeskeisyys verkoissa, joissa komponentit eivät ole kytkettynä . - 2010 - maaliskuu.
Paolo Boldi, Sebastiano Vigna. Keskeisyyden aksioomit // Internet Mathematics. - 2014. - T. 10 , nro 3-4 . doi : 10.1080 / 15427951.2013.865686 .
Harris CD Markkinat teollisuuden lokalisointitekijänä Yhdysvalloissa // Annals of the Association of American geographers. - 1954. - T. 44 , no. 4 .
Theresa Gutberlet. Halpa hiili vs. markkinoille pääsy: luonnonvarojen ja kysynnän rooli Saksan teollistumisessa // Working Paper. – 2014.
Alex Bavelas. Viestintämallit tehtäväkeskeisissä ryhmissä // J. Acoust. soc. Olen. - 1950. - T. 22 , no. 6 .
Sabidussi G. Graafin keskeisyysindeksi // Psychometrica. - 1966. - T. 31 , no. 4 . - doi : 10.1007/bf02289527 . — PMID 5232444 .
Stephenson KA, Zelen M. Rethinking centrality: Methods and esimerkit // Social Networks. - 1989. - T. 11 . - doi : 10.1016/0378-8733(89)90016-6 .
Noh JD, Rieger H. Random Walks on Complex Networks // Phys. Rev. Lett .. - 2004. - T. 92 , no. 11 . - doi : 10.1103/physrevlett.92.118701 . - . - arXiv : cond-mat/0307719 . — PMID 15089179 .
Tien-Dzung Tran, Yung-Keun Kwon. Hierarkkinen läheisyys ennustaa tehokkaasti sairauden geenejä ohjatussa signalointiverkossa // Laskennallinen biologia ja kemia. - 2014. - syyskuu ( osa 53PB ). — ISSN 1476-928X .