Centrálnost

Indikátor centrality nebo blízkosti středu v teorii grafů a síťové analýze určuje nejdůležitější vrcholy grafu. Aplikace indikátoru se používají k identifikaci nejvlivnějších osob v sociální síti , klíčových infrastrukturních uzlů na internetu nebo metropolitních sítích a nositelů nemoci. K měření sociologických primárních zdrojů se používají koncepty centrality původně vyvinuté v analýze sociálních sítí a mnoho pojmů centrality [2] . Tyto metriky by se neměly zaměňovat s metrikami vlivu uzlů , které hledají kvantitativní charakteristiky vlivu každého uzlu v síti.

Definice a popis indexů centrality

Indexy centrality jsou odpovědí na otázku "Co charakterizuje důležitost vrcholu?" Odpověď je dána z hlediska funkce s reálnou hodnotou na vrcholech grafu, jejíž hodnoty (očekávaně) poskytují pořadí, které určuje nejdůležitější uzly [3] [4] [5] .

Slovo „důležitost“ má širokou škálu významů, což vede k mnoha různým definicím centrality. Byla navržena dvě kategorizační schémata. „Důležitost“ lze chápat ve vztahu k typu toku sítí. To umožňuje klasifikaci centrality podle typu toku, který je považován za důležitý [4] . „Důležitost“ lze alternativně chápat jako účast na integritě sítě. To umožňuje klasifikovat centrality na základě toho, jak měří účast [6] . Oba tyto přístupy rozdělují centrality do různých kategorií. Centralita, která je vhodná pro jednu kategorii, bude často nevhodná při aplikaci na jinou kategorii [4] .

Pokud jsou centrality kategorizovány podle jejich účasti, je jasné, že většina centralit patří do stejné kategorie. Počet cest pocházejících z daného uzlu se liší pouze tím, jak jsou cesty určovány a počítány. Omezení dohod pro tuto skupinu umožňuje popis centralit na spektru tras od délky jedna ( stupeň konektivity ) po neomezené trasy ( stupeň ovlivnění ) [3] [7] . Pozorování, že mnoho centrál sdílí tyto vazby, vysvětluje vysokou úroveň korelace mezi těmito indexy.

Popis toků v síti

Síť si lze představit jako popis cest, po kterých něco proudí. To umožňuje popis na základě typů toků a typů cest kódovaných centralitou. Tok může být založen na převodech, kdy každý nedělitelný prvek přechází z jednoho uzlu do druhého, podobně jako při doručování balíků z pošty k zákazníkovi domů. V druhém případě dochází k reprodukci prvku, který přechází do dalšího uzlu, takže tento prvek má zdroj i cíl. Příkladem takového případu je šíření fám, kdy jsou informace sdíleny soukromě, přičemž zdroj i cíl jsou na konci procesu informovány. Posledním případem je paralelní šíření, kdy se prvek šíří více spoji současně, podobně jako rozhlasové vysílání, které poskytuje stejnou informaci mnoha posluchačům současně [4] .

Podobně lze druh cesty omezit na: Geodézie (nejkratší cesty), cesty (žádný vrchol není navštíven více než jednou), cesty (vrcholy lze navštívit vícekrát, ale žádná hrana není překročena dvakrát) nebo trasy (vrcholy i hrany může nastat několikrát) [4] .

Popis podle struktury chůze

Alternativní klasifikaci lze odvodit ze způsobu, jakým je konstruována centralita. To opět vede k rozdělení na dvě třídy – Radial nebo Medián. Radiální středy počítají počet cest, které začínají/končí v daném vrcholu. Stupně konektivity a stupně vlivu jsou příklady radiálních mír středovosti, které počítají počet cest délky jedna nebo neomezené délky. Středové středy počítají cesty, které procházejí daným vrcholem. Kanonickým příkladem je míra Freemanova zprostředkování, počet nejkratších cest, které procházejí daným vrcholem [6] .

Podobně může počet zachytit buď objem , nebo délku trasy. Objem je celkový počet tras daného typu. Do této kategorie spadají tři příklady z předchozího odstavce. Délka je vzdálenost od daného vrcholu k ostatním vrcholům v grafu. Míra blízkosti k dalším Freemanovým uzlům, celková geodetická vzdálenost od daného vrcholu ke všem ostatním vrcholům, je nejznámější příklad [6] . Všimněte si, že tato klasifikace závisí na typu kalkulovaných tras (tj. trasy, okruhy, stezky, geodetika).

Borgatti a Everett se domnívali, že tato typologie poskytuje představu o tom, jak porovnávat míry centrality. Centrality spadající do stejné buňky v této klasifikaci 2x2 jsou dostatečně podobné, aby byly přijatelnými alternativami, a lze rozumně porovnat, které skóre je pro daný problém nejlepší. Míry z různých buněk jsou však zcela odlišné. Jakékoli určení relativní vhodnosti může nastat pouze v předem určeném kontextu, která kategorie je vhodnější [6] .

Radiální objemové centrality, které existují ve spektru

Popis struktury trasy ukazuje, že téměř všechny použité středisky jsou radiálně-objemové míry. To dává jistotu, že centralita vrcholu je funkcí centrality vrcholů, se kterými je spojena. Centrality se liší způsobem, jakým jsou spojeny.

Bonacic ukázal, že pokud je asociace definována z hlediska cest, pak rodina centralit může být definována z hlediska délek uvažovaných cest [3] . Stupeň konektivity počítá počet tras délky jedna, stupeň ovlivnění počítá trasy neomezené délky. Alternativní definice asociací jsou také možné. Alfa-centralita vám umožňuje mít vnější zdroje vlivu na vrcholy. Estrada's subgraph centrality počítá pouze uzavřené cesty (trojúhelníky, čtyřúhelníky, ...).

Srdcem takových měření je pozorování, že stupně matice sousednosti grafu dávají počet cest s délkou rovnou stupni. Podobně exponent matice úzce souvisí s počtem cest dané délky. Počáteční transformace matice sousednosti umožňuje definovat počet různých typů tras. V obou přístupech může být centralita vrcholu vyjádřena jako nekonečný součet, nebo

{\displaystyle \sum _{k=0}^{\infty }A_{R}^{k}\beta ^{k))

pro maticové pravomoci, popř

\sum _{k=0}^{\infty }{\frac {(A_{R}\beta )^{k}}{k!)}}

pro maticový exponent, kde

$k$ rovna délce trasy,
$A_{R}$ je transformovaná matice sousedství a
$\beta$ je kompenzační parametr, který zajišťuje konvergenci součtu.

Rodina Bonacicových mír netransformuje matici sousedství. Alfa centralita nahrazuje matici sousednosti svým rozlišením . Centralita podgrafu nahrazuje matici sousednosti její stopou. Bez ohledu na počáteční transformaci matice sousednosti mají všechny tyto přístupy společné omezující chování. Jak má tendenci k nule, index konverguje ke stupni konektivity . Při snaze o maximální hodnotu index konverguje k míře ovlivnění [7] . $\beta$ $\beta$

Herně-teoretická centrálnost

Společným znakem většiny výše uvedených standardních opatření je, že hodnotí důležitost uzlu a zaměřují se pouze na roli, kterou uzel hraje sám o sobě. V mnoha aplikacích však tento přístup nebude adekvátní, protože interakce uzlů může být detekována, pokud jsou opatření aplikována na skupinové uzly.

Vezměme si například problém zastavení epidemie. Při pohledu na výše uvedený obrázek sítě, které uzly by měly být očkovány? Na základě výše popsaných opatření chceme rozpoznat uzliny, které jsou při šíření nemoci nejdůležitější. Používat přístupy založené pouze na centralitě, které se zaměřují na jednotlivé vlastnosti uzlů, nemusí být dobrý nápad. Uzliny v červeném rámečku samy o sobě nemohou zastavit šíření nemoci, ale při pohledu jako skupina jasně vidíme, že mohou zastavit nemoc, pokud začne v uzlinách , , . Herně-teoretické centrály se snaží zohlednit popsané problémy a příležitosti pomocí nástrojů teorie her. Přístup navržený Michalakem (et al.) [8] využívá Shapleyho vektor . Vzhledem ke složitosti (času) výpočtu Shapleyho vektoru je většina úsilí v této oblasti investována do vývoje nových algoritmů a metod, které spoléhají na specifickou topologii sítě a zvláštní povahu problému. Tento přístup může snížit časovou složitost algoritmu z exponenciálního na polynomiální. $v_{1}$ ${\displaystyle v_{4))$ $v_{5}$

Důležitá omezení

Indexy centrality mají dvě důležitá omezení, jedno je zřejmé a druhé jemné. Zjevným omezením je, že centralita, která je optimální pro jednu aplikaci, často není optimální pro jinou. Navíc, kdyby tomu tak nebylo, nebylo by potřeba tolik různých centrál. Ilustraci tohoto jevu poskytuje Crackhardův drak , pro kterého tři různé pojmy centrality dávají tři různé nejcentrálnější vrcholy [9] .

Drobným omezením je, že existuje všudypřítomná mylná představa, že centralita vertexu odráží relativní důležitost vertexů. Indexy centrality byly vyvinuty výslovně pro klasifikaci, což umožňuje výběr nejdůležitějších vrcholů [3] [4] . Dělají to dobře se zmíněnými omezeními. Nebyly navrženy k obecnému měření uzlů. Nedávno začali síťoví fyzici vyvíjet metriky vlivu uzlů , aby tento problém vyřešili.

Chyba je dvojí. Za prvé, řazení pouze v pořadí vrcholů, protože jejich důležitost neodráží rozdíl v důležitosti mezi různými úrovněmi hodnocení. Tato skutečnost může být zmírněna aplikací Freemanovy centrality na dotyčnou míru centrality, což dává určitý pohled na důležitost uzlů podle jejich různých skóre centrality. Freemanova centralita navíc umožňuje porovnávat některé sítě z hlediska ukazatelů z uzlů s nejvyšší hodnotou [10] .

Za druhé, vlastnosti, které (správně) odrážejí nejdůležitější vrcholy v dané síti/aplikaci, nemusí nutně zobecňovat na zbytek vrcholů. Pro většinu ostatních uzlů v síti může být hodnocení bezvýznamné [11] [12] [13] [14] . To například vysvětluje, proč se pouze prvních několik výsledků vyhledávání obrázků Google zobrazí v adekvátním pořadí. PageRank je vysoce nestabilní měřítko, které často ukazuje opačnou pozici po malé změně parametru vyhledávání [15] .

I když se nemožnost zobecnění indexu centrality na zbytek sítě nemusí na první pohled zdát samozřejmá, vyplývá přímo z výše uvedených definic. Složité sítě mají heterogenní topologii. Do jaké míry závisí optimální míra na struktuře sítě nejdůležitějších vrcholů, do jaké míry optimální míra pro takové vrcholy není optimální pro zbytek sítě [11] .

Konektivita

Historicky prvním a koncepčně nejjednodušším konceptem je míra konektivity , která je definována jako počet spojů spadajících do uzlu (tj. počet spojů, které uzel má). Stupeň lze interpretovat jako přímé riziko uzlu, že zachytí něco, co prochází sítí (například virus nebo nějaké informace). V případě směrované sítě (kde jsou směrovány odkazy) obvykle definujeme dvě různé míry míry konektivity, a to in -degree a out -degree . V souladu s tím je in-stupeň počet spojení s uzlem a out-degree je počet spojení uzlu s jinými uzly. Když je spojení spojeno s nějakým pozitivním aspektem, jako je přátelství nebo spolupráce, in-degree je často interpretován jako druh popularity a out-degree jako sociabilita.

Stupeň propojenosti vrcholu pro daný graf s vrcholy a hranami je definován jako $proti$ $G:=(V,E)$ $|V|$ $|E|$

C_{D}(v)=\deg(v)

Výpočet stupně konektivity pro všechny uzly v grafu vyžaduje čas v husté reprezentaci grafu matice sousedství a čas v reprezentaci řídké matice pro hrany . $\Theta (V^{2})$ $\Theta (E)$

Definici centrality na úrovni uzlů lze rozšířit na celý graf a v tomto případě hovoříme o centralitě grafu [10] . Nechť je uzel s nejvyšším stupněm konektivity v . Nechť je spojený graf s uzly, který maximalizuje následující hodnotu (s jako uzel s nejvyšším stupněm konektivity v ): $v*$ $G$ $X:=(Y,Z)$ $|Y|$ $y*$ $X$

H=\sum _{j=1}^{|Y|}[C_{D}(y*)-C_{D}(y_{j})]

Stupeň centrality grafu se tedy rovná: $G$

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})] }{H}}

Hodnota je maximální, když graf obsahuje jeden centrální uzel, ke kterému jsou připojeny všechny ostatní uzly ( hvězdový graf ), v tom případě $H$ $X$

H=(n-1)\cdot ((n-1)-1)=n^{2}-3n+2.

Tedy pro jakýkoli graf $G:=(V,E),$

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})] }{|V|^{2}-3|V|+2}}

Blízkost k jiným uzlům

V souvislém grafu se normalizovaný stupeň blízkosti uzlu rovná průměrné délce nejkratší cesty mezi uzlem a všemi ostatními uzly v grafu. Čím je uzel centrálnější, tím je blíže všem ostatním uzlům.

Míru blízkosti definoval Alex Bavelas (1950) jako převrácenou hodnotu vzdálenosti [16] [17] , tzn.

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

kde se rovná vzdálenosti mezi vrcholy a . Když však mluvíme o míře blízkosti k jiným uzlům, lidé mají obvykle na mysli její normalizovanou formu, obvykle získanou z předchozího vzorce vynásobením pomocí , kde se rovná počtu uzlů v grafu. Velikost umožňuje srovnání mezi uzly grafů různých velikostí. $d(y,x)$ $X$ $y$ $N-1$ $N$

Zohlednění vzdálenosti od všech ostatních uzlů nebo ke všem ostatním uzlům není použitelné pro neorientované grafy, zatímco v orientovaných grafech dávají zcela odlišné výsledky. Webová stránka může mít například vysokou odchozí vzdálenost, ale nízkou příchozí vzdálenost).

Harmonická centralita

V (ne nutně spojeném) grafu harmonická centralita obrací operace součtu a inverze při určování stupně podobnosti:

H(x)=\součet _{y\neq x}{\frac {1}{d(y,x)))

kde , pokud neexistuje žádná cesta z do . Harmonickou centralitu lze normalizovat dělením , kde se rovná počtu uzlů v grafu. $1/d(y,x)=0$ $y$ $X$ $N-1$ $N$

Harmonickou centralitu navrhli Marchiori a Lathora (2000) [18] , samostatně pak Dekker (2005) pod názvem oceňovaná centralita [19] a Rochat (2009) [ 20] .

Stupeň zprostředkování

Stupeň zprostředkování je mírou centrálnosti vrcholu v grafu (existuje také okrajový stupeň zprostředkování , který zde není diskutován). Stupeň zprostředkování kvantifikuje, kolikrát uzel překlene nejkratší cestu mezi dvěma dalšími uzly. Stupeň zprostředkování zavedl Linton Freeman jako míru kvantitativního vyjádření interakce člověka s ostatními lidmi v sociální síti [21] . V tomto pojetí mají vrcholy, které mají nejvyšší pravděpodobnost, že budou na náhodně zvolené nejkratší cestě mezi dvěma náhodně vybranými vrcholy, vysoký stupeň zprostředkování.

Stupeň zprostředkování vrcholu v grafu s vrcholy se vypočítá takto: $proti$ $G:=(V,E)$ $PROTI$

Pro každou dvojici vrcholů ( s , t ) se vypočítají nejkratší cesty mezi nimi .
Pro každou dvojici vrcholů ( s , t ) určete zlomek nejkratších cest, které procházejí daným vrcholem (zde vrchol v ).
Tyto podíly shrneme přes všechny dvojice vrcholů ( s , t ).

Kompaktněji lze míru zprostředkování vyjádřit jako [22] :

{\displaystyle C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st))))

kde se rovná celkovému počtu nejkratších cest od uzlu k uzlu a rovná se počtu takových cest, které procházejí . Stupeň zprostředkování lze normalizovat vydělením počtem párů vrcholů nezahrnujících v , který je roven pro orientované grafy a rovný pro neorientované grafy . Například v neorientované hvězdě má centrální vrchol (který je obsažen v jakékoli možné nejkratší cestě) stupeň zprostředkování (1, pokud je normalizován), zatímco listy (které nejsou obsaženy v žádné nejkratší cestě) mají stupeň zprostředkování 0. ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $proti$ $(n-1) (n-2)$ $(n-1) (n-2)/2$ $(n-1) (n-2)/2$

Z hlediska výpočtu zahrnuje stupeň zprostředkování i stupeň blízkosti všech vrcholů v grafu výpočet nejkratších cest mezi všemi páry vrcholů v grafu, což při použití Floyd-Warshallova algoritmu zabere čas . Na řídkých grafech však může být Johnsonův algoritmus efektivnější a běží v čase . V případě nevážených grafů lze výpočty provádět pomocí Brandesova algoritmu [22] , což vyžaduje čas . Tyto algoritmy obvykle předpokládají, že grafy jsou neorientované a spojené s rozlišením smyček a více hran. Při práci se síťovými grafy, které představují jednoduchá spojení, která často nemají smyčky nebo více hran (kde hrany představují spojení mezi lidmi). V tomto případě, s použitím Brandesova algoritmu, se konečný index centrality vydělí dvěma, aby se zohlednila každá nejkratší cesta, která se započítává dvakrát [22] . $O(V^{3})$ $O(V^{2}\log V+VE)$ $O(VE)$

Stupeň vlivu

Míra vlivu je mírou vlivu uzlu v síti . Všem uzlům v síti přiděluje relativní skóre na základě konceptu, že odkazy na uzly s vysokým skóre přispívají ke skóre příslušného uzlu více než stejné spojení s uzlem s nízkým skóre [23] [5] [5] . Google PageRank a Katzova centralita uzlů jsou variantami míry vlivu [24] .

Použití matice sousednosti k nalezení stupně vlivu

Pro daný graf s vrcholy nechť je matice sousednosti , tedy , pokud je vrchol připojen k vrcholu , a jinak. Relativní index centrality vrcholu lze definovat jako $G:=(V,E)$ $|V|$ $A=(a_{v,t})$ $a_{v,t}=1$ $proti$ $t$ $a_{v,t}=0$ $proti$

x_{v}={\frac {1}{\lambda }}\součet _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\součet _ {t\in G}a_{v,t}x_{t}

kde je množina sousedů vrcholu a je konstanta. Po menších transformacích lze tento výraz přepsat do vektorového zápisu jako rovnice pro vlastní vektor $M(v)$ $proti$ $\lambda$

\mathbf {Ax} ={\lambda }\mathbf {x}

Obecně existuje mnoho různých vlastních hodnot , pro které existuje nenulový vlastní vektor. Protože prvky matice sousednosti jsou nezáporné, existuje jediná největší vlastní hodnota, která je reálná a pozitivní, podle Frobenius-Perronovy věty . Tato největší vlastní hodnota dává požadovanou míru centrality [23] . Přidružená komponenta vlastního vektoru udává relativní centrálnost vrcholu v síti. Vlastní vektor je definován až na faktor, takže je zcela definován pouze vztah vrcholových centralit. Pro určení absolutní hodnoty exponentu je třeba normalizovat vlastní vektor např. tak, aby součet přes všechny vrcholy byl roven 1 nebo normalizovat celkovým počtem vrcholů n . Mocninná metoda je jedním z mnoha derivačních algoritmů vlastních hodnot, které lze použít k nalezení tohoto dominantního vlastního vektoru [24] . Navíc to lze zobecnit tak, že prvky matice A mohou být reálná čísla představující sílu vazby, jako ve stochastické matici . $\lambda$ $v^{th}$ $proti$

Centrálnost podle Katze

Centralita podle Kaca [25] je zobecněním míry souvislosti. Konektivita měří počet přímých sousedů a centralita Kac měří počet všech uzlů, které lze propojit cestami, a přitom penalizuje vzdálené uzly. Matematicky je tato centralita definována jako

x_{i}=\součet _{k=1}^{\infty }\součet _{j=1}^{N}\alpha ^{k}(A^{k})_{ji}

kde je násobitel útlumu z intervalu . $\alpha$ $(0,1)$

Podle Katze lze na centralitu pohlížet jako na variantu míry vlivu. Jinou formou centrality podle Kaca je

x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).

Ve srovnání se stupněm vlivu je nahrazena $x_{j}$ $x_{j}+1.$

Ukázalo se [26] , že hlavním vlastním vektorem (odpovídajícím největšímu vlastnímu číslu matice sousednosti ) je mez centrality Kac, když se k přibližuje zdola. $A$ $\alpha$ ${\tfrac {1}{\lambda ))$

PageRank

PageRank splňuje následující rovnost

x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)))+{\frac {1-\alpha }{N}} ,

kde

{\displaystyle L(j)=\sum _{i}a_{ji))

rovná se počtu sousedů uzlu (nebo počtu odchozích spojení orientovaného grafu). Ve srovnání s Katzovým stupněm vlivu a centrality je faktor škálování důležitým rozdílem . Rozdíl mezi PageRankem a mírou vlivu spočívá v tom, že vektor PageRank je levý vlastní vektor (tj. vlastní vektor transponované matice, všimněte si, že multiplikátor má opačné pořadí indexů) [27] . $j$ $L(j)$ ${\displaystyle a_{ji))$

Perkolační centralita

K určení „důležitosti“ jednoho uzlu ve složité síti existuje řada opatření centrality. Odrážejí však důležitost uzlu čistě z topologického hlediska a hodnota uzlu nijak nezávisí na „stavu“ uzlu. Hodnota zůstává konstantní bez ohledu na dynamiku sítě. To platí i pro měřená mediační opatření. Uzel však může být také umístěn centrálně, pokud jde o stupeň zprostředkování nebo jinou míru centrálnosti, ale nesmí být „centrálně umístěn“ v kontextu sítě, ve které dochází k úniku. K úniku „infekce“ dochází ve složitých sítích ve velkém množství scénářů. Virová nebo bakteriální infekce se může šířit prostřednictvím sociálních sítí lidí, známých jako kontaktní sítě. Na šíření nemocí lze také nahlížet na vysoké úrovni abstrakce, vezmeme-li v úvahu síť měst nebo populačních center propojených silnicemi, železnicemi nebo leteckými společnostmi. Počítačové viry se mohou šířit přes počítačové sítě. Pověsti nebo zprávy o obchodních nabídkách a akcích se mohou šířit také prostřednictvím sociálních sítí lidí. Ve všech těchto scénářích se „infekce“ šíří prostřednictvím spojení složité sítě a mění „stavy“ uzlů reverzibilně nebo nevratně. Například v epidemiologickém scénáři se jednotlivci přesunou z „vnímavého“ stavu do „infikovaného“ stavu. Stavy konkrétních uzlů, jak se „nákaza“ šíří, mohou nabývat binárních hodnot (jako je „přijatá/neobdržená zpráva“), diskrétních hodnot (náchylných/infikovaných/vyléčených) nebo dokonce spojitých hodnot (jako je podíl nakažených lidí ve městě). Společnou věcí ve všech těchto scénářích je, že šíření „infekce“ vede ke změně stavu síťových uzlů. S ohledem na tuto skutečnost byla navržena perkolační centralita (PC) , která měří důležitost uzlu z hlediska přispívání k perkolaci prostřednictvím sítě. Toto opatření navrhl Pairavinan et al [28] .

Centralita průsaku je definována pro daný uzel a v daném čase jako podíl "průsakových cest", které procházejí uzlem. "Cesta úniku" je nejkratší cesta mezi dvojicí uzlů, kde je zdrojový uzel ve stavu úniku (např. infikovaný). Cílový uzel může být ve stavu perkolace, stavu bez perkolace nebo ve stavu částečné perkolace.

PC^{t}(v)={\frac {1}{N-2}}\součet _{s\neq v\neq r}{\frac {\sigma _{sr}(v)} {\sigma _{sr))}{\frac {{x^{t}}_{s}}({\sum {[{x^{t}}_{i}}]}-{x^{ televize}}}

kde je celkový počet nejkratších cest od uzlu k uzlu a je počet takových cest procházejících . Stav netěsnosti uzlu v čase je označen jako a existují dva speciální případy, kdy, což označuje těsný stav v čase , a kdy , označuje plnou netěsnost v čase . Hodnoty mezi těmito hodnotami znamenají stavy částečného prosakování (například v síti měst to může být procento infikovaných lidí ve městě). ${\displaystyle \sigma _{sr))$ $s$ $r$ $\sigma _{sr}(v)$ $proti$ $i$ $t$ ${x^{t}}_{i}$ ${x^{t}}_{i}=0$ $t$ ${x^{t}}_{i}=1$ $t$

Váhy cesty úniku závisí na úrovních úniku přiřazených ke zdrojovým uzlům na základě předpokladu, že čím vyšší je úroveň úniku zdrojového uzlu, tím důležitější jsou cesty vycházející z tohoto uzlu. Uzly, které leží na nejkratších drahách začínajících na uzlech s vysokou perkolací, jsou proto pro perkolaci potenciálně důležitější. Definici PC lze také rozšířit tak, aby zahrnovala také váhy cílových uzlů. Výpočet centrality úniku se provádí v čase s efektivní implementací vypůjčenou z rychlého Brandesova algoritmu, a pokud výpočty vyžadují zohlednění vah koncových uzlů, čas nejhoršího případu je . $O(NM)$ $O(N^{3})$

Centralita křížového kliknutí

Centralita křížové kliky jednotlivého uzlu v komplexním grafu určuje spojení uzlu s různými klikami . Uzel s vysokou centralitou křížového kliknutí podporuje šíření informací nebo nemocí v grafu. Kliky jsou podgrafy, ve kterých je každý uzel spojen se všemi ostatními klikovými uzly. Centralita křížového kliknutí uzlu pro daný graf s vrcholy a hranami je označena jako a rovna počtu kliků, ke kterým vrchol patří. Toto opatření bylo použito ve Faganiho práci [29] , ale poprvé jej navrhli Everett a Borgatti v roce 1998 pod názvem „clique overlap centrality“. $proti$ $G:=(V,E)$ $|V|$ $|E|$ $X(v)$ $proti$

Freeman centralita

Centrálnost jakékoli sítě je měřítkem toho, jak centrální je její nejcentrálnější uzel ve srovnání s ostatními uzly [10] . Míra centrality se pak (a) vypočítá jako součet rozdílů centrality mezi nejcentrálnějším uzlem v síti a všemi ostatními uzly a (b) vydělením této hodnoty teoreticky největším součtem rozdílů jakékoli sítě v síti. stejné velikosti [10] . Každá míra centrality pak může mít svou vlastní míru centrality. Formálně řečeno, jestliže je míra centrálnosti bodu , jestliže je největší taková míra v síti, a jestliže $C_{x}(p_{i})$ $i$ $C_{x}(p_{*})$

\max \sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})

je největší součet rozdílů v centralitě bodů pro libovolný graf se stejným počtem uzlů, potom je centralita sítě [10] $C_{x}$

C_{x}={\frac {\sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}{\max \ součet _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}}.

Diferenční míry centrality

Aby se dosáhlo lepších výsledků při hodnocení uzlů dané sítě, Alvarez-Socorro (et al.) [30] používá míru odlišnosti (charakteristickou pro teorii klasifikace a analýzu dat) ke zlepšení míry centrality ve složitých sítích. To je ilustrováno stupněm ovlivnění výpočtem centrálnosti každého uzlu řešením problému vlastních čísel

W\mathbf {c} =\lambda \mathbf {c}

kde (součin souřadnicový), a je libovolná matice nepodobnosti definovaná v podmínkách míry nepodobnosti. Například prostřednictvím Jaccardovy nepodobnosti dané vzorcem $W_{ij}=A_{ij}D_{ij}$ $D_{ij}$

D_{ij}=1-{\dfrac {|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{ +}(j)|}}

Toto měření nám umožňuje kvantifikovat topologický příspěvek (proto nazývaný centralita příspěvku) každého uzlu k centralitě daného uzlu, čímž získáme větší poměr váha/důležitost těch uzlů s větší odlišností, protože to umožňuje danému uzlu dosáhnout uzlů, které nelze dosáhnout přímo.

Všimněte si, že je nezáporné, protože a jsou nezáporné matice, takže můžeme použít Frobenius-Perronovu větu , abychom zajistili, že řešení výše uvedeného problému je jedinečné pro s nezáporným c , což nám umožňuje získat centrálnost každý uzel v síti. Centrálnost i-tého uzlu je tedy rovna $W$ $A$ $D$ ${\displaystyle \lambda =\lambda _{max))$

c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\ ,j=1,\cdots ,n

kde se rovná počtu síťových uzlů. Některé sítě a míry odlišnosti byly testovány Alvarezem-Socorrem (et al.) [31] a ve studovaných případech byly získány lepší výsledky. $n$

Zobecnění

Empirické a teoretické studie zobecňují koncept centrality v kontextu statických sítí na dynamické centrality [32] v kontextu časově závislých sítí a sítí s krátkou životností [33] [34] [35] .

Pro zobecnění na vážené sítě viz Opsal et al ., [36] .

Koncept centrality byl také zobecněn na skupinovou úroveň. Například míra zprostředkování skupiny ukazuje podíl geodetických vazeb dvojic (tedy cest minimální délky) uzlů nepatřících do skupiny, které procházejí skupinou [37] [38] .

Viz také

Poznámky

↑ Část terminologie je převzata z článku A. S. Semenova a M. V. Bartoshe "ODHAD STABILITY SÍTĚ INTERNET VĚCÍ POMOCÍ INDIKÁTORŮ CENTRALITY VZTAHŮ" . Termíny v literatuře v ruštině se neustálily. V článku Evina I. A. Komplexní sítě: Úvod do teorie se tedy místo termínu „stupeň zprostředkování“ používají termíny „zatížení uzlů“, „spojení s maximální důležitostí“. Na stránce Network Metrics je místo výrazu „stupeň konektivity“ použit doslovný překlad „centralita podle stupně“ namísto výrazů „stupeň…“ - „centralita podle…“. Někdy se místo termínu "centralita" používá termín "centralita".
↑ Newman, 2010 .
↑ 1 2 3 4 Bonacich, 1987 , str. 1170–1182.
↑ 1 2 3 4 5 6 Borgatti, 2005 , str. 55–71.
↑ 1 2 3 Negre, Morzan, Hendrickson a kol., 2018 , str. E12201-E12208.
↑ 1 2 3 4 Borgatti, Everett, 2006 , str. 466–484.
↑ 1 2 Benzi, Klymko, 2013 , str. 686–706.
↑ Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013 , s. 607-650.
↑ Krackhardt, 1990 , s. 342–369.
↑ 1 2 3 4 5 Freeman, 1979 , str. 215–239.
↑ 12 Právník , 2015 , str. 8665.
↑ da Silva, Viana, da F. Costa, 2012 , str. P07005.
↑ Bauer a Lizier, 2012 , s. 68007.
↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , str. 1–13.
↑ Ghoshal, Barabsi, 2011 , str. 394.
↑ Bavelas, 1950 , s. 725–730.
↑ Sabidussi, 1966 , s. 581–603.
↑ Marchiori, Latora, 2000 , str. 539–546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Freeman, 1977 , str. 35–41.
↑ 1 2 3 Brandes, 2001 , str. 163–177.
↑ 12 Newman , 2007 , str. 1-12.
↑ 12 Americká matematická společnost . (neurčitý)
↑ Katz, 1953 , str. 39–43.
↑ Bonacich, 1991 , str. 155–168.
↑ Jak Google hodnotí webové stránky? Archivováno z originálu 31. ledna 2012. 20Q: O Networked Life
↑ Piraveenan, Prokopenko, Hossain, 2013 , str. e53095.
↑ Faghani, 2013 , str. 1815–1826
↑ Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015 , str. 17095.
↑ Alvarez-Socorro AJ, Herrera-Almarza LA, González-Díaz. Doplňkové informace pro Eigencentralitu založené na měření odlišnosti odhalují centrální uzly ve složitých sítích . Nature Publishing Group. (neurčitý)
↑ Braha, Bar-Yam, 2006 , str. 59–63.
↑ Hill, Braha, 2010 , str. 046105.
↑ Gross, Sayama, 2009 .
↑ Holme, Saramaki, 2013 .
↑ Opsahl, Agneessens, Skvoretz, 2010 , str. 245–251.
↑ Everett, Borgatti, 2005 , str. 57–76.
↑ Puzis, Yagil, Elovici, Braha, 2009 .

Literatura

Newman MEJ Networks: Úvod. — Oxford, UK: Oxford University Press, 2010.
Newman MEJ Matematika sítí, // The New Palgrave Encyclopedia of Economics . — Basingstoke, Palgrave Macmillan, 2007.

Filip Bonacich. Moc a centrálnost: Rodina opatření // American Journal of Sociology. - 1987. - T. 92 , čís. 5 . - doi : 10.1086/228631 .
Bonacich P. Simultánní skupinové a individuální centrality // Sociální sítě. - 1991. - T. 13 , no. 2 . - doi : 10.1016/0378-8733(91)90018-o .
Stephen P. Borgatti. Centrality and Network Flow // Sociální sítě. - 2005. - T. 27 . - doi : 10.1016/j.socnet.2004.11.008 .
Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. Centrálnost vlastního vektoru pro charakterizaci proteinových alosterických drah // Proceedings of the National Academy of Sciences. - 2018. - T. 115 . - doi : 10.1073/pnas.1810452115 .
Stephen P. Borgatti, Martin G. Everett. Graf-teoretický pohled na centralitu // Sociální sítě. - 2006. - T. 28 , no. 4 . - doi : 10.1016/j.socnet.2005.11.005 .
Michele Benzi, Christine Klymko. Maticová analýza různých měření centrality // SIAM Journal on Matrix Analysis and Applications. - 2013. - T. 36 , č. 2 . - doi : 10.1137/130950550 . - arXiv : 1312.6722 .
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. Efektivní výpočet Shapleyho hodnoty pro herně teoretickou síťovou centralitu // Journal of Artificial Intelligence Research. - 2013. - T. 46 .
David Krackhardt. Hodnocení politického prostředí: struktura, poznání a moc v organizacích // čtvrtletník správní vědy. - 1990. - Červen ( díl 35 , číslo 2 ). - doi : 10.2307/2393394 . — .
Renato da Silva, Matheus Viana, Luciano da F. Costa. Predikce epidemie z jednotlivých znaků šiřitelů // J. Stat. Mech.: Teorie Exp.. - 2012. - T. 2012 . - doi : 10.1088/1742-5468/2012/07/p07005 . - . - arXiv : 1202.0024 .
Frank Bauer, Joseph Lizier. Identifikace postižených šiřitelů a efektivní odhad počtu infekcí v epidemických modelech: Přístup počítání chůze // Europhys Lett. - 2012. - T. 99 . - S. 68007 . - doi : 10.1209/0295-5075/99/68007 . - . - arXiv : 1203.0502 .
Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Centralita epidemie – existuje podceňovaný dopad epidemie síťových periferních uzlů? // The European Physical Journal B. - 2013. - T. 86 , č. 10 . - doi : 10.1140/epjb/e2013-31025-5 . - arXiv : 1110.2558 .
Ghoshal G., Barabsi AL Hodnocení stability a superstabilních uzlů ve složitých sítích. // NatCommun. - 2011. - T. 2 . - doi : 10.1038/ncomms1396 . — .
právník Glenn. Pochopení schopnosti šíření všech uzlů v síti: perspektiva v nepřetržitém čase // Sci Rep. - 2015. - T. 5 . - doi : 10.1038/srep08665 . - . - arXiv : 1405.6707 . — PMID 25727453 .
Linton C. Freeman. Centralita v sociálních sítích: Koncepční vyjasnění // Sociální sítě. - 1979. - svazek 1 , vydání. 3 . — S. 215–239 . - doi : 10.1016/0378-8733(78)90021-7 . Archivováno z originálu 22. února 2016.
Linton Freeman. Soubor měřítek centrality založených na mezilidství // Sociometrie. - 1977. - T. 40 , čís. 1 . — s. 35–41 . - doi : 10.2307/3033543 . — .
Alex Bavelas. Komunikační vzorce v úkolově orientovaných skupinách // J. Acoust. soc. Dopoledne. - 1950. - T. 22 , čís. 6 .
Sabidussi G. Sabidussi. Index centrality grafu // Psychometrie. - 1966. - T. 31 , čís. 4 . - doi : 10.1007/bf02289527 . — PMID 5232444 .
Massimo Marchiori, Vito Latora. Harmonie v malém světě // Physica A: Statistická mechanika a její aplikace. - 2000. - T. 285 , čís. 3–4 . - doi : 10.1016/s0378-4371(00)00311-3 . - . - arXiv : cond-mat/0008357 .
Anthony Decker. Koncepční vzdálenost v analýze sociálních sítí // Journal of Social Structure. - 2005. - T. 6 , no. 3 .
Yannick Rochat. Centralita blízkosti rozšířená na nespojené grafy: Harmonický index centrality // Applications of Social Network Analysis, ASNA 2009 . — 2009.
Ulrik Brandes. Rychlejší algoritmus pro centralitu mezilidských vztahů // Journal of Mathematical Sociology. - 2001. - T. 25 , no. 2 . - doi : 10.1080/0022250x.2001.9990249 .
Newman MEJ Matematika sítí .
Katz L. Nový stavový index odvozený ze sociometrického indexu // Psychometrics. - 1953. - S. 39-43 .
Piraveenan M., Prokopenko M., Hossain L. Perkolační centralita: kvantifikace grafově teoretického dopadu uzlů během perkolace v sítích // PLOS ONE. - 2013. - T. 8 , no. 1 . - doi : 10.1371/journal.pone.0053095 . - . — PMID 23349699 .
Mohamamd Reza Faghani. Studie mechanismů šíření a detekce červů XSS v online sociálních sítích // Transakce IEEE v oblasti informační forenzní analýzy a bezpečnosti. - 2013. - T. 8 , no. 11 . - doi : 10.1109/TIFS.2013.2280884 .
Alvarez-Socorro AJ, Herrera-Almarza GC, González-Díaz LA Eigencentralita založená na opatřeních odlišnosti odhaluje centrální uzly ve složitých sítích // Scientific Reports. - 2015. - Listopad ( 5. díl ). - doi : 10.1038/srep17095 . - . — PMID 26603652 .
Braha D., Bar-Yam Y. Od centrality k dočasné slávě: Dynamická centralita ve složitých sítích // Složitost. - 2006. - T. 12 , no. 2 . - doi : 10.1002/cplx.20156 . - . - arXiv : fyzika/0611295 .
Hill SA, Braha D. Dynamický model časově závislých komplexních sítí // Physical Review E. - 2010. - Vol. 82 , no. 4 . - doi : 10.1103/physreve.82.046105 . - . - arXiv : 0901.4407 . — PMID 21230343 .
Adaptivní sítě: teorie, modely a aplikace / Gross T., Sayama H.. - Springer, 2009.
Holme P., Saramaki J. Temporal Networks. — Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Centralita uzlů ve vážených sítích: Zobecňující stupeň a nejkratší cesty // Sociální sítě. - 2010. - T. 32 , no. 3 . - doi : 10.1016/j.socnet.2010.03.006 . Archivováno z originálu 26. února 2018.
Everett MG, Borgatti SP Rozšíření centrality. In PJ Carrington, J. Scott a S. Wasserman (Eds.) // Modely a metody v analýze sociálních sítí. - New York: Cambridge University Press, 2005. - S. 57-76.
Puzis R., Yagil D., Elovici Y., Braha D. Kolaborativní útok na anonymitu uživatelů internetu // Internet Research. - 2009. - T. 19 , no. 1 . Archivováno z originálu 7. prosince 2013.

Čtení pro další čtení

Koschützki, D.; Lehmann, K.A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. a Zlotowski, O. (2005) Centrality Indexes. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations , pp. 16-61, LNCS 3418, Springer-Verlag.