Entreness centrality

Percolation centrality é uma versão da centralidade da betweenness ponderada, mas considera o ‘estado’ dos nós de origem e de destino de cada caminho mais curto no cálculo deste peso. A percolação de um ‘contágio’ ocorre em redes complexas em uma série de cenários. Por exemplo, a infecção viral ou bacteriana pode se espalhar por redes sociais de pessoas, conhecidas como redes de contato. A propagação da doença também pode ser considerada num nível de abstracção mais elevado, ao contemplar uma rede de cidades ou centros populacionais, ligados por ligações rodoviárias, ferroviárias ou aéreas. Os vírus de computador podem se espalhar por redes de computadores. Rumores ou notícias sobre ofertas e negócios também podem se espalhar através de redes sociais de pessoas. Em todos estes cenários, um “contágio” espalha-se pelas ligações de uma rede complexa, alterando os “estados” dos nós à medida que se espalha, seja de forma recuperável ou não. Por exemplo, num cenário epidemiológico, os indivíduos passam de um estado ‘susceptível’ para um estado ‘infectado’ à medida que a infecção se espalha. Os estados que os nós individuais podem assumir nos exemplos acima podem ser binários (como receber/não receber uma notícia), discretos (susceptíveis/infectados/recuperados), ou mesmo contínuos (como a proporção de pessoas infectadas em uma cidade), à medida que o contágio se espalha. A característica comum em todos estes cenários é que a propagação do contágio resulta na mudança dos estados dos nós nas redes. A centralidade da percolação (PC) foi proposta com isto em mente, o que mede especificamente a importância dos nós em termos de ajudar a percolação através da rede. Esta medida foi proposta por Piraveenan et al.

Centralidade de percolação é definida para um determinado nó, em um determinado momento, como a proporção de ‘caminhos percolados’ que passam por aquele nó. Um ‘caminho percolado’ é um caminho mais curto entre um par de nós, onde o nó fonte é percolado (por exemplo, infectado). O nó alvo pode estar percolado ou não-percolado, ou em estado parcialmente percolado.

P C t ( v ) = 1 N – 2 ∑ s ≠ v ≠ r σ s r ( v ) σ s r x t s ∑ – x t v {\i1}{t}(v)={\i}frac {1}{N-

where σ s r {\i}displaystyle {sigma _{sr}}

é o número total de caminhos mais curtos a partir do nó s {\i}

ao nó r {\i1}displaystyle r

e σ s r ( v ) {\i1}displaystyle {\i}(v)}displaystyle _{\i}(v)}

é o número daqueles caminhos que passam por v {\i1}displaystyle v}

. O estado de percolação do nó i {\\i1}displaystyle i}

no momento t {\i1}displaystyle t

é denotado por x t i {x^{t}}_{i}}

e dois casos especiais são quando x t i = 0 {\i} {x^{t}}_{i}=0}

o que indica um estado não-percolado no momento t {\i1}displaystyle t

enquanto que quando x t i = 1 {\\i}_{i}=1}

que indica um estado totalmente percolado no momento t {\i1}displaystyle t

. Os valores entre eles indicam estados parcialmente percolados (por exemplo, numa rede de cidades, esta seria a percentagem de pessoas infectadas nessa cidade).

Os pesos anexos aos caminhos de percolação dependem dos níveis de percolação atribuídos aos nós de origem, com base na premissa de que quanto maior o nível de percolação de um nó de origem, mais importantes são os caminhos que se originam desse nó. Portanto, os nós que se encontram nos caminhos mais curtos originários de nós altamente percolados são potencialmente mais importantes para a percolação. A definição de PC também pode ser estendida para incluir também os pesos do nó de destino. Os cálculos de centralidade de percolação são executados em O ( N M ) {\\i1}displaystyle O(NM)}.

tempo com uma implementação eficiente adotada a partir do algoritmo rápido da Brandes e se o cálculo precisar considerar os pesos dos nós alvo, o pior caso é O ( N 3 ) {\i1}displaystyle O(N^{3})}