sistema cidades: de cidades a redes, sobre redes
teoria das redes
O nosso objetivo é verificar se uma mudança na geometria da cidade leva a mudanças na topologia da rede de encontros formada pelos agentes que ali interagem. Entretanto, precisamos entender o que pode significar eventuais diferentes topologias dessa rede. Na estrutura de pensamento que estamos seguindo, essa rede é de troca de informações, portanto, são relevantes propriedades que influenciam esta troca, que mudem o comportamento de difusão da informação na mesma. As redes podem ser diferenciadas entre si relativamente a questões como a existência de caminhos que permita atingir todos os elementos do conjunto, a distância máxima entre dois nós quaisquer, robustez, entre outras. A rede e a informação que estão aqui sendo tratadas de maneira abstrata, num cenário real, podem ser referentes à rede de fornecedores de uma fábrica, por exemplo. Como fica o abastecimento da fábrica se o único fornecedor ficar impedido de entregas temporariamente? E no caso de epidemias infecto-contagiosas, em que a transmissão se dá pelo contato entre as pessoas, diferentes topologias mudariam o seu comportamento, acelerando, desacelerando ou mesmo interrompendo a sua propagação, ou ainda criando algum circuito em que a epidemia fique eternamente circulando? São questões que mostram a relevância que a topologia pode ter.
Dentre os trabalhos que desenvolveram as teorias das redes, selecionamos quatro que entendemos terem introduzido maiores novidades nesse pensamento levando a mudanças de patamar, os de Erdos-Rényi (1959), Granovetter (1983), Watts-Strogatz (1998, apud WATTS, 2004) e Barabási-Albert (2002). Teoria de redes, teoria dos Grafos e topologia, são disciplinas fortemente relacionadas, com objetos de interesse com grande sobreposição, com as duas últimas compartilhando o fundador, Leonhard Euler e o problema das pontes de Königsberg (na antiga Prússia, atual Kaliningrado na Rússia) como parte do mito de criação. O problema envolve duas ilhas em um rio que atravessa a cidade, e sete pontes que ligam as duas entre si e entre as margens do rio. A questão é se seria possível atravessar todas elas apenas uma vez e voltar ao ponto de partida. Euler conseguiu provar que isso era impossível em 1736, lançando mão (e criando) as duas disciplinas. A prova se dá em que, de um determinado ponto, só se pode ir e voltar se esse estiver conectado a um número par de arestas.
A teoria dos grafos, assim nascente, trata da representação em vértices e arestas da relação em um fenômeno: os objetos e suas relações/conexões, estados em um processo, e as propriedades dessas relações. A topologia descreve as relações de posição dos objetos relativos uns aos outros, e trata de relações espaciais matemáticas independentes da geometria euclidiana. Um exemplo topológico clássico é o da equivalência entre um toróide e uma caneca, devido à continuidade das duas superfícies. Essas representações relacionais, de conexões e fluxos, se adaptam muito bem às discussões da teoria da complexidade, sendo largamente utilizadas. A teoria das redes, finalmente, é um desenvolvimento dessa junção, tratando de redes complexas, propriedades e dinâmicas relativas a elas, como robustez, emergência, criticalidade, adaptações, sendo bastante utilizada para representar (e estudar) fenômenos como redes ecológicas, econômicas, sociais, de transporte, entre outros.
elementos dos grafos e redes
As redes são usadas para representar relações de um conjunto de elementos, podendo descrever desde a relação entre objetos ou entre estados de um fenômeno dinâmico. Os nós costumam representar elementos, lugares ou estados (cidades, pessoas, adolescência), enquanto as arestas indicam a conexão entre eles ou troca de fase (estradas, grau de familiaridade, graduação da universidade). As representações mais populares de redes são os grafos e as matrizes de adjacências (figura matriz e grafo). Enquanto a representação gráfica do grafo é ótima para uma percepção geral da rede, especialmente sua forma e leituras topológicas, é na matriz de adjacências que se consegue operar a maior parte das métricas formais sobre suas propriedades.
A matriz de adjacências é uma matriz de tamanho n x n, onde n é o total de elementos da rede, seus vértices ou nós, e o valor do item nij se refere a aresta que conecta dois itens, ni e nj. Via de regra, assumem o valor de 0 quando não há conexão, 1 quando há. Pode ser representado pelo grafo G(V,A), V sendo o conjunto de vértices e A o de arestas, do tipo A = {(Va, Vb)}. Na representação gráfica, os nós são apresentados como pontos ou círculos, e as arestas mostram as conexões (figura SR1).
SR1. (a) matriz de adjacencia (b) grafo (c) representação gráfica
O elemento base da rede é o nó, e dá forma a rede a partir das suas conexões. Essas conexões indicam quem está conectado com quem e podem também representar características dessa relação. Por exemplo, na rede de comunicação televisão-audiência, a rede descreve a conexão da emissora com as pessoas que assistem. Não existe conexão das pessoas entre si. A informação flui apenas na direção da televisão para as pessoas, e temos uma rede direcionada. Já no caso da rede de telefonia, uma pessoa se conecta a outra e a informação flui nas duas direções, e temos uma rede não direcionada. As redes não-direcionadas possuem uma matriz de adjacência simétrica, ou seja, nij = nji. Na representação gráfica, uma aresta direcionada possui uma seta.
Essa troca de informação também pode ter peso diferente, uma gradação de intensidade. Em uma sala de aula, por exemplo, existe a troca de informação sobre a disciplina de estudo entre o professor e os alunos e entre os alunos entre si. Nesse caso, a expectativa é que uma declaração do professor sobre o assunto seja considerada mais acertada pelos alunos (com peso 5, por exemplo) do que alguma feita por algum dos demais colegas (com peso 1). Em geral é uma boa prática normalizar essa variação de modo que a aresta assuma valores entre 0 e 1, no exemplo, 1 para a fala do professor e 0.2 na fala dos colegas. Já numa votação no congresso, o voto de cada parlamentar (a informação trocada) tem o mesmo valor (todos com peso único, 1). Para representar o peso da aresta graficamente, diversas estratégias são utilizadas, desde a espessura da linha até a notação do valor junto da aresta.
A quantidade de conexões de um vértice é chamada de grau, e indica com quantos elementos cada nó da rede está conectado, a quantidade k de vizinhos. Como cada nó tem a sua quantidade específica de conexões, a distribuição de grau dos nós traz bastante informação sobre a rede. Podemos ter redes regulares, em que todos os nós apresentam o mesmo grau. Esse grau pode ser alto ou baixo. Como exemplo, imaginem-se 3 redes com 10 elementos e graus 2, 4 e 9. Em termos de consequências, de novo olhando a transmissão de informação, considere-se 1 tempo para transmitir de um nó para o outro e que cada nó transmita para todos os seus vizinhos. Na rede com k = 2, para a informação sair do nó inicial e atingir todos os nós são necessários 5 tempos. Já na rede com k = 4, 3 tempos, e para k = 9, 1 tempo será suficiente (figura SR2).
SR2. (a) rede k = 2 (b) rede k = 4 (c) rede k = 9
Outra consequência importante do grau das redes é a robustez. Considere-se a remoção de 1 aresta em cada uma dessas redes. Se a aresta removida for a do nó inicial, ao se proceder novamente a transmissão de uma informação serão necessários 9 tempos para atingir todos os nós. Na rede com k = 4, uma aresta a menos pode até fazer com que o nó desconectado receba a informação 1 tempo depois, porém a difusão alcança toda a rede nos mesmos 3 tempos. O mesmo vale para k = 9. Com 2 arestas removidas pode-se isolar um nó ou um conjunto de nós na rede com k = 2, que ficaria interrompida. Para k = 4, isolar 1 nó precisa suprimir 4 arestas, e para um conjunto de 2 ou mais nós, 6 arestas. Para k = 9, para isolar 1 nó é necessário cortar 9 arestas, para isolar 2 nós, 18 arestas, para 3 nós, 21. Fica claro que o incremento de k aumenta rapidamente a robustez da rede. Quando existem vários caminhos possíveis numa rede, perder uma ou outra conexão é indiferente, porque a rede pode contornar o problema. Portanto, ela será mais robusta. Mas nem sempre isso é verdade. Isso traz uma outra característica: algumas conexões ou nós são mais estratégicos em termos de transmissão de informações. Claro que, se todos os nós da rede tiverem o mesmo grau, isso não importa. Mas a redundância das conexões e como elas estão interligadas afetam a robustez. Em uma rede de grau três, por exemplo, conectada apenas com seus vizinhos imediatos e um vizinho seguinte, isso resultará em um determinado valor de robustez. Mas se a terceira conexão for aleatória dentro da rede, haverá outra característica de robustez.
Nos exemplos anteriores, tratamos de redes regulares, onde todos os nós possuem o mesmo grau, e a média de grau da rede é igual ao grau dos nós. Entretanto, os nós podem apresentar graus diferentes, com grande heterogeneidade, o que é inclusive mais comum. Nesse caso, temos a função de distribuição de grau P(k). Duas funções muito recorrentes são a de Poisson para redes aleatórias, e a lei de potência, que resultam em redes scale free (figura SR3).
SR3. distribuição de Poisson (azul) e lei de potencia (laranja)
(a) gráfico linear (b) gráfico log
Fonte: Oliveira et al (2022)
Nesses dois casos, se descreve um processo de formação das redes. Nos gráficos em SR3, em laranja está a probabilidade de grau para uma função de lei de potência e em azul para uma função de Poisson. O eixo x indica o grau, e o eixo y a probabilidade de ocorrência de nó com aquele grau. O gráfico SR3(a) está em escala linear, e o SR3(b) em escala logarítmica.
Para a função de Poisson, o resultado é uma concentração de nós com grau próximo da média, poucos com baixo grau e com alto grau. Esse modelo de rede aleatória é chamado de Erdös-Rényi, e foi desenvolvido pela dupla nos anos 1960.
As redes que apresentam características de scale free seguem uma função de potência com expoente negativo, do tipo P (k) ∝ k−γ . Ela é assim chamada porque para essa função, qualquer intervalo apresenta a mesma distribuição de probabilidade, o que fica evidente pela reta inclinada da escala logarítmica. Ao final dos anos 1990, estudando a internet e outros bancos de dados, Albert-László Barabási e Réka Albert identificaram que estas redes apresentavam essa característica de distribuição scale free. O modelo ficou conhecido como Barabási-Albert e descreve redes cujo crescimento se dá por conexão preferencial, que tipicamente apresentam essa distribuição scale free. Por exemplo, pesquisadores mais famosos de renome internacional tendem a ser mais citados, em outro grau de citação vêm os pesquisadores que são referências regionais e por aí vai, até chegar no aluno de iniciação científica que cita todos os demais, mas raramente é citado. Aliás, esse é justamente o tema do trabalho de Oliveira et al (2022), em que faz uma boa apresentação das características e formalizações matemáticas das principais descrições e propriedades das redes. Intitulado “Uma Visão da Ciência das Redes sobre o Instituto Nacional de Ciência e Tecnologia em Informação Quântica (INCT-IQ)”, que tem por objetivos:
Primeiramente, apresentar os principais conceitos da ciência das
redes, tais como grafos, propriedade de mundo pequeno, distribuição de
conectividade entre outros, assim como alguns dos principais modelos
de redes já propostos. O segundo objetivo é aplicar este ferramental para
analisar uma rede real, mais precisamente a rede de pesquisadores do
Instituto Nacional de Ciência e Tecnologia de Informação Quântica.
Um terceiro modelo sempre presente em todo manual sobre teoria de redes é o de Watts-Strogratz, também do final dos anos 1990. Eles partem das redes aleatórias e regulares, e uma propriedade descrita ainda nos anos 1970 por Granovetter (1983), a de small-world, mundos pequenos. O que essa propriedade descreve é aquela sensação de mundo pequeno em que todo mundo se conhece, ao se descobrir que se possui amigos em comum com um novo conhecido. O que se pensa é que dentro de 4 ou 6 contatos se chega em qualquer pessoa do planeta, o que não é muito distante da realidade.
Granovetter estudou tanto as características de mundo pequeno das redes quanto as de clusterização, isto é, a formação de grupos dentro de grupos maiores. Nem os modelos de redes regulares (a depender do grau), nem os aleatórios de Erdös-Renyi apresentavam essas características. O modelo de Watts-Strogratz (pode ser ensaiado em NetLogo aqui) consegue obter propriedades de mundo pequeno partindo de uma rede regular, e em seguida refazendo de maneira aleatória as conexões. Com um baixo número de substituições se alcança tanto propriedades de small-world quanto de clusterização (figura SR4).
SR4. tipos de rede
Os diferentes tipos de redes implicam diferentes percursos, tempos e formas de comunicação. Como algo é transmitido depende da rede em questão. É importante ressaltar que, voltando às redes aleatórias, por exemplo, não é apenas o grau que define todas as características. Quem são os seus vizinhos e quem os amigos deles também interfere. The Strenght of Weak Ties é um trabalho de Granovetter de 1973 que descreve essas questões com profundidade. Ele fala de um experimento desenvolvido por Milgram, em que cartas são entregues para pessoas de uma cidade A e solicitado que enviem para pessoas específicas na cidade B. Por não se ter o contato do destinatário, a carta precisa ser encaminhada de pessoa a pessoa até chegar ao destino. Como resultado disso, se desenvolve a idéia de comprimento dos caminhos das redes, caminhos médios, diâmetro das redes e entre outras.
Granovetter estudava basicamente redes de convívio, especialmente de estudantes de colegial. Ele percebia que havia alguns grupos no colégio totalmente conectados entre si, porém, com muito poucas pessoas em comuns em mais de um grupo. Esses grupos mais conectados são os clusters. Internamente, os clusters apresentam alto grau e a presença de cliques, que é a conexão máxima entre 3 nós, formando um triângulo. A está conectado a B, que está conectado a C, e C está conectado a A, isso forma um clique onde todos se conhecem. Formar esses triângulos não impede que eles estejam conectados a outros, e um cluster tende a surgir justamente quando se formam vários triângulos conectados.
Dentro dos clusters, a informação se propaga muito rapidamente, devido a essa forte conexão interna. A observação de Granovetter está justamente na propagação de um cluster para o outro. Eventualmente, existem pessoas que participam do cluster mas não estão muito conectadas, possuem um baixo grau, o que ele chamou de nós fracos. Boa parte dessas pessoas possui nós fracos com mais de um cluster. O que Granovetter observa é que essa transmissão de informação é feita justamente pelos nós com conexões fracas, muito pouco conectados dentro de qualquer cluster, mas justamente fazendo a ponte entre eles. Ele exemplifica que as pessoas encontram emprego mais através de um conhecido que de um amigo frequente. Quem traz uma novidade para o grupo tende a ser um sujeito menos central, e foram esses mais ou menos conhecidos os principais responsáveis para as cartas chegarem de A a B no experimento de Milgram. Os nós fracos tendem a ser os principais meios na transmissão de informação entre os grupos da rede.
Essas redes possuem uma série de características distintas que são úteis para diferentes propósitos. O tempo de transmissão, o percurso dessa transmissão, e a duração da permanência da informação na rede podem ser afetadas por essas propriedades. A estrutura da rede também pode indicar o grau de robustez ou fragilidade, por exemplo, se é possível interromper a transmissão de informação e quais conexões cortar para evitar que a informação se propague pelo resto da rede.
As redes são pervasivas, e cada contexto evidencia mais ou menos um conjunto de propriedades específicas. Um relatório com todas as propriedades pode ficar impraticável. As características que trouxemos aqui nos permitem perceber melhor a relevância das redes, de modo a desenhar nosso experimento e avaliar a distinção entre os resultados obtidos. Descrições mais precisas e ricas ficam melhor servidas com as devidas demandas, e nesse sentido Spatial Networks de Marc Barthelemy (2011) traz uma vasta coleção muito bem demonstrada matematicamente, assim como The New Sciene of Cities de Michael Batty.