Escola de Redes

Índice de distribuição em 2 tipos de redes regulares complementares

Para não desandar em delírios matemáticos inúteis e fazer justiça a realidade do caos, tendo estudado um pouco sobre grafos aleatórios, fui compelido a dar uma olhada nos grafos regulares, ainda sob a ótica do índice de distribuição.

Redes reais são um misto de aleatoriedade com regularidade.

A configuração todos-com-todos é um exemplo de topologia regular.

Mundo 100% conexo: todos nodos se conectam a todos.

A partir disso é fácil imaginar dois outros tipos de topologia regular: polígonos e estrelas.

Grafos poligonais são mundos nos quais cada nodo se conecta apenas com seus 2 vizinhos imediatos

Estrelas formadas por todas diagonais dos polígonos. O mesmo que topologia todos-com-todos SEM as conexões com os 2 vizinhos imediatos.

A sobreposição dessas duas topologias resulta na configuração todos-com-todos. Será que isso também vale em relação ao índice de distribuição de cada uma delas?

Poderia o índice de distribuição de uma topologia ser calculado dividindo-a em duas ou mais?

Ou seja, computando separadamente os graus de distribuição de um polígono e o da estrela formada por suas diagonais, somando os dois obteremos o índice de distribuição da topologia todos-com-todos correspondente?

O grau de distribuição é computado através de

I = C.(C - D)/E .

Para padrões regulares seu cálculo não demanda grande esforço, pode-se obtê-lo observando os desenhos acima.

Nos polígonos o número de conexões é igual ao de nodos ( C = N ), se eliminássemos o nodo mais conectado (que, pela simetria, pode ser qualquer um) não desligaríamos nenhum outro da rede, logo, D = 0, mas eliminaríamos 2 conexões , então E = 2 . E o índice dos polígonos fica

Ipol = N.N/2

Nas estrelas consideradas temos C = (nro de diagonais) ou C = Cmax - N , uma vez que Cmax = N.(N-1)/2 é o máximo de conexões possíveis (todos-com-todos), o que resulta C = N.(N-3) . Logicamente vamos nos restringir aos casos de N > 3 , senão não há diagonais. Observe as figuras das estrelas. Claramente há uma simetria aqui também: todos nodos com o mesmo número de conexões, a saber, N-3 conexões cada um. Eliminar um deles não implicaria desconectar outro , a não ser para N = 4, aonde se desconectaria 1 nodo. Para N > 4 tem-se D = 0 e E = N-3, e o índice fica

Iestr = N.N.(N-3)/4

Para ficar realmente fácil ver a resposta vou fazer a normalização, dividindo por Imax (o índice da topologia todos-com-todos). Sendo Imax = N.N.(N-1)/4 , as razões I/Imax são

Ipol/Imax = 2/(N-1)

e

Iestr/Imax = (N-3)/(N-1) ,

sendo tais expressões válidas para qualquer N>4.

O que acontece se somarmos as duas razões? Resulta um valor constante, independente do N, a saber, 1.

(Ipol/Imax) + (Iestr/Imax) = 1

ou, multiplicando por Imax,

Ipol + Iestr = Imax

Então, de fato, a soma do índice do polígono com o da estrela resulta no índice da topologia todos-com-todos.

Plotagem dos índices de distribuição relativos dos polígonos (vermelho) e estrelas (azul) .

No gráfico acima temos o comportamento das razões I/Imax , começando em N=5, aonde ambos graus de distribuição são exatamente iguais a 50%, notamos as diferentes tendências das estruturas poligonais e estreladas.

Na configuração poligonal cada nodo se conecta apenas a seus 2 vizinhos imediatos. Uma estrutura como essa, à medida que cresce, tem seu grau de distribuição cada vez mais insignificante, em relação ao universo de máxima conectividade ("todos-com-todos"). Já num mundo "estrelado", onde todos nodos se conectam a todos MENOS seus 2 vizinhos imediatos, a expansão, o crescimento da estrutura torna o grau de distribuição cada vez mais próximo do máximo.

Noutras palavras, apesar do anel, roda ou ciranda ser muitas vezes adotado como um símbolo de união, fraternidade ou sinergia sua ação é pouco eficaz quando as pessoas se restrigem a interagir com seus vizinhos apenas. E se você não se relaciona com os seus vizinhos, família ou pessoas próximas mas cultiva muitas outras relações, inclusive com pessoas distantes, não se preocupe, você não vai para o inferno...

Agora, um delírio matemático final....

Conforme sugerido pictoricamente, a soma dos índices de distribuição de dois grafos com mesmo número de nodos sempre será igual ao índice da superposição dos dois grafos? Valeria isso para dois grafos quaisquer? Somente para grafos regulares? Sempre haveria um maneira de decompor um grafo em dois de modo a satisfazer essa condição?

Noutras palavras, a operação de calcular o I seria 'distributiva' sobre uma 'soma' definida pela superposição dos grafos nodo a nodo ? Simbolicamente:

g1 '+' g2 = g3

e denotando por I(g) o índice correspondente ao grafo g,

g1 '+' g2 = g3 => I(g1) + I(g2) = I(g3) ???

Exibições: 1881

Comentar

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

Entrar em Escola de Redes

© 2018   Criado por Augusto de Franco.   Ativado por

Badges  |  Relatar um incidente  |  Termos de serviço