Escola de Redes

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 .

Exibições: 402

Comentar

Você precisa ser um membro de Escola de Redes para adicionar comentários!

Entrar em Escola de Redes

Comentário de Gabriel R. de Andrade Silva em 25 novembro 2009 às 13:38
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.
Comentário de Luiz Eduardo Amaral em 25 novembro 2009 às 13:17
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?
Comentário de Gabriel R. de Andrade Silva em 24 novembro 2009 às 19:03
É 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.
Comentário de Luiz Eduardo Amaral em 24 novembro 2009 às 14:48
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?
Comentário de Gabriel R. de Andrade Silva em 12 novembro 2009 às 12:15
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!
Comentário de Carlos Boyle em 9 novembro 2009 às 10:10
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-distri...
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?PreferentialAtta.... 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

© 2019   Criado por Augusto de Franco.   Ativado por

Badges  |  Relatar um incidente  |  Termos de serviço