Em redes complexas nem sempre todos os nós possuem caminhos entre si, já que pode acontecer de alguns nós da rede estejam desconectados dos demais, não havendo um caminho que permita sair destes nós desconectados para outro nó. Citamos este caso quando falamos de caminhos na rede e nomeamos estes grafos como desconexos. Neste post explicamos também que quando não há caminho para de um nó para outro, assumimos que a distância tem valor infinito.
Alguns grafos podem estar dispostos em diversos grupos de nós onde existem caminhos entre si, mas que estejam desconectados dos demais grupo. Chamamos cada grupo de nós de uma componente conectada do grafo desconexo. Porém é comum que grafos desconexos apresentem uma componente conectada maior dos que as demais, i.e., com maior número de nós do que as demais componentes. Esta componente nós chamamos de maior componente conectada.
Uma forma de medir a conectividade e importância da maior componente conectada é estimar quantos caminhos podem ser feitos na componente conectada. Esta métrica é calculada por
$ \begin{equation*} \epsilon = \frac{\sum\limits_{i \in N}\sum\limits_{j \in N}x_{ij}}{n(n-1)} \end{equation*}$
onde cada elemento $x_{ij}$ da equação é dado por
$\begin{equation*} x_{ij}= \begin{cases} 0, & \text{se}\ \nexists \ \text{caminho entre}\ i \ \text{e}\ j\\ 1, & \text{se}\ \exists \ \text{caminho entre}\ i \ \text{e}\ j\\ \end{cases}. \end{equation*}$
Esta métrica de conectividade ($\epsilon$) parte da observação de que existem $n(n-1)$ caminhos (considerando caminhos de ida e volta) entre todos os nós de um grafo qualquer e procura fazer a razão entre este valor e o número de caminhos efetivamente existentes entre cada um dos nós na rede simulada.
Portanto, de forma breve, a métrica que mostramos indica o percentual dos nós alcançáveis na rede. Esta métrica varia de zero, para o caso de um grafo sem enlaces, até 1, quando o grafo é conexo, i.e., todos os nós são alcançáveis a partir de qualquer outro nó.
O estudo da conectividade e das componentes conectadas de uma rede podem ajudar a entender o grau de fragmentação desta rede. No caso de redes sociais, a depender de como a rede é modelada, este tipo de análise pode ajudar a identificar a formação de grupos que se isolam dos demais, as chamadas bolhas sociais.
A conectividade também é usada para o estudo da robustez de redes complexas. Nestes tipos de estudo, um processo dinâmico de desagregação ocorre na rede, removendo nós e arestas devido a uma falha desses e propagando destas falhas na rede devido à interdependência entre os nós que falharam e os restantes. Assim, a métrica de conectividade pode ser usada para medir a fragmentação sofrida pela rede após a falha de seus elementos. Ainda voltaremos a abordar isso em outro post no futuro.
Comentários
Postar um comentário