Quando queremos estabelecer se dois grafos são similares é comum verificarmos se o número de nós e enlaces são próximos. Contudo, mesmo em situações em que estes números são distantes podemos, ainda assim, determinar alguma similaridade por meio da densidade.
A densidade de um grafo é a razão do número de enlaces no grafo pelo número de enlaces no grafo completo equivalente. Um grafo equivalente, neste caso, é aquele possui o mesmo número de nós do que o grafo original. Um grafo completo é aquele em que todos os nós estão ligados entre si. Em outras palavras, a densidade é uma relação da quantidade de enlaces que uma rede possui e da quantidade de enlaces possíveis na rede, o que é determinado pela quantidade de nós.
Esta medida é diferente para grafos não-dirigidos e digrafos. Isso ocorre porque o número de enlaces em um grafo não dirigido completo com $n$ nós é de $\frac{n(n-1)}{2}$. Em um grafo dirigido este valor é de $n(n-1)$. Assim, sendo $m$ a quantidade de enlaces, então para grafos não-dirigidos temos
$densidade = \frac{2m}{n(n-1)}$
Já em digrafos temos
$densidade = \frac{m}{n(n-1)}$
O valor da densidade varia entre 0%, para um grafo sem enlaces, e 100%, para um grafo completo. De modo geral, redes complexas reais tendem a ter baixa densidade porque costumam ser esparsas, i.e., tem muito menos enlaces do que seria possível com a quantidade de nós.
Para exemplificar, considere as redes estudadas no trabalho seminal de Watts e Strogatz: a rede de colaboração de atores de filmes (atores), a rede de distribuição de energia do oeste americano (energia) e a rede neural do C. elegans (elegans). A tabela abaixo mostra como se comporta a densidade de cada uma destas redes. Observe que a maior densidade (elegans) é menor que 3% e nas redes maiores (i.e., com mais nós) a densidade tende a ser bem pequena.
Comentários
Postar um comentário