Koeficient bohatého klubu - Rich-club coefficient

The koeficient bohatého klubu je metrika grafy a sítí, určené k měření rozsahu, v jakém se dobře připojené uzly také navzájem spojují. Sítě, které mají relativně vysoký koeficient bohatých klubů, údajně prokazují efekt bohatých klubů a budou mít mnoho spojení mezi uzly vysokého stupně. Koeficient rich-klubu byl poprvé představen v roce 2004 při studiu papíru Topologie internetu.^[1]^[2]

Efekt „bohatého klubu“ byl změřen a zaznamenán u sítí vědecké spolupráce a sítí letecké dopravy. Ukázalo se, že to výrazně chybí interakce bílkovin sítí.

Definice

Nenormalizovaná forma

Koeficient rich-klubu byl poprvé představen jako metrika bez měřítka parametrizovaná řadami stupňů uzlů.^[1] Nověji to bylo aktualizováno, aby bylo možné jej parametrizovat z hlediska stupňů uzlů k , označující mezní stupeň. Koeficient rich-club pro danou síť N je pak definována jako:

{ displaystyle phi (k) = { frac {2E _ {> k}} {N _ {> k} (N _ {> k} -1)}}}

(1)

^[3]^[4]^[5]

kde ${ displaystyle E _ {> k}}$ je počet hran mezi uzly stupně většího nebo rovného k, a ${ displaystyle N _ {> k}}$ je počet uzlů se stupněm větším nebo rovným k. Tím se měří, kolik hran existuje alespoň mezi uzly stupně k, normalizováno podle toho, kolik hran může být mezi těmito uzly v úplném grafu. Když je tato hodnota blízká 1 pro hodnoty k blízko k ${ displaystyle k_ {max}}$ , je interpretováno, že uzly vysokého stupně v síti jsou dobře propojeny. Přidružený podgraf uzlů s minimálně stupněm k se také nazývá graf „Rich Club“.

Normalizováno pro randomizaci topologie

Kritika výše uvedené metriky spočívá v tom, že nemusí nutně znamenat existenci efektu bohatého klubu, protože se monotónně zvyšuje i pro náhodné sítě. V některých stupně distribuce, není možné se vyhnout připojení vysokorychlostních nábojů. Z tohoto důvodu je nutné porovnat výše uvedenou metriku se stejnou metrikou v distribuci stupňů se zachováním randomizované verze sítě. Tato aktualizovaná metrika je definována jako:

{ displaystyle rho _ {rand} (k) = { frac { phi (k)} { phi _ {rand} (k)}}}

(2)

kde ${ displaystyle phi _ {rand} (k)}$ je metrika rich-klubu na maximálně randomizované síti se stejným rozložením stupňů ${ displaystyle P (k)}$ studované sítě. Tento nový poměr slevy nevyhnutelné strukturální korelace které jsou výsledkem rozdělení stupňů, což poskytuje lepší indikátor významnosti efektu bohatého klubu.

Pro tuto metriku, pokud pro určité hodnoty k my máme ${ displaystyle rho _ {rand} (k)> 1}$ , to znamená přítomnost efektu bohatého klubu.

Zobecnění

Obecné vlastnosti bohatosti

Přirozenou definicí „bohatosti“ uzlu je jeho počet sousedů. Pokud místo toho nahradíme obecnou metriku bohatosti v uzlech r, pak můžeme přepsat neškálovaný koeficient Rich-Club jako:

{ displaystyle phi (r) = { frac {2E _ {> r}} {N _ {> r} (N _ {> r} -1)}}}

(3)

Kde místo toho uvažujeme dílčí graf pouze na uzlech s mírou bohatosti alespoň r. Například na sítích vědecké spolupráce, nahrazujících stupeň bohatosti (počet spoluautorů) bohatostí sil (počet publikovaných prací), se dramaticky mění topologie bohatého klubového grafu.

Související metriky

Assortativity

The Assortativity sítě je měřítkem toho, jak jsou podobné uzly propojeny, kde se podobnost obvykle zobrazuje z hlediska stupně uzlu. Rich-club lze chápat jako konkrétnější notaci assortativity, kde se zabýváme pouze konektivitou uzlů nad rámec určité metriky bohatosti. Pokud by například síť sestávala ze sbírky rozbočovačů a paprsků, kde byly rozbočovače dobře připojeny, taková síť by byla považována za disassortativní. Vzhledem k silné propojenosti hubů v síti by však síť demonstrovala efekt bohatého klubu.

Příklad sítě, která je disassortativní a demonstruje efekt Rich Club. Červené uzly jsou rozbočovače a tvoří „bohatý klub“.

Aplikace

Koeficient rich-klubu sítě je užitečný jako heuristické měření robustnosti sítě. Vysoký koeficient bohatého klubu znamená, že rozbočovače jsou dobře připojeny a globální konektivita je odolná vůči jakémukoli odebíranému rozbočovači. Je také užitečné pro ověřování teorií, které se zobecňují na jiné sítě. Například důsledné pozorování vysokých koeficientů bohatých klubů pro sítě vědecké spolupráce přidává důkaz k teorii, že v rámci sociálních skupin má elita tendenci se navzájem sdružovat.

Implementace

Koeficient rich-klubu byl implementován v NetworkX, knihovna Pythonu pro síťovou analýzu. Tato implementace zahrnuje jak normalizované, tak normalizované formy, jak je popsáno výše.

Viz také

Reference

^ ^A ^b Zhou, Shi & Mondragón, Raúl J. (2004). „Fenomén Rich-Club v topologii internetu“. Komunikační dopisy IEEE. 8 (3): 180–182. arXiv:cs / 0308036. doi:10.1109 / lcomm.2004.823426.
^ Mattia Gasparini, Javier Luis Canovas Izquierdo, Robert Clariso, Marco Brambilla, Jordi Cabot: Analýza chování Rich-Club v projektech s otevřeným zdrojovým kódem. OpenSym 2019 řízení
^ Colizza, V. a Flammini, A. a Serrano, M. A. a Vespignani, A. (2006). "Detekce objednávání bohatých klubů ve složitých sítích". Fyzika přírody. 2. 2 (2): 110–115. arXiv:fyzika / 0602134. Bibcode:2006NatPh ... 2..110C. doi:10.1038 / nphys209.CS1 maint: více jmen: seznam autorů (odkaz)
^ McAuley, Julian J. a da Fontoura Costa, Luciano a Caetano, Tibério S. (2007). „Fenomén bohatého klubu napříč složitými síťovými hierarchiemi“. Aplikovaná fyzikální písmena. 91 (8): 084103. arXiv:fyzika / 0701290. Bibcode:2007ApPhL..91h4103M. doi:10.1063/1.2773951.CS1 maint: více jmen: seznam autorů (odkaz)
^ Opsahl, Tore; Colizza, Vittoria; Panzarasa, Pietro; Ramasco, José J. (2008). „Prominence and Control: The Weighted Rich-Club Effect“. Dopisy o fyzické kontrole. 101 (16): 168702. arXiv:0804.0417. Bibcode:2008PhRvL.101p8702O. doi:10.1103 / physrevlett.101.168702. PMID 18999722.

externí odkazy

Dokumentace NetworkX funkce koeficientu Rich Club

[rc_zhou-1] A ^b Zhou, Shi & Mondragón, Raúl J. (2004). „Fenomén Rich-Club v topologii internetu“. Komunikační dopisy IEEE. 8 (3): 180–182. arXiv:cs / 0308036. doi:10.1109 / lcomm.2004.823426.

[2] Mattia Gasparini, Javier Luis Canovas Izquierdo, Robert Clariso, Marco Brambilla, Jordi Cabot: Analýza chování Rich-Club v projektech s otevřeným zdrojovým kódem. OpenSym 2019 řízení

[rc_colizza-3] Colizza, V. a Flammini, A. a Serrano, M. A. a Vespignani, A. (2006). "Detekce objednávání bohatých klubů ve složitých sítích". Fyzika přírody. 2. 2 (2): 110–115. arXiv:fyzika / 0602134. Bibcode:2006NatPh ... 2..110C. doi:10.1038 / nphys209.CS1 maint: více jmen: seznam autorů (odkaz)

[rc_mcauley-4] McAuley, Julian J. a da Fontoura Costa, Luciano a Caetano, Tibério S. (2007). „Fenomén bohatého klubu napříč složitými síťovými hierarchiemi“. Aplikovaná fyzikální písmena. 91 (8): 084103. arXiv:fyzika / 0701290. Bibcode:2007ApPhL..91h4103M. doi:10.1063/1.2773951.CS1 maint: více jmen: seznam autorů (odkaz)

[rc_weighted-5] Opsahl, Tore; Colizza, Vittoria; Panzarasa, Pietro; Ramasco, José J. (2008). „Prominence and Control: The Weighted Rich-Club Effect“. Dopisy o fyzické kontrole. 101 (16): 168702. arXiv:0804.0417. Bibcode:2008PhRvL.101p8702O. doi:10.1103 / physrevlett.101.168702. PMID 18999722.

[1]

[2]

[3]

[4]

[5]