Centrálnost

V teorii grafů a teorii sítí jsou ústřednost indikátorů opatřeními, která mají zachytit pojem důležitosti v grafu a identifikovat nejvýznamnější vrcholy. Aplikace těchto indikátorů zahrnují identifikaci nejvlivnějších osob v sociální síti , klíčové uzly v infrastruktuře, jako je internet nebo městská síť, a dokonce i ohniska infekce, ať už nozokomiální povahy, nebo superinfektoři , pro určité nemoci. Konkrétnější příklady zahrnují kooperativní vztahy v profesionálních sítích, jako je vědecká práce prováděná společně nebo ve filmovém průmyslu herci, kteří hráli ve stejných filmech.

Pojmy a pojmy kolem centrality byly nejprve vyvinuty pro analýzu sociálních sítí a většina termínů používaných k měření centrality odráží tento sociologický původ .

Definice a charakterizace indexů centrálnosti

Indexy centrálnosti jsou zamýšleny jako odpovědi na otázku „Co charakterizuje důležitý vrchol?“ ". Odpověď je dána z hlediska skutečné funkce nad vrcholy grafu, kde mají produkované hodnoty poskytovat hodnocení, které identifikuje nejdůležitější uzly. Kvalifikátor „důležité“ má velký počet a různé interpretace, což vede k mnoha různým definicím ústředního významu. Byly navrženy dva režimy kategorizace. „Důležitost“ lze chápat ve vztahu k určitému typu toku nebo přenosu přes síť. To vede ke klasifikaci centralit podle typu toku považovaného za důležitý. „Důležitost“ lze také chápat jako míru účasti na soudržnosti sítě. To vede ke klasifikaci centralit podle způsobu, jakým měří tuto soudržnost. Tyto dva přístupy rozdělují míry ústřednosti do odlišných kategorií. Normálním důsledkem toho je, že pojem ústřednosti, který je vhodný pro jednu z kategorií, může vést k závěrům, které jsou v rozporu s očekáváním a jsou v rozporu s ostatními, pokud jsou použity v jiné kategorii.

Indexy ústřednosti, které měří soudržnost sítě, patří z větší části do stejné kategorie. Centrály, které měří počet cest z daného vrcholu, se tedy liší pouze povahou cest, které jsou brány v úvahu. Omezení zkoumání na tuto skupinu měr umožňuje flexibilní charakterizaci, která rozprostírá centrality ve spektru od cest délky jedna ( centrality stupně ) po nekonečné cesty ( centrality vlastního vektoru ).

Skutečnost, že mnoho měřítek centralit má podobné definice, také vysvětluje úzké korelace, které lze mezi těmito indexy pozorovat.

Charakterizace síťovým tokem

Síť lze považovat za popis cest, kterými datové toky procházejí. To vede k charakterizaci založené na typu toku a na typu cest zadržených ústředností. Tok může být založen na převodech, kdy každý nedělitelný prvek cestuje z jednoho uzlu do druhého, jako je dodávka balíků, která jde ze skladu do domu zákazníka. Dalším případem je sériová duplikace, kdy se jedná o repliku položky, která cestuje do dalšího uzlu, takže zdroj i cíl mají kopii. Příkladem je šíření informací drby, kde se informace šíří skrytým způsobem a kde zdrojový i cílový uzel mají informace o informacích na konci procesu přenosu. Posledním případem je paralelní vysílání, kdy jsou data duplikována na několik odkazů současně, jako rozhlasový program, který poskytuje stejnou informaci mnoha posluchačům současně.

K povaze cesty je přidána volba vektoru cesty, jinými slovy povaha cest, které jsou v síti brány v úvahu. Typ cest může být omezen tak, aby byl pouze typu geodetiky nebo kratších cest, nebo elementárních cest (neprochází dvakrát stejným vrcholem), jednoduchých cest (neprochází dvakrát stejnou hranou) nebo konečně neomezených cest , které mohou projít několikrát stejným vrcholem nebo stejnou hranou.

Charakterizace strukturou cesty

Další klasifikaci lze odvodit ze způsobu, jakým je postavena ústřednost. Dále je rozdělena do dvou tříd. Centrálnosti jsou „radiální“ nebo „střední“ . Radiální centralita počítá cesty, které začínají nebo končí v daném vrcholu. Stupně a eigenvectorové centrality jsou příklady radiálních centralit, počítající počet cest délky jedna, respektive nekonečné délky. Medián centrálnosti počítá počet cest, které procházejí daným vrcholem. Kanonický příklad je betweenness centrálnost ( „betweenness centrálnost“), Freedman, který počítá počet nejkratší cesty přes daný vrcholu.

Podobně může počet zachytit buď „objem“, nebo „délku“ cest. „Hlasitostí“ se rozumí celkový počet cest daného typu. Tři příklady v předchozím odstavci spadají do této kategorie. „Délka“ měří vzdálenost mezi daným vrcholem a dalšími vrcholy v grafu. Nejznámějším příkladem je Freedmanova ústřední blízkost, což je celková geodetická vzdálenost od daného vrcholu ke všem ostatním vrcholům. Je třeba poznamenat, že tato klasifikace je nezávislá na typu počítaných cest (obecné, základní, jednoduché, geodetické).

Borgatti a Everett se domnívají, že tato typologie (radiální nebo střední centrálnosti, objem nebo délka) usnadňuje srovnání měr centrálnosti. Centrály, které jsou v této klasifikaci 2 × 2 umístěny ve stejné skupině, jsou dostatečně podobné, aby byly věrohodnými alternativami; lze rozumně porovnat, který z nich je pro danou aplikaci nejvhodnější. Míra, která jsou v různých skupinách, jsou naopak v samostatných kategoriích. Jakékoli hodnocení jejich srovnávací schopnosti má smysl pouze v kontextu předchozího stanovení kategorie, která je nejvhodnější, což činí srovnání formálním.

Objemové radiální centrality

Charakterizace strukturou cest ukazuje, že téměř všechny často používané centrálnosti jsou radiální i objemové míry. Ty kódují hypotézu, že ústřednost vrcholu je funkcí ústřednosti vrcholů s ním spojených. Centraly se od sebe odlišují způsobem, jakým je asociace definována.

Bonacich ukázal, že pokud je asociace definována v pojmech cest , rodinu centralit lze definovat délkou uvažované cesty. Stupeň Centrálnost účtu cesty o délce, centrálnost eigenvector účtu stezek nekonečné délky. Jiné definice asociace jsou také rozumné. Centrálnost alfa tedy umožňuje vrcholům zohlednit vnější zdroj vlivu. Centrálnost podgrafů Estrada navrhuje, aby se počítají jen obvody (trojúhelníky, čtverce, ...).

Podstata těchto měření spočívá v pozorování, že síly matice sousedství grafu poskytují počet cest délky daných touto silou. Podobně exponenciál matice také úzce souvisí s počtem cest dané délky. Předchozí transformace matice sousedství umožňuje definovat různé typy počítaných cest. V obou přístupech lze centralitu vrcholu vyjádřit nekonečným součtem, tj.

\ sum _ {{k = 0}} ^ {\ infty} \ beta ^ {k} A _ {{R}} ^ {{k}}

pro pravomoci matic, to znamená

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

pro exponenciál matic. V těchto vzorcích

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

Rodina měr Bonacich nemění matici sousedství. Alfa centrality nahrazuje matici sousedství jejím resolventem. Centrálnost podgrafu nahrazuje matici její stopou. Překvapivým závěrem je, že bez ohledu na počáteční transformaci matice sousedství mají všechny tyto přístupy společné hraniční chování.

Když se blíží nule, indexy konvergují směrem ke stupni centrálnosti. Když se blíží jeho maximální hodnota, indexy konvergují k centrálnosti vlastního vektoru. $\beta$ $\beta$

Důležitá omezení

Indexy centrálnosti mají dvě důležitá omezení, jedno je zjevné a druhé jemnější. Zjevným omezením je, že centralita, která je optimální pro jednu aplikaci, je často jen neoptimální pro jinou aplikaci. Pokud by tomu bylo jinak, nepotřebovali bychom tolik různých představ o ústřednosti.

Čím jemnějším omezením je běžně udělaná chyba, že číselná hodnota centrálnosti vrcholů naznačuje relativní důležitost vrcholů. Indexy centrálnosti jsou výslovně navrženy tak, aby vytvářely pouze hodnocení, které poskytuje vodítka o nejdůležitějších špičkách. Dělají to dobře, s výhradou tohoto omezení. Chyba je dvojí.

Za prvé, žebříček seřazuje pouze vrcholy v pořadí podle důležitosti, nevyčísluje rozdíl v důležitosti mezi různými hodnotami žebříčku. To však lze napravit aplikací Freemanovy centralizace na dotyčné opatření centrálnosti, které poskytuje vhled do důležitosti uzlů jako funkce rozdílů v jejich skóre centralizace.

Za druhé, funkce, které správně identifikují nejdůležitější vrcholy v dané síti nebo aplikaci, se nemusí nutně rozšířit na další vrcholy. U většiny ostatních uzlů v síti může být hodnocení bezvýznamné. To například vysvětluje, proč se při vyhledávání obrázků Google v rozumném pořadí zobrazují pouze první výsledky.

I když se nemožnost zobecnit indexy centrálnosti na zbytek sítě může na první pohled zdát protiintuitivní, vyplývá to přímo z výše uvedené definice.

Komplexní sítě mají heterogenní topologii. Protože optimální míra závisí na struktuře sítě nejdůležitějších vrcholů, je míra, která je pro tyto vrcholy optimální, pro zbytek sítě neoptimální.

Centrálnost titulů

Termín centrality stupně nebo centrality stupně („stupeň centrality“) je první historicky a koncepčně nejjednodušší. Je definován jako počet dopadajících odkazů na uzel (to znamená počet sousedů, které má uzel). Stupeň lze interpretovat z hlediska schopnosti uzlu zachytit cokoli, co prochází v blízkosti v síti (například virus nebo informace). V případě směrované sítě (kde odkazy mají směr) obvykle definujeme dvě samostatná měřítka centrálnosti stupňů, a to příchozí stupeň a odchozí stupeň . Podle toho příchozí stupeň počítá počet odkazů směrovaných do uzlu a odchozí stupeň je počet odkazů, které směrují uzel k ostatním. Pokud jsou vazby spojeny s nějakým pozitivním aspektem, jako je přátelství nebo spolupráce, vstup do studia se často interpretuje jako forma popularity a odchod do studia jako míra společenskosti. Centrálnost přicházejícího stupně se také nazývá centralita prestiže .

Stupeň ústřednosti vrcholu daného grafu s vrcholy a hranami je definován: $proti$ $G = (V, E)$ $N = | V |$ $M = | E |$

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

Někdy je tento stupeň centrálnosti vztahem mezi a , kde je vrchol maximálního stupně. Výpočet stupně centrálnosti pro všechny uzly v grafu má časovou složitost v zobrazení hustoty matice sousednosti grafu a má složitost v zobrazení hranami řídké matice . $\ deg (v)$ $\ deg (v ^ {*})$ $v ^ {*}$ $\ Theta (N ^ {2})$ $\ Theta (M)$

Definici centrálnosti na úrovni uzlu lze rozšířit na celý graf. V tomto případě mluvíme o centralizaci grafů . Nechť je uzel s největším stupněm centrálnosti v . Dovolit být vrchol graf, který maximalizuje následující množství , kde je uzel maximálního stupně v : $v ^ {*}$ $G$ $X = (Y, Z)$ $N = | Y | = | V |$ $H$ $y ^ {*}$ $X$

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

Poté je stupeň centralizace grafu definován poměrem: $G$

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

Hodnota je maximální, když graf obsahuje centrální uzel, ke kterému jsou připojeny všechny ostatní uzly ( hvězdný graf ), a v tomto případě . $H$ $X$ $H = (N-1) (N-2)$

Blízkost centrálnosti

V připojeném grafu je míra přirozené vzdálenosti mezi dvojicemi uzlů, definovaná délkou jejich nejkratších cest . Excentricita uzlu x je definován jako součet délek k všechny ostatní uzly, a blízkost je definován Bavelas jako inverzní na vzdálenosti, která je tím, že:

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

Centrálnější uzel má tedy menší vzdálenost od všech ostatních uzlů. Rozdíl mezi vzdáleností k uzlu nebo od uzlu je v neorientovaných grafech irelevantní, zatímco v orientovaných grafech jsou vzdálenosti od uzlu považovány za významnější míru ústřednosti, protože obecně (např. Na webu) má uzel malou kontrolu přes jeho příchozí odkazy.

Pokud graf není silně propojen , populární metodou je použití součtu vzájemných vzdáleností namísto inverzní k součtu vzdáleností, s konvencí : $1 / \ infty = 0$

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

Tento koncept byl formulován výslovně pod názvem harmonická centralita pro neorientované grafy Rochatem v roce 2009 a znovu navržen Opsahlem v roce 2010. Později byl obecně studován pro sítě orientované Boldi a Vigna (2014).

Harmonická centralita je nejpřirozenější modifikací Bavelasovy definice blízkosti podle obecného principu, který navrhli Massimo Marchiori a Vito Latora (en) v roce 2000, že v grafu s nekonečnými vzdálenostmi se harmonický průměr chová lépe než střední aritmetika. Ve skutečnosti lze Bavelasovu blízkost popsat jako nenormalizovanou převrácenou hodnotu aritmetického průměru vzdáleností, zatímco harmonická centrálnost je nenormalizovanou převrácenou hodnotou harmonického průměru vzdáleností.

Dangalchev (2006) ve své práci o zranitelnosti sítí navrhuje jinou definici neorientovaných grafů, a to:

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

Původní definice se používá . $d (x, y)$

Informace Centrálnost o Stephenson a zeleň (1989) je další míra blízkosti, který počítá Harmonická střední odolnost vzdálenosti k vrcholu x ; tato vzdálenost je menší, pokud x má mnoho cest s nízkým odporem, které ji spojují s jinými vrcholy.

V klasické definici centrálnosti blízkosti je šíření informací modelováno pomocí kratších cest. Tento model nemusí být nejrealističtější pro všechny typy scénářů komunikace. Byly tedy zkoumány odpovídající definice pro měření blízkosti, protože centrálnost náhodného procházení (en) zavedená Nohem a Riegerem (2004). Měří, jak rychle náhodně odeslané zprávy dosáhnou dalšího vrcholu - je to jakási „náhodná procházka“ verze centrální blízkosti. Hierarchické blízkosti (en) z Tran a Kwon (2014), je ústřední význam rozšířené blízkosti léčit v ještě jiným způsobem omezení pojmu blízkosti do grafů, které nejsou pevně spojené. Hierarchická blízkost výslovně zahrnuje informace o rozsahu dalších uzlů, které mohou být ovlivněny daným uzlem.

Centrálnost zprostředkovatele

Betweenness je míra centrálnosti na vrcholu jednoho grafu (je zde také betweenness z hran , který zde není podrobně). Centrálnost mezi body počítá, kolikrát uzel funguje jako bod průchodu nejkratší cestou mezi dvěma dalšími uzly. Linton Freeman (en) Byl představen jako opatření ke kvantifikaci kontroly člověka nad komunikací mezi jinými lidmi v sociální síti (en) Návrh vrcholů, u nichž je vysoká pravděpodobnost, že se objeví na krátké náhodně vybrané cestě mezi dvěma náhodně vybranými vrcholy mají vysoké zprostředkování.

Zprostředkování vrcholu v s vrcholy se vypočte takto: $proti$ $G = (V, E)$ $| V]$

Pro každý pár ( s , t ) vypočítáme nejkratší cesty, které je spojují.
Pro každý pár ( s , t ) určíme podíl nejkratších cest, které procházejí daným vrcholem, zde v .
Sčítáme tento zlomek přes všechny páry vrcholů ( s , t ).

Stručněji, zprostředkování může být reprezentováno

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

kde je celkový počet nejkratších cest od uzlu k uzlu a je počet takových cest, které procházejí . Zprostředkování můžeme normalizovat vydělením výsledku počtem párů bez v , což je počet, který se rovná v orientovaném grafu s vrcholy a v neorientovaném grafu. Například pro neorientovaný hvězdný graf je střední vrchol obsažený v jakékoli nejkratší cestě s mezilehlostí rovnou (nebo 1, pokud je normalizována), zatímco listy, které nejsou obsaženy v žádné kratší dráze, mají mezilehlost rovnou 0. $\ sigma _ {{st}}$ $s$ $t$ $\ sigma _ {{st}} (v)$ $proti$ $(N-1) (N-2)$ $NE$ $(N-1) (N-2) / 2$ $(N-1) (N-2) / 2$

Výpočet středních a proximitních centrál všech vrcholů v grafu vyžaduje výpočet nejkratších cest mezi všemi páry vrcholů v grafu, což u vertexového grafu vyžaduje čas s algoritmem Floyd-Warshall . V grafech s dutými hranami však může být Johnsonův algoritmus v čase efektivnější. U nevážených grafů lze výpočty provádět Brandesovým algoritmem, což vyžaduje čas . Normálně tyto algoritmy předpokládají, že grafy jsou neorientované, spojené, s více smyčkami nebo hranami. Když se zabýváme konkrétně grafy sítí, grafy jsou často bez smyček nebo hran, aby se zachovaly jednoduché vztahy (kde hrany představují spojení mezi dvěma lidmi nebo vrcholy). V tomto případě se pomocí Brandesova algoritmu vydělí konečné skóre centrálnosti o 2, aby se zohlednila skutečnost, že každá nejkratší cesta se počítá dvakrát. $\ Theta (N ^ {3})$ $NE$ $M$ $O (N ^ {2} \ log N + NM)$ $O (NM)$

Centrality vlastního vektoru

Centrálnost eigenvector ( „vlastního vektoru ústřední“), nebo spektrální ústřední je mírou vlivem uzlu v síti . Přiřadí relativní skóre všem uzlům v síti na základě konceptu, že připojení k uzlům s vysokým skóre přispívá více k skóre uzlu než stejná připojení k uzlům s nízkým skóre. PageRank z Googlu je varianta měření centrálnost eigenvector. Další míra ústřednosti, která s ní úzce souvisí, je ústřednost Katze (v) .

Výpočet ústřednosti vlastních vektorů pomocí matice sousedství

U daného grafu s vrcholy nechte jeho matici sousednosti definovanou tím, zda je vrchol spojen s vrcholem , a jinak. Vrchol Centrálnost skóre je číslo ověření vztah: $G = (V, E)$ $N = | V |$ $A = (a _ {{v, t}})$ $a _ {{v, t}} = 1$ $proti$ $t$ $a _ {{v, t}} = 0$ $proti$ $x_ {vb}$

x_ {v} = {\ frac {1} {\ lambda}} \ sum _ {{t \ v M (v)}} x_ {t} = {\ frac {1} {\ lambda}} \ sum _ {{t \ in G}} a _ {{v, t}} x_ {t}

kde je množina sousedů a je konstanta. Po přeskupení můžeme tuto rovnici napsat do vektorového zápisu jako vlastní vektorovou rovnici : $M (v)$ $proti$ $\ lambda$

{\ mathbf {Axe}} = {\ lambda} {\ mathbf {x}}

Obecně existuje několik vlastních čísel a několik vlastních řešení. Pokud však dále stanovíme, že koeficienty vlastního vektoru musí být kladné, Perronova-Frobeniova věta zajistí, že požadovanou míru ústřednosti poskytne pouze největší vlastní hodnota. Složka indexu příslušného vlastního vektoru pak dává skóre centrálnosti vrcholu v síti. Metoda iterace výkonu (en) je jedním z mnoha algoritmů pro výpočet vlastních čísel (en) . Tuto metodu lze navíc zobecnit na matice, jejichž vstupy jsou reálná čísla představující intenzitu připojení, jako ve stochastické matici . $\ lambda$ $proti$ $proti$

Centrality Katz a PageRank

Centrálnost Katz (en) je míra centrálnost generalizace. Centrálnost stupňů měří počet přímých sousedů, zatímco Katzova centralita měří počet všech uzlů propojených cestou a penalizuje příspěvky ze vzdálených uzlů. Matematicky je definován:

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

kde je útlumový faktor, přijatý v intervalu . $\ alfa$ $(0,1)$

Katzovu ústřednost lze považovat za variantu ústřednosti vlastních vektorů. Další formou Katzovy ústřednosti je:

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

Získává se z expresi vlastního vektoru ústřední nahrazením o . $x_ {j}$ $x_ {j} +1$

Víme, jak dokázat, že vlastní vektor spojený s největším vlastním číslem matice sousedství je limitem ústřednosti Katze, když má tendenci k nižším hodnotám. $NA$ $\ alfa$ $1 / \ lambda$

PageRank ověří následující rovnici:

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

kde je počet sousedů uzlu (nebo počet jeho předchůdců v orientovaném grafu). Ve srovnání s ústředností vlastních vektorů nebo ústředností Katz spočívá hlavní rozdíl v zavedení faktoru měřítka . Dalším rozdílem mezi PageRank a ústředností vlastních čísel je to, že PageRank je levý vlastní vektor (řádkový vektor), protože ve faktorech jsou indexy zaměňovány. ${\ displaystyle L (j) = \ součet _ {i} a_ {ij}}$ $j$ $L (j)$ $a _ {{ji}}$

Centrálnost perkolace

Tato část může obsahovat nepublikovanou práci nebo neauditovaná prohlášení (červenec 2018) . Můžete pomoci přidáním odkazů nebo odebráním nepublikovaného obsahu.

K určení „důležitosti“ jediného uzlu ve složité síti existuje řada opatření ústřednosti. Tato měření však kvantifikují význam uzlu z čistě topologického hlediska a hodnota uzlu nijak nezávisí na „stavu“ uzlu. Zůstává konstantní bez ohledu na dynamiku sítě. To platí i pro vážená zprostředkovatelská opatření. Uzel však může být velmi dobře umístěn, pokud jde o centrálnost zprostředkování nebo nějakou jinou míru ústřednosti, ale nemůže být umístěn centrálně jako součást sítě, ve které dochází k perkolaci. K pronikání „nákazy“ dochází ve složitých sítích v řadě scénářů.

Například 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ě. O šíření nemoci lze uvažovat také při vyšší úrovni abstrakce, s přihlédnutím k síti měst nebo populačních center propojených silniční, vlakovou nebo leteckou komunikací. Počítačové viry se mohou šířit po počítačových sítích. Zvěsti nebo zprávy o obchodních dohodách nebo obchodech se mohou šířit také prostřednictvím sociálních sítí lidí. Ve všech těchto scénářích se „nákaza“ šíří přes odkazy složité sítě a mění „stavy“ uzlů při jejím šíření, což je stav, který může nebo nemusí být obnoven. Například v epidemiologickém scénáři se jednotlivci při šíření infekce pohybují ze stavu „vnímavý“ do stavu „infikovaný“.

Hodnoty stavů, které mohou jednotlivé uzly nabývat, jsou v příkladech výše binární (jako přijaté / nepřijaté pro informaci), diskrétní (vnímavé / infikované / vyléčené) nebo dokonce spojité (například podíl infikovaných lidí) ve městě), jak se šíří nákaza. Společným znakem všech těchto scénářů je, že nákaza vede ke změně stavu uzlů v sítích. S ohledem na tuto skutečnost byla navržena Percolation Centrality (PC), která konkrétně měří důležitost uzlů, pokud jde o to, že pomáhají perkolaci prostřednictvím sítě. Toto opatření navrhli Piraveenan et al.

Perkolační centralita je definována pro daný uzel v daném čase jako podíl perkolačních cest, které procházejí tímto uzlem. Perkolační cesta je kratší cesta mezi dvěma uzly, kde je počáteční uzel již ovlivněn (např. Infikován). Cílový uzel může nebo nemusí být ovlivněn nebo v částečně ovlivněném stavu.

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

kde je celkový počet nejkratších cest od uzlu k uzlu a kde je počet takových cest, které procházejí . Perkolace stav uzlu v čase je třeba poznamenat , a dvě krajní případy nastávají, pokud indikuje stav beze změny v čase , zatímco indikující stav zcela ovlivněny v čase . Mezilehlé hodnoty označují částečně ovlivněné státy (například v městské síti by to bylo procento lidí infikovaných v daném městě). $\ 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 připojené k perkolačním cestám závisí na úrovních perkolace přiřazených zdrojovým uzlům, přiřazení založené na principu, že čím vyšší je úroveň perkolace zdrojového uzlu, tím větší jsou cesty, které začínají v tomto uzlu. Uzly, které jsou na nejkratších cestách z vysoce ovlivněných uzlů, jsou proto potenciálně důležitější pro perkolaci. Definici ústřední perkolace lze rozšířit tak, aby zahrnovala i váhy cílových uzlů. Výpočet ústřední perkolace pro síť uzlů a oblouků je časově náročný s účinnou implementací přijatou rychlým Brandesovým algoritmem. Pokud vezmeme v úvahu váhy cílových uzlů, výpočet nějakou dobu trvá . $NE$ $M$ $O (NM)$ $O (N ^ {3})$

Klikněte na centrálnost

Centrálnost kliknutí ( „cross-centrálnost kliknutí“) o uzel v grafu určuje připojení různých uzlových klik , klika je definována jako skupina lidí ovlivňovat ve více nebo méně časté. Uzel s vysokou centralitou kliknutí usnadňuje šíření informací nebo chorob v grafu. Matematicky je klika podgrafem, jehož uzly jsou navzájem spojeny. Centrálnost kliknutí uzlu grafu s vrcholy a hranami je počet kliknutí, ke kterým uzel patří. Toto opatření použilo Faghani v roce 2013, ale již jej ohlásili Everett a Borgatti v roce 1998, kde jej nazývají „ústřední přesnost kliky“ . $proti$ $G = (V, E)$ $| V |$ $| E |$ $X (v)$

Freemanova centralizace

Centralizace sítě měří poměr ústřednosti nejcentrálnější uzlu na ústřední ostatních uzlů. Centralizační opatření fungují ve dvou fázích: vypočítáme součet rozdílů v ústřednosti mezi nejcentrálnějším uzlem a ostatními, poté tuto veličinu vydělíme největším součtem rozdílů, které mohou existovat v síti stejné velikosti. Každá míra ústřednosti má tedy svou vlastní míru centralizace. Formálně, pokud je míra ústřednosti bodu , jestliže a největší míra v síti, a pokud je největší součet rozdílů v ústřednosti mezi všemi grafy stejného počtu uzlů, centralizace sítě je: $C_ {x} (p_ {i})$ $i$ $C_ {x} (p _ {*})$ $\ max \ sum _ {{i = 1}} ^ {{N}} C_ {x} (p _ {*}) - C_ {x} (p_ {i})$ $C_x$

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

Centrálnost založená na opatřeních podobnosti

Aby se dosáhlo lepších výsledků v hodnocení uzlů v dané síti, používají se pro obohacení měr centrálnosti v komplexních sítích opatření odlišnosti (specifická pro klasifikační teorii a dolování dat). To je ilustrováno na ústřednosti vlastních čísel, výpočtu ústřednosti každého uzlu díky řešení problému vlastních čísel.

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

kde (souřadnice koordinovat produkt) a je libovolná matice odlišnosti, definovaná mírou odlišnosti, například Jaccardova odlišnost daná: ${\ displaystyle W_ {ij} = A_ {ij} D_ {ij}}$ ${\ displaystyle D_ {ij}}$

{\ displaystyle D_ {ij} = 1 - {\ dfrac {| V ^ {+} (i) \ cap V ^ {+} (j) |} {| V ^ {+} (i) \ pohár V ^ { +} (j) |}}}

Když toto opatření umožňuje kvantifikovat topologický příspěvek (což je důvod, proč nazýváme centralita příspěvku) každého uzlu k centralitě daného uzlu, přičemž tyto uzly mají větší váhu / relevanci s větší odlišností, protože tyto - c umožňují přístup k uzlu vzhledem k uzlům, které samy nemají přímý přístup.

Všimněte si, že je non-negativní, protože i nezáporné matice, takže můžeme použít Perron, Frobeniova věta, aby zajistily, že výše uvedený problém je jedinečné řešení pro s non-negativní, což nám umožňuje odvodit ústřední každého uzlu síť. Proto je ústřední role uzlu ie: $Ž$ $NA$ $D$ ${\ displaystyle \ lambda = \ lambda _ {max}}$ $\ mathbf {c}$

{\ displaystyle c_ {i} = {\ dfrac {1} {n}} \ součet _ {j = 1} ^ {n} W_ {ij} c_ {j}, \, \, \, \, \, \ , j = 1, \ cdots, n}

kde je počet uzlů v síti. Několik opatření odlišnosti a sítí, kde byly testovány, přinesly ve studovaných případech lepší výsledky. $ne$

Rozšíření

Empirický a teoretický výzkum rozšířil pojem centrality kontextu statických sítí na dynamickou centralitu v rámci časově závislých sítí a dočasných sítí.

Zobecnění na vážené sítě studují Opsahl et al. (2010).

Pojem ústřednosti byl rozšířen i na úroveň skupiny. Například centralita Group Betweenness („Group Betweenness“) ukazuje podíl geodetik spojujících páry členů mimo skupinu mimo skupinu a procházejících prvky skupiny.

Poznámky a odkazy

Poznámky

Mark EJ Newman, Networks: An Introduction. , Oxford, Oxford University Press,2010, 772 s. ( ISBN 978-0-19-920665-0 a 0-19-920665-1 , číst online ).
Phillip Bonacich , „ Síla a centralita: rodina opatření “, American Journal of Sociology , University of Chicago Press, sv. 92,1987, str. 1170–1182 ( DOI 10.1086 / 228631 ).
Stephen P. Borgatti , „ Centrality and Network Flow “, Social Networks , Elsevier, sv. 27, 2005, str. 55–71 ( DOI 10.1016 / j.socnet.2004.11.008 ).
Stephen P. Borgatti a Martin G. Everett , „ Graficko -teoretický pohled na centralitu “, Social Networks , Elsevier, sv. 28, 2006, str. 466–484 ( DOI 10.1016 / j.socnet.2005.11.005 ).
Michele Benzi a Christine Klymko , „ Maticová analýza různých měr centrálnosti “, arXiv ,2013( číst online , konzultováno 11. července 2014 ).
Glenn Lawyer , „ Porozumění šířící se síle všech uzlů v síti: perspektiva kontinuálního času “, Sci Rep , sv. 5,2015, str. 8665 ( DOI 10.1038 / srep08665 )
Například na analytické stránce sociálních sítí .
Linton C. Freeman, „ Centrálnost v sociálních sítích. Koncepční objasnění “, Sociální sítě , sv. 1, n o 3,1979, str. 215–239.
Alex Bavelas, „ Komunikační vzorce ve skupinách zaměřených na úkoly “, J. Acoust. Soc. Am. , Sv. 22, n o 6,1950, str. 725–730.
G. Sabidussi, „ Index centrálnosti grafu “ Psychometrika , roč. 31,1966, str. 581–603.
Yannick Rochat. „ Centrálnost blízkosti se rozšířila i na nepřipojené grafy: Index harmonické centrality “ v Aplikacích analýzy sociálních sítí, ASNA 2009 .
Tore Opsahl, „ Centrálnost blízkosti v sítích s odpojenými komponentami “ .
Paolo Boldi a Sebastiano Vigna , „ Axioms for centrality “, Internet Mathematics , roč. 10,2014( číst online ).
Massimo Marchiori a Vito Latora , „ Harmony in the small-world “, Physica A: Statistická mechanika a její aplikace , sv. 285 n kostí 3-4,2000, str. 539–546 ( číst online ).
Ch. Dangalchev, „ Reziduální blízkost v sítích “, Phisica A , sv. 365,2006, str. 556.
KA Stephenson a M. Zelen, „ Rethinking centrality: Methods and examples “, Social Networks , sv. 11,1989, str. 1–37.
JD Noh a H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
T.-D. Tran a Y.-K. Kwon, „ Hierarchická blízkost účinně předpovídá geny nemoci v směrované signální síti “, výpočetní biologie a chemie ,2014.
Linton Freeman , „ Soubor měřítek ústřednosti založených na mezičase “, Sociometry , sv. 40,1977, str. 35–41 ( DOI 10,2307 / 3033543 )
Ulrik Brandes , „ Rychlejší algoritmus pro centralitu mezi centry “, Journal of Mathematical Sociology , sv. 25,2001, str. 163–177 ( DOI 10.1080 / 0022250x.2001.9990249 , číst online [PDF] , zpřístupněno 11. října 2011 )
Nacim Fateh Chikhi, kap. 1.2.4 „Spektrální centralita“ , Výpočet centrality a identifikace struktur komunit v grafech dokumentů ( číst online ) , s. 1.2.4 . 23-25.
http://www.ams.org/samplings/feature-column/fcarc-pagerank
MEJ Newman, „ Matematika sítí “ [PDF] (zpřístupněno 9. listopadu 2006 )
L. Katz, „ Nový index stavu odvozený od sociometrického indexu “, Psychometrika ,1953, str. 39–43.
P. Bonacich „ Simultánní skupinové a individuální centrality “ Social Networks , sv. 13,1991, str. 155–168.
Jak Google hodnotí webové stránky? 20Q: About Networked Life
Mahendra Piraveenan , „ Centralita perkolace : Kvantifikace graficko -teoretického dopadu uzlů během perkolace v sítích “, PLoSone , sv. 8, n o 1,2013( DOI 10.1371 / journal.pone.0053095 ).
Mohamamd Reza Faghani , „ Studie mechanismů šíření a detekce červů XSS v online sociálních sítích “, IEEE Trans. Inf. Forenzní a bezpečnostní ,2013
Linton C. Freeman , „ Centrality v sociálních sítích: Konceptuální vyjasnění “, Social Networks , sv. 1, n o 3,1979, str. 215–239 ( číst online )
(in) AJ Alvarez-Socorro , GC Herrera-Almarza a LA González-Díaz , „ Eigencentrality je založen na odlišnosti Opatření odhaluje centrální uzly v komplexních sítích “ , Scientific Reports , sv. 5,25. listopadu 2015( PMID 26603652 , PMCID 4658528 , DOI 10.1038 / srep17095 , číst online , přistupováno 17. února 2016 )
D. Braha a Y. Bar-Yam, „ Od ústřednosti k dočasné slávě: dynamická ústřednost v komplexních sítích. », Složitost , sv. 12,2006, str. 59–63.
SA Hill a D. Braha, „ Dynamický model časově závislých komplexních sítí “, Physical Review E , sv. 82, n O 046 105,2010.
T. Gross a H. Sayama (eds), Adaptive Networks: Theory, Models and Applications , Springer,2009.
P. Holme a J. Saramäki, Temporal Networks , Springer,2013.
Tore Opsahl , Filip Agneessens a John Skvoretz , „ Centrálnost uzlů ve vážených sítích: zobecňující stupeň a nejkratší cesty “, Social Networks , sv. 32, n o 3,2010, str. 245 ( DOI 10.1016 / j.socnet.2010.03.006 , číst online ).
MG Everett a SP Borgatti, „ Extending centrality“ , 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, str. 57–76.
Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009). Společný útok na anonymitu uživatelů internetu , Internet Research 19 (1)

Zdroj (fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „ Centrality “ ( viz seznam autorů ) . Další bibliografie

D. Koschützki, KA Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl a O. Zlotowski, „Centrality Indices“ , v U. Brandes, U. a T. Erlebach (eds), Analýza sítě: Metodické základy Springer-Verlag, kol. "LNCS" ( n o 3418)2005, str. 16-61
John Scott a Peter J. Carrington (eds), The SAGE Handbook of Social Network Analysis , SAGE Publications,2011, 640 s. ( ISBN 978-1-84787-395-8 , online prezentace )
My T. Thai a Panos M. Pardalos (eds), Handbook of Optimization in Complex Networks: Communication and Social Networks , Springer Science & Business Media, coll. "Springer optimalizace a její aplikace" ( n o 58)2011, 544 s. ( ISBN 978-1-4614-0857-4 , číst online )
(en) John G. Scott, Social Network Analysis , Los Angeles, SAGE Publications Ltd,2012, 3 e ed. , 216 s. ( ISBN 978-1-4462-0904-2 )
Stephen P Borgatti, Martin G. Everett a Jeffrey C Johnson, Analýza sociálních sítí , SAGE Publications Ltd,2013, 304 s. ( ISBN 978-1-4462-4741-9 )

Související články

externí odkazy

PageRank v pythonu
Centrálnost
R a statnet - podrobný přehled
Nicolas Carayol, „ Struktura sociálních sítí “ , Analýza a modelování sítí , University of Bordeaux IV (konzultováno 9. července 2015 ) .
Robert A. Hanneman, „ Úvod do metod sociálních sítí: Centrality and power “, na Kalifornské univerzitě v Riverside