Topologias de rede – AUGUSTO DE FRANCO

Conteúdo origial em Augusto de Franco

Topologias de rede

A distribuição (I) cresce com o número de conexões (C). E descresce com o crescimento de nodos desconectados e de conexões eliminadas, porém em razões distintas. Eliminar um nodo pode, em alguns casos, desconectar apenas mais um nodo e, simultaneamente, muitas conexões. O número de conexões eliminadas com a eliminação de um nodo é – na razão direta do número de nodos da rede (N) – muito maior do que o número de nodos desconectados. As duas variáveis – D e E – comportam-se, assim, de modo diferente para efeitos de distribuição.

>>>

‘Carta Rede Social’, ex-‘Carta Capital Social’ (e antiga ‘Carta DLIS’) é uma comunicação pessoal de Augusto de Franco enviada quinzenalmente, desde 2001, para milhares de agentes de desenvolvimento e outras pessoas interessadas no assunto, do Brasil e de alguns países de língua portuguesa e espanhola. A presente ‘Carta Rede Social 168’ está sendo encaminhada para 10.194 destinatários.

Prezado(a) Leitor(a)

Passei os últimos dias mergulhado numa investigação sobre topologias de rede. Creio que encontrei algumas coisas interessantes, ainda que usando um formalismo matemático elementar (o que, nesse caso, é até bom): formulei uma equação para calcular o índice de distribuição de uma rede e também uma matriz topológica para caracterizar inequivocamente as configurações possíveis de uma rede (da totalmente centralizada à totalmente distribuída). Nesta ‘Carta Rede Social 168’ vou tentar fazer um resumo dos primeiros resultados desses trabalhos (que ainda precisam, certamente, passar por uma revisão cuidadosa).

É certo que agora, para avançar mais, preciso de ajuda. Estou, há muitos anos, afastado das abordagens matemáticas. Imagino que na Escola-de-Redes possamos exercer a ajuda-mútua nessas investigações. Para quem não sabe, a Escola-de-Redes é uma rede de pessoas dedicadas à investigação teórica e à disseminação de conhecimentos sobre redes sociais e à criação e transferência de tecnologias de netweaving. Para saber mais clique em http://www.escoladeredes.org Para se conectar clique em http://escoladeredes.wordpress.com

REDES DISTRIBUÍDAS E REDES CENTRALIZADAS

Em uma carta anterior já escrevi que, a rigor, não podemos falar em redes distribuídas ou redes centralizadas (monocentralizadas ou multicentralizadas, quer dizer, descentralizadas). Deveríamos falar em graus de distribuição (ou, inversamente, em graus de centralização).

Vamos retomar, para começar, os diagramas propostos originalmente por Paul Baran em um documento em que descrevia a estrutura de um projeto que mais tarde se converteria na Internet:

Baran, Paul (1964). “On distributed communications: I. Introduction to distributed communications networks” in Memorandum RM-3420-PR, August 1964. Santa Mônica: The Rand Corporation, 1964.

Os mencionados diagramas foram reunidos e melhorados por Rodrigo Araya e divulgados por David de Ugarte (2007) no livro “O poder das redes” (Porto Alegre: ediPUCRS/CMDC, 2008):

Para saber mais sobre Paul Baran clique no link abaixo:

http://www.ibiblio.org/pioneers/baran.html

Para ler o trabalho original de Paul Baran (1964), onde aparecem pela primeira vez seus famosos diagramas, faça o download do memorandum clicando no link abaixo:

http://www.rand.org/pubs/research_memoranda/2006/RM3420.pdf

Pois bem. Rede centralizada é aquela que configura o padrão um-com-todos, enquanto que rede distribuída é aquela que configura o padrão todos-com-todos.

Entre a monocentralização (o grau máximo de centralização, que no diagrama de Baran aparece como rede centralizada) e a distribuição máxima (todos os caminhos possíveis, correspondendo ao número máximo de conexões para um dado número de nodos – que não aparece no terceiro grafo do diagrama de Paul Baran, por razões de clareza de visualização), existem muitos graus de distribuição. É entre esses dois limites que se realiza a maioria das redes realmente existentes.

Portanto, não parece muito consistente falar de rede centralizada ou rede distribuída, a não ser, em termos matemáticos, como limites. A partir de certo número de nodos, nenhuma rede social real consegue ser totalmente centralizada (isso seria supor a inexistência de conexões entre os nodos, mas apenas de conexões entre o nodo central e os outros nodos). Ora, a partir de certo número de nodos é impossível que isso aconteça, pois é o próprio tamanho (social) do mundo que impõe um determinado número mínimo de conexões entre quaisquer nodos escolhidos aleatoriamente. Assim, mesmo que não queiramos, os nodos ligados a um centro tendem também a estar ligados entre si em alguma medida. Esse número de nodos a partir do qual uma rede não conseguirá mais permanecer centralizada depende do mundo em que se está, dos seus graus de separação.

O mesmo vale, mutatis mutandis, para as redes com topologia considerada descentralizada. Existem diferentes graus de descentralização. Mas o menor grau de descentralização já é (localmente falando) um grau de distribuição. A descentralização máxima coincide com a distribuição (quando cada centro coincidir com cada nodo, é óbvio). Distribuir é des-con-centrar. A rigor, portanto, mais de um centro já des-con-centra. Há um problema com o segundo grafo de Baran (o da rede descentralizada). Os nodos conectados a cada um dos múltiplos centros não costumam estar totalmente desconectados entre si como aparece no segundo grafo de Baran (quer pensemos em filiais de uma empresa multinacional, quer pensemos em um partido de células).

Não se trata apenas de encontrar uma fórmula matemática, porque não existe um número ideal para uma rede poder ser considerada distribuída (a não ser o número total de conexões possíveis entre seus nodos, correspondendo ao grau máximo de distribuição).

O assunto merece um tratamento mais cuidadoso. Precisamos de um índice de distribuição de rede e, além disso, de uma maneira inequívoca de caracterizar uma topologia de rede.

ÍNDICE DE DISTRIBUIÇÃO DE REDE

As investigações que venho fazendo me levaram a propor um Índice de Distribuição de Rede (I):

I = (C – D).C/E —-> [Equação 1]

Na equação acima:

C = Número de conexões

D = Número de nodos desconectados com a eliminação do nodo mais conectado (sem contar este último)

E = Número de conexões eliminadas com a eliminação do nodo mais conectado.

Quando esse índice é mínimo (I = 0) temos uma rede centralizada (o caso limite de uma rede totalmente centralizada).

Quando esse índice é máximo (I = Imax) temos uma rede distribuída (é o caso limite de uma rede totalmente distribuída).

É claro que o Índice Máximo de Distribuição (Imax) pode ser calculado a partir do número de conexões (independentemente da configuração particular que assume a rede). Enquanto que o Índice Mínimo de Distribuição (Imin) será sempre igual a zero (correspondendo a uma rede totalmente centralizada).

Assim, para calcular o Imax (rede totalmente distribuída), pode-se aplicar a mesma equação acima (Equação 1), colocando no lugar de C (Número de Conexões), o Número Máximo de Conexões (Cmax), calculado, por sua vez, a partir da Equação 2 (abaixo):

Cmax = (N – 1).N/2 —-> [Equação 2]

onde N = Número de nodos.

As duas equações são válidas para quaisquer números de nodos, inclusive para o caso limite de um mundo com dois nodos, no qual não há diferença entre rede distribuída e rede centralizada (hierarquia) e, portanto, não se pode falar propriamente de rede. Com efeito, para um mundo de dois elementos (N = 2): Cmax = 1. Neste caso, o Índice de Distribuição Máxima (Imax) será: Imax = 0 (ou seja, será nulo, indicando uma rede totalmente centralizada).

Vejamos alguns exemplos simples, de redes com pouquíssimos nodos. Para um mundo de três elementos (N = 3): Cmax = 3 e, conseqüentemente, Imax = 0,5; para um mundo de quatro elementos: Cmax = 6 e Imax = 12; para um mundo de cinco elementos: Cmax = 10 e Imax = 25; e assim por diante.

Para cada um dos diferentes números de nodos considerados acima (2; 3; 4; e 5), os valores de Imax (respectivamente 0; 0,5; 12; e 25) correspondem a 100% de distribuição. A partir daí podemos atribuir porcentagens a cada configuração possível da rede.

Por exemplo, no caso de um mundo de 4 elementos (N = 4), temos os seguintes valores de I: I = 0 (rede totalmente centralizada, correspondendo a 0% de distribuição); I = 3 (rede com 25% de distribuição); I = 4 (rede com 33% de distribuição); I = 8 (rede com 67% de distribuição); I = 8,3 (rede com 69% de distribuição); e, finalmente, I = 12 (rede com 100% de distribuição; ou seja, rede totalmente distribuída). E, nesse mundo (de quatro elementos), portanto, só temos 6 configurações possíveis de rede, seis topologias distintas.

Cabe repetir que uma rede totalmente distribuída (Imax) é um caso matemático limite, no qual a eliminação do nodo mais conectado não desconecta nenhum outro nodo da rede (ou seja, em que D = 0).

Não basta, entretanto, que D seja igual a zero para caracterizar uma rede totalmente distribuída. Também é necessário que C (número de conexões) seja máximo: C = Cmax (e essa variável, como vimos, depende apenas do número de nodos) e que E (número de conexões eliminadas com a eliminação do nodo mais conectado) seja mínimo.

A distribuição (medida pelo índice I) cresce com o número de conexões (C). E descresce com o crescimento de nodos desconectados e de conexões eliminadas, porém em razões distintas. Eliminar um nodo pode, em alguns casos, desconectar apenas mais um nodo e, simultaneamente, muitas conexões. O número de conexões eliminadas com a eliminação de um nodo é – na razão direta do número de nodos da rede (N) – muito maior do que o número de nodos desconectados. As duas variáveis – D e E – comportam-se, assim, de modo diferente para efeitos de distribuição.

Enquanto a Equação 2 é rigorosamente correta em termos matemáticos, a Equação 1, que estabelece um Índice de Distribuição, é uma definição, e, como tal, é uma convenção (arbitrária, portanto, como ocorre com qualquer índice). No entanto, ela pode ser muito útil à análise das topologias de rede na medida em que fornece os graus possíveis de distribuição, que vai de zero (Imin = 0, rede totalmente centralizada) até um Imax (correspondendo à rede totalmente distribuída).

Destarte, alguns teoremas sugestivos podem ser demonstrados com o auxílio dessa equação. Por exemplo, na rede com grau máximo de distribuição cada nodo tem o mesmo número de conexões do que o nodo central da rede com grau máximo de centralização. Não há aqui uma grande descoberta. Mas o tratamento adotado é sugestivo porquanto deixa claro que, em geral, toda vez que eliminamos nodos ou caminhos (conexões), criamos centralização (ou acrescentamos à rede algum grau de centralização, reduzindo o valor de I).

Um outro exemplo interessante do efeito ilustrativo do presente tratamento é o cálculo do número de configurações que correspondem a graus diferentes de distribuição. Em um mundo de cinco elementos conectados em rede, temos, entre a centralização máxima (Imin = 0 => 4 conexões) e a distribuição máxima (Imax = 25 => 10 conexões), 16 configurações intermediárias diferentes.

Entretanto, configurações diferentes não correspondem necessariamente a graus de distribuição diferentes. Para tratar desse assunto temos que introduzir um outro recurso descritivo: o que chamei de Matriz Topológica de Rede.

MATRIZ TOPOLÓGICA DE REDE

Não podemos determinar uma topologia de rede partindo apenas do número de nodos e do número de conexões. É necessário, para tanto, construir uma matriz que indique o número de conexões para cada nodo:

(N – n | Nx) —-> [Matriz 1]

onde N = Número de nodos;

n é um número inteiro que varia no intervalo (1, N -1); e,

x = N – n (esse formalismo abstruso foi introduzido aqui em virtude das limitações do editor de texto).

Por exemplo, para um mundo de cinco elementos em rede, usando a Matriz 1 geramos um total de 45 matrizes específicas, indicando, porém, vários conjuntos de números que não correspondem, todos, a configurações topologicamente possíveis, além de configurações diferentes para um mesmo índice de distribuição. Vamos examinar em separado cada um desses problemas.

Para um mundo de 5 elementos em rede temos:

N = 5; logo: N – 1 = 4; N – 2 = 3; N – 3 = 2; e N – 4 = 1. Assim, vamos, desde a rede totalmente centralizada, onde 4 nodos têm apenas 1 conexão e 1 nodo (central) tem 4 conexões:

Matriz N=5 (Centralizada)
(4 | 1)
(3 | 0)
(2 | 0)
(1 | 4)

até a rede totalmente distribuída, onde temos 4 nodos com 5 conexões e nenhum nodo com 3, 2 ou 1 conexões:

Matriz N=5 (Distribuída)
(4 | 5)
(3 | 0)
(2 | 0)
(1 | 0)

Entre esses dois limites, temos 43 possibilidades “algébricas” (vamos dizer assim), que não correspondem necessariamente a possibilidades topológicas.

Além disso, temos matrizes que apresentam um número ímpar de conexões totais, o que não é possível, pois todas as conexões são pares (P2P) ou transitivas e, assim, o resultado da divisão por 2 deve dar um número inteiro. Eliminadas tais impossibilidades (conexões com frações), restam:

1 configuração com 10 conexões = 1 topologia; 2 com 9 conexões (mas somente 1 é topologicamente possível) = 1; 4 com 8 (mas 2 são impossíveis) = 2; 5 com 7 (mas 1 é impossível) = 4; 5 com 6 (mas 2 são impossíveis) = 3; 4 com 5 = 4; 3 com 4 = 3; 1 com 3 (impossível) = 0.

Ou seja, temos aqui um total de 18 topologias possíveis, que não podem ser caracterizadas apenas pelo número de nodos e de conexões, mas se referem, em geral, a índices distintos de distribuição.

Nem sempre, porém. Continuando com nosso exemplo de um mundo de 5 elementos conectados em rede, podemos ter, com 5 conexões, quatro topologias distintas:

Matriz N = 5 | 5A
(4 | 1)
(3 | 0)
(2 | 2)
(1 | 2)

Para a topologia 5A, temos I = 3,75 (ou seja, 15% de distribuição).

Matriz N = 5 | 5B
(4 | 0)
(3 | 0)
(2 | 5)
(1 | 0)

Para essa topologia 5B, que poderia ser representada geometricamente pelo pentágono, temos I = 12,50 (ou seja, 50% de distribuição).

Matriz N=5 | 5C
(4 | 0)
(3 | 2)
(2 | 1)
(1 | 2)

Para a topologia 5C, temos I = 6,66 (ou seja 26,64% de distribuição).

Matriz N=5 | 5D
(4 | 0)
(3 | 1)
(2 | 3)
(1 | 1)

Para a topologia 5D, temos, igualmente, I = 6,66 (ou seja, como na topologia C, 26,64% de distribuição).

Ou seja, conquanto a Matriz 5C e a Matriz 5D representem sistemas com distribuições diferentes de conexões, elas têm o mesmo índice de distribuição. E conquanto possam ser representadas por grafos distintos, são redes equivalentes do ponto de vista da distribuição.

As muitas limitações desse meio digital (no caso, do sistema que envia as ‘Cartas Rede Social’) impedem a publicação dos diagramas (grafos) que facilitariam a compreensão dos trabalhos que estou tentando resumir aqui.

Brevemente quem tiver interesse no assunto vai encontrar uma exposição mais detalhada – e ilustrada com diagramas – no meu livro “A Rede: um índice de explorações imaginativas no multiverso das conexões ocultas que configuram o que chamamos de social”, previsto para vir à luz no segundo semestre deste ano.

Há aqui algum conhecimento novo, por certo. Mas caberia perguntar agora para que serve tal conhecimento. Essa é uma pergunta que matemáticos não fariam; não, pelo menos, dessa forma. Entretanto, os que estão interessados não apenas em compreender as redes, mas em aplicar tal compreensão para entender melhor o funcionamento da sociedade e poder elaborar e aplicar tecnologias de netweaving precisam fazer tal pergunta. Na próxima carta vou tentar oferecer algumas respostas.

Muito obrigado por sua atenção e pela paciência de ter chegado até aqui.

Até a ‘Carta Rede Social 169’ e um abraço do

Augusto de Franco
augusto@augustodefranco.com.br

17 de julho de 2008.

Conecte-se à Escola-de-Redes, uma rede de pessoas dedicadas à investigação teórica e à disseminação de conhecimentos sobre redes sociais e à criação e transferência de tecnologias de netweaving. Uma boa oportunidade para conhecer com profundidade o que são redes sociais. Para saber mais clique em http://www.escoladeredes.org
Para se conectar clique em http://escoladeredes.wordpress.com

Anúncios
Post a comment or leave a trackback: Trackback URL.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: