Centralitatea de întrepătrundere

Centralitatea de întrepătrundere este o versiune a centralității de întrepătrundere ponderate, dar ia în considerare „starea” nodurilor sursă și țintă ale fiecărei căi cele mai scurte la calcularea acestei ponderi. Percolarea unei „contagiuni” are loc în rețelele complexe într-o serie de scenarii. De exemplu, o infecție virală sau bacteriană se poate răspândi în rețele sociale de persoane, cunoscute sub numele de rețele de contact. Răspândirea unei boli poate fi, de asemenea, luată în considerare la un nivel mai înalt de abstractizare, prin luarea în considerare a unei rețele de orașe sau centre de populație, conectate prin legături rutiere, feroviare sau aeriene. Virușii informatici se pot răspândi prin rețele de calculatoare. Zvonurile sau știrile despre ofertele și afacerile comerciale se pot răspândi, de asemenea, prin intermediul rețelelor sociale de persoane. În toate aceste scenarii, o „contagiune” se răspândește prin legăturile unei rețele complexe, modificând „stările” nodurilor pe măsură ce se răspândește, fie că se recuperează sau nu. De exemplu, într-un scenariu epidemiologic, indivizii trec de la starea „sensibilă” la starea „infectată” pe măsură ce infecția se răspândește. Stările pe care le pot lua nodurile individuale în exemplele de mai sus ar putea fi binare (cum ar fi primit/nu a primit o știre), discrete (susceptibil/infectat/recuperat) sau chiar continue (cum ar fi proporția de persoane infectate dintr-un oraș), pe măsură ce contagiunea se răspândește. Trăsătura comună în toate aceste scenarii este că răspândirea contagiunii are ca rezultat schimbarea stărilor nodurilor din rețele. În acest sens, a fost propusă centralitatea de percolație (PC), care măsoară în mod specific importanța nodurilor în ceea ce privește contribuția la percolația prin rețea. Această măsură a fost propusă de Piraveenan et al.

Centralitatea de percolație este definită pentru un nod dat, la un moment dat, ca fiind proporția de „căi de percolație” care trec prin acel nod. O „cale percolată” este cea mai scurtă cale între o pereche de noduri, în care nodul sursă este percolat (de exemplu, infectat). Nodul țintă poate fi percolat sau nepercolat sau într-o stare de percolare parțială.

P C t ( v ) = 1 N – 2 ∑ s ≠ v ≠ r σ s r ( v ) σ s r x t s ∑ – x t v {\displaystyle PC^{t}(v)={\frac {1}{N-2}}\suma _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}}_{s}}{{\suma {}-{x^{t}}_{v}}}}

unde σ s r {\displaystyle \sigma _{sr}}

este numărul total al celor mai scurte căi de la nodul s {\displaystyle s}

până la nodul r {\displaystyle r}

și σ s r ( v ) {\displaystyle \sigma _{sr}(v)}

este numărul acelor căi care trec prin v {\displaystyle v}

. Starea de percolație a nodului i {\displaystyle i}

la momentul t {\displaystyle t}

se notează cu x t i {\displaystyle {x^{t}}_{i}}.

și două cazuri speciale sunt atunci când x t i = 0 {\displaystyle {x^{t}}_{i}=0}

care indică o stare nepercolată la momentul t {\displaystyle t}

, în timp ce atunci când x t i = 1 {\displaystyle {x^{t}}_{i}=1}

ceea ce indică o stare complet percolată la momentul t {\displaystyle t}.

. Valorile intermediare indică stări parțial percolate ( de exemplu, într-o rețea de localități, acesta ar fi procentul de persoane infectate în acel oraș).

Ponderile atașate căilor de percolație depind de nivelurile de percolație atribuite nodurilor sursă, pornind de la premisa că, cu cât nivelul de percolație al unui nod sursă este mai mare, cu atât mai importante sunt căile care pornesc de la acel nod. Nodurile care se află pe căile cele mai scurte care provin din noduri cu un nivel ridicat de percolație sunt, prin urmare, potențial mai importante pentru percolație. Definiția PC poate fi, de asemenea, extinsă pentru a include și ponderile nodurilor țintă. Calculele centralității percolației se execută în O ( N M ) {\displaystyle O(NM)}.

timp cu o implementare eficientă adoptată din algoritmul rapid al lui Brandes, iar în cazul în care calculul trebuie să ia în considerare ponderile nodurilor țintă, timpul în cel mai rău caz este de O ( N 3 ) {\displaystyle O(N^{3})}