Índice de distribuição normalizado

[Gabriel R. de Andrade Silva]

Estive tentando encontrar uma maneira de comparar o índice de distribuição de redes com tamanhos diferentes.

Fiz alguns 'experimentos numéricos' com redes aleatórias, calculando o índice conforme explicado em

http://escoladeredes.ning.com/profiles/blogs/o-poder-nas-redes-sociais

Resultou uma característica interessante: em média, o índice parecia depender de algo como o número de nodos elevado ao cubo...

Acima: índice médio versus número de nodos, são 5 pontos entre 10 e 170 nodos, médias feitas em amostras de 45 a 14 mil grafos aleatórios. Abaixo: grafico superior em escala log x log , coeficiente angular da reta em torno de 3,1 e coeficiente linear aproximadamente -2,8 .

Coloquei no meu álbum todos resultados, com algumas explicações da metodologia.

http://escoladeredes.ning.com/photo/dependencia-de-i-em-relacao-ao/...
http://escoladeredes.ning.com/photo/alguns-grafos-com-10-nodos/next...

Contudo, me ocorreu agora uma abordagem diferente e muito mais simples. Observe a expressão do índice:

I = C.(C - D)/E

Conforme analisou Augusto no texto acima mencionado, e conforme verifiquei em diversos grafos de 10 a 200 nodos, o índice máximo parece corresponder ao máximo número de conexões (máximo C).

Alguns grafos com 40 nodos e seus índices de distribuição (no meu álbum está mais legível).

E o máximo C depende de número de nodos de acordo com

Cmax = N.(N-1)/2

Este é então o C de uma rede com todas conexões possíveis. Ora, D e E não são totalmente independentes de C. Sendo D a quantidade de nodos desconectados da rede pela eliminação do nodo mais conectado (sem contar este último) entendemos que D = 0 nesse caso, pois num mundo 100% conexo a remoção de um nodo qualquer não afeta em nada a rede. E se E é o número de conexões eliminadas com a eliminação do nodo mais conectado, logo, E = N-1, pois o nodo eliminado está conectado com todos os outros (no caso, esse nodo pode ser qualquer um) .

Alguns dos "mundos" 100% conexos, nos quais C = Cmax.

Portanto, C = Cmax, D = 0, E = N-1 e inserindo na expressão do índice obteremos o Imax

Imax = Cmax.Cmax/(N-1)

Imax = N.N.(N-1)/4

Daí a dependência com N elevado a 3 observada anteriormente nos experimentos. Tirando o logaritmo natural disso tem-se

ln(Imax) = 2.ln(N) + ln(N-1) - 2.ln(2)

para N grande é de se esperar que ln(N-1) se aproxime de ln(N) e aí

ln(Imax) = 3.ln(N) - 2.ln(2)

Aonde vemos o motivo do coeficiente angular da reta definida por x = ln(N) e y = ln(Imédio) se aproximar de 3. Apenas o coeficiente linar -2.ln(2) = -1,3863... não se aproximou do valor obtido nos experimentos anteriores.

A fim de entender melhor fiz novo 'experimento numérico' apenas com grafos 100% conectados, variando N de 10 a 2000. Obtive o seguinte:

log(I) contra log(N) - pontos em azul são os resultados do experimento simulado.

A curva contínua em preto é ln(Imax) calculado conforme expressão negritada acima. Segue análise dos pontos azuis:

Linear model Poly1:
y(x) = p1*x + p2
Coefficients (with 95% confidence bounds):
p1 = 3.006 (3.006, 3.007)
p2 = -1.432 (-1.438, -1.426)

Esses últimos resultados são mais coerentes com o Imax calculado , incluindo o coeficiente linear.

Então, como medida de comparação para o grau de distribuição em redes de tamanho diferente, fica a proposta de usar o I dividido por Imax.

Uma outra forma mais simples de escrever Imax seria:

Imax = n.Cmax/2

A razão I / Imax deverá estar sempre entre 0 e 1, independente do N .

[Gabriel R. de Andrade Silva]

I não-normalizado é o que o Augusto definiu aqui:

http://escoladeredes.ning.com/profiles/blogs/o-poder-nas-redes-sociais

e o normalizado é esse mesmo dividido por Imax.

I = Imax nos grafos completamente conectados. A idéia foi checar se estaria correta a expressão do Imax e fazer uma relação com os resultados anteriores.

[Luiz Eduardo Amaral]

Duas coisas:
1) O que você chama de índice normalizado? (consequentemente o não-normalizado também)
2) Se o I seria igual para vários grafos 100% conectados, ainda não entendi o porque do segundo experimento? Você queria ver que o Imax tinha um crescimento cúbico em relação ao aumento do N?

[Gabriel R. de Andrade Silva]

É isso mesmo. Nessa última simulação não fiz 2 grafos com mesmo N, são todos diferentes. Antes estava trabalhando com amostras de vários grafos para cada N e tirava uma média dos índices, porque eram grafos aleatórios, então tinha muita variação em um mesmo número de nodos. Mas quando fiz esse dos grafos totalmente conectados só gerei uma única matriz para cada N, já que não tem dois desses grafos com mesmo N. Assim, nesse caso o índice não-normalizado é diferente para todos, mas o I normalizado é o mesmo, são todos igual a 1.

[Luiz Eduardo Amaral]

No seu segundo experimento, com os grafos completamente conectados, apesar da simulação, o I de todos os grafos cuja quantidade de nodos é igual foi o mesmo, não foi? Por exemplo, gerar 10 grafos com 20 nodos, todos completamente conectados, nos dará sempre o mesmo I, certo? Então, porque a realização do segundo experimento?

[Gabriel R. de Andrade Silva]

Pois é Carlos, muitas coisas podem parecer "leis de escala" sendo na verdade polinômios ou algo totalmente diferente. Não sei muito sobre o 'clustering coefficient' mas gostaria de entender melhor algumas situações mais realistas. Obrigado pelas indicações!

[Carlos Boyle]

Gabriel no se si viste esto http://en.wikipedia.org/wiki/Clustering_coefficient del que nos ocupábamos acá: http://carlosboyle.blogspot.com/2008/07/la-comunidad-una-red-distribuida.html
Es interesante esta fórmula ln(Imax) = 3.ln(N) - 2.ln(2) que me hace acordar al Preferential attachment de BArabasi. Voy a seguir trabajando con todo esto
Ver acá http://ccl.northwestern.edu/netlogo/models/run.cgi?PreferentialAttachment.836.527. El preferentia atachment da una dimensión fractal característica de un valor cercano a 3, sin embargo el modelo de Barabassi es solo un modelo