Densidade

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.

Rede	n	m	densidade	TMC
atores	225.226	6.869.393	0,014%	3,65
energia	4.941	6.594	0,027%	18,7
elegans	282	1.974	2,491%	2,65

Acrescentamos ainda nesta tabela o tamanho médio dos caminhos (TMC) em cada uma destas redes. Por ele podemos observar que apesar da esparsidade das redes em estudo, elas possuem distâncias médias surpreendentemente pequenas. 

No caso da rede de atores, embora tenhamos muitos nós e uma quantidade de enlaces que é de menos de 0,02% dos enlaces possíveis, a topologia da rede é bastante eficiente, com uma média de 3,65 saltos entre um ator e outro. 

Já o pior caso de distâncias médias fica com a rede de energia, com TMC de 18,7 saltos entre um componente da rede e outro. A despeito disso, a rede é bastante eficiente, já que a eficiência dos enlaces é de 99,72%, com uma densidade de apenas 0,027%.