Nesta seção, apresentaremos alguns conceitos usuais em redes como conectivi- dade, distribuição de conectividade, menor caminho médio e coeficiente de agregação.
2.2.1 Conectividade
plo, observando o grafo de Euler, figura 2.1(b), é possível ver que este grafo possui três nós de conectividade k = 3 e um nó de conectividade k = 5. Um nó muito conectado é denominado de pólo ou hub e sua presença em uma rede tem grande influência em sua estrutura.
Um outro conceito importante, para o caso de uma rede direcionada, é o de co- nectividade de entrada (kin) e de saída (kout). Se a conectividade é de entrada a ligação
aponta para o nó. Caso contrário, na connectividade de saída, a ligação sai do nó e aponta para outro como ilustra a figura 2.5. A conectividade total (k) do nó, nesse caso, é a soma das conectividades de entrada e saída, ou seja, k= kin+ kout.
Figura 2.5:Conectividades de entrada e saída, kine kout, de um nó. A conectividade k= kin+ kout é número total de ligações do nó. Figura adaptada da referência [9].
2.2.2 Distribuição de conectividade
A distribuição de conectividade P(k) é definida como o número de nós com k liga- ções e, quando normalizada, podemos definí-la como a probabilidade de um nó, escolhido ao caso, ter exatamente k ligações [10]. Como observado nas figuras 2.2, 2.4(a) e 2.4(b), os nós de uma rede, exceto para redes regulares, possuem números distintos de ligações. Entretanto, dependendo do tipo da rede, embora os nós da rede possam possuir números distintos de ligações, elas podem apresentar um k típico. Um exemplo, desse tipo de rede, são as redes aleatórias de Erdös-Rényi. Nesse caso, a distribuição de conectividade decai muito rapidamente com P(k) ∼ 1/k!, para k muito grande. Para essa distribuição, todos os seus momentos,∑kknP(k)/∑kP(k), são finitos mesmo quando o tamanho da rede tende
para o infinito e, assim, o valor médio da conectividade, ܂k܂ = ∑kkP(k), é uma escala
típica para as conectividades [8, 9].
Em contraste, numerosas redes reais tais como Internet e rede celular, têm dis- tribuições decaindo muito lentamente. Os momentos de alta ordem dessas distribuições divergem quando fazemos a rede tender para o infinito. Esse decaimento lento é caracte- rizado por um decaimento tipo lei de potência expresso por P(k) ∼ k−γ. As distribuições
tipo lei de potência são chamadas livre de escala e as redes com tais distribuições são cha- madas de Redes Complexas. Este termo indica a ausência de uma escala típica, ou seja, sem um número característico de ligações, como apresentam as redes aleatórias [8, 9] ou as redes regulares que possuem um k fixo.
2.2.3 Menor caminho médio
Em uma rede, a distância (ou menor caminho), di,j, entre dois nós i e j, é definida
como o menor número de ligações entre eles [8, 18]. O menor caminho médio l, é dado pela média de di,j sobre todos os N(N − 1)/2 pares de nós, ou seja,
l= 2
N(N − 1) ∑i≠j
di,j. (2.1)
Embora possa parecer uma ideia simples o menor caminho representa uma das ideias básicas no estudo de Redes Complexas. Ele desempenha um papel importante no transporte e comunicação dentro de uma rede. Suponha, por exemplo, que precisemos enviar uma informação de um computador para outro através da Internet, excetuando- se os possíveis ”congestionamentos”, o menor caminho oferecerá a forma mais eficiente para o tráfego daquela informação, uma vez que, por ele, os dados serão transferidos numa rapidez ótima.
Outro conceito que, de certa forma, associa-se com a noção de caminho em redes é o de diâmetro lD [8, 22]. Este é definido como o caminho mais longo entre dois escolhi-
dos aleatoriamente. A importância desta definição se dá, por exemplo, em situações em que se pretende analisar a robustez da rede à ataques, sendo eles dirigidos ou aleatórios. Alterações no valor do diâmetro são indicativos de quão forte é a estrutura topológica
da rede. Se o grafo que estamos considerando é desconectado (grafos com aglomerados isolados), dizemos que seu diâmetro é infinito, pois não é possível conectar todos os pares de nós nessa rede. Neste caso, é mais apropriado definir o diâmetro da rede como sendo o diâmetro máximo de seus aglomerados.
2.2.4 Coeficiente de agregação
Uma propriedade interessante das redes tipo sociais é que formam grupos. Cada membro do grupo pode estar vinculado pelas relações de amizades, profissionais, por exemplo, de forma que cada membro conhece a maioria dos outros membros, existindo uma tendência de agregação entre eles. Esta tendência de agregação, pode ser quantifi- cada pelo coeficiente de agregação que mede, dentre o número total de vizinhos de um nó, quantos desses são vizinhos entre si [8, 23]. Em outras palavras, se um nó i tem zi pri-
meiros vizinhos com ki ligações entre eles, o coeficiente de agregação pode ser expresso
como: Ci(zi) = ki 1 2zi(zi− 1) , (2.2)
onde zi(zi− 1)/2 são todas as possíveis ligações entre os zi′sprimeiros vizinhos do nó i. A
grandeza Ci(zi) assume valores no intervalo 0 ≤ Ci(zi) ≤ 1. Quando Ci(zi) = 0, entende-
mos que os vizinhos do nó i não se conhecem e, portanto, não estabelecem ligações entre si. Entretanto, quando Ci(zi) = 1 existem todas as ligações possíveis presentes entre todos
os primeiros vizinhos do nó i.
A figura 2.6, ilustra um exemplo simples. Nesse exemplo, temos um nó i (símbolo vermelho) conectado a seis primeiros vizinhos (símbolos pretos). Queremos determinar, para este sistema, o seu coeficiente de agregação. Para responder esta questão, devemos verificar, incialmente, qual a vizinhança de i e quantos dos seus primeiros vizinhos estão conectados entre si. Neste caso, podemos ver que cinco dos seis vizinhos dele estão conec- tados (ver linhas verdes), ou seja, ki = 5. Assim, usando a equação 2.2, é possível mostrar
Figura 2.6: Vizinhança de i com zi= 6, ki= 5 e Ci(zi) = 13.
Suponhamos que o sistema mostrado na figura 2.6 seja parte de uma rede muito grande. O que determinamos, neste exemplo, foi apenas o coeficiente de agregação local. Então, como determinar o coeficiente de agregação para toda rede? Neste caso, é conve- niente determinarmos o coeficiente de agregação médio da rede que é obtido somando sobre todos os Ci′se dividindo pelo número total de nós da rede, ou seja,
C= 1 N ∑i Ci(zi) = 1 N ∑i ki 1 2zi(zi− 1)