Teoria das redes complexas

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas

No contexto da teoria de redes complexas, uma rede corresponde a um grafo, que se representa por um conjunto de nós ligados por arestas, que em conjunto formam uma rede. Esta rede ou grafo, permite representar relações. Muitos foram os que se dedicaram a perceber as propriedades dos vários tipos de grafos e como são constituídos, ou seja, como se agrupam os seus nós. Estes estudos são essenciais para a compreensão das relações complexas do mundo que nos rodeia, nomeadamente para as áreas da biologia, da neurociência, da linguística de associação, da psicologia, das redes sociais e das redes de comunicação, etc.

Breve história

Existem vários marcos históricos para o estudo das Redes Complexas, cujos primeiros fundamentos se baseiam na origem das Redes Complexas.

• 1736 - Leonhard Euler, matemático e físico, fundamentou a Teoria dos Grafos e a Topologia quando resolveu o problema das Pontes de Königsberg. A questão era saber se era possível atravessar as sete pontes da cidade sem passar duas vezes pela mesma ponte, o que Euler provou ser impossível, criando uma regra para aplicar a qualquer rede de pontes de qualquer cidade.
• 1847 - Gustav Robert Kirchhoff, físico russo, ao estudar circuitos eléctricos, iniciou a Teoria das Árvores.
• 1852 - Francis Guthrie, matemático inglês, criou a conjectura das 4 cores (um mapa no plano, dividido num qualquer número de regiões, pode ser colorido, de forma a que regiões fronteiras não tenham a mesma cor, com um mínimo de 4 cores), que serviu de base a conceitos importantes para a teoria dos grafos, como os polinómios cromáticos de Birhoff (1912), o grafo dual de Whitney (1931) e o teorema que limita o número cromático de um grafo, de Brooks (1941).
• 1859 - William Rowan Hamilton, matemático, físico e astrônomo, inventou um jogo cujo objetivo era percorrer uma única vez, todos os vértices de um dodecaedro regular. Este jogo inspirou o conceito de ciclo e o caminho euleriano e hamiltoniano.
• 1959 - Erdős e Rényi iniciaram o estudo dos grafos aleatórios e, através de métodos probabilísticos, estudaram as propriedades dos grafos em função do crescimento de ligações entre vértices.
• 1967 - Stanley Milgram, psicólogo, promoveu uma experiência para estudar o conceito de Mundo Pequeno, de forma a avaliar o grau de ligação entre pessoas. Através do envio de cartas, para determinados destinatários, criou o conceito de seis graus de separação entre pessoas, demonstrando que há uma probabilidade alta de que pessoas desconhecidas possuam amigos em comum.
• 1998 - Steven Strogatz e Duncan Watts, desenvolveram um algoritmo com base em grafos aleatórios, para estudarem o conceito de Mundo Pequeno.
• 1999 - Albert László Barabási e Réka Albert publicaram um artigo com a proposta de um modelo genérico de construção de redes, semelhante à estrutura encontrada em redes genéricas ou redes da Internet. Estas redes foram apelidadas de Redes livres de escala.

A partir da década de 90, do século passado, com a Internet e a informática capaz de dar resposta a grandes volumes de informação, estabeleceu-se a Teoria das Redes Complexas. Apesar das semelhanças, a Teoria das Redes Complexas difere da Teoria dos Grafos, em 3 aspetos básicos: (i) está relacionada com a modelação de redes reais, por meio da análise de dados empíricos, (ii) as redes não são estáticas, mas evoluem no tempo, alterando a sua estrutura e (iii) as redes constituem estruturas onde processos dinâmicos (como a propagação de vírus ou opiniões) podem ser simulados.

Conceitos básicos

Convém clarificar alguns termos ligados à Teoria da Redes Complexas:

• Nó ou vértice - característica local de uma rede. Pode corresponder a um documento (no contexto da Web), um computador (numa rede), um gene (em biologia), etc.
• Aresta ou ligação - a linha que une dois nós.
• Rede dirigida/não dirigida - se tem um sentido entre 2 nós ou se tem ambos. Por exemplo, na Web uma página pode conter um link para outra página e o contrário não se verificar, já na Internet, os cabos transportam informação em ambos os sentidos.
• Grau de um nó - é o número de ligações de um nó. Se a rede for dirigida, considera-se uma conectividade de entrada e uma de saída, conforme a ligação seja para o nó ou saia do nó.
• Distribuição da conectividade - forma como se distribuem as ligações pelos nós, dando-nos a probabilidade de um nó ter k ligações.
• Conectividade média - é dada pela média do número de ligações entre os nós.
• Caminho mais curto - é a menor distância entre dois nós de uma rede, dado que poderá haver mais do que um caminho a ligá-los.
• Diâmetro - é o comprimento da maior distância entre 2 nós, medidos em número de ligações.
• Matriz de adjacência - matriz que contém toda a informação sobre uma rede. Uma rede com N nós, tem uma matriz de adjacência de N*N. Numa matriz A, se dois nós i e j estão ligados, a entrada a_ij na matriz será igual a 1 e, será igual a 0, no caso contrário.
• Coeficiente de agregação ou aglomeração (clustering coefficient) - é o número de ligações entre os vizinhos mais próximos de um nó.
• Resistência - é a capacidade de resistência da rede quanto à eliminação de alguns nós, sem que haja perda da sua funcionalidade.
• Redes estáticas/dinâmicas - a rede é estática quando não há variação do número de nós e, é dinâmica, quando é possível modelar o seu crescimento pela análise da variação da sua estrutura ao longo do tempo.

Tipos de redes

As redes complexas podem ser classificadas segundo propriedades estatísticas como o grau ou o coeficiente de agregação.

Rede regular

Nas redes regulares todos os nós apresentam o mesmo grau. Na física, por exemplo, os modelos atômicos são estudados através de redes regulares.

Rede aleatória

Os estudos de Erdös e Rényi constituem uma das bases das redes complexas. Eles estudaram, do ponto de vista matemático, um sistema formado por E ligações, distribuídas aleatoriamente entre N nós. Erdös e Rényi tentaram representar a formação de redes sociais, e, para eles, bastaria uma ligação entre cada um dos convidados de uma festa, para que todos estivessem conectados no final dela. Ainda segundo Erdös e Rényi, quanto mais links eram adicionados, maior a probabilidade de serem gerados clusters, ou seja, grupos de nós mais coesos. Uma festa, portanto, poderia ser um conjunto de clusters (grupos de pessoas) que de tempos em tempos estabeleciam relações com outros grupos (rede). O processo de formação da rede é aleatório: os nós interligam-se aleatoriamente. Neste modelo, todos os nós têm mais ou menos a mesma quantidade de ligações, ou a mesma probabilidade de receber novas ligações. Assim, a distribuição de conectividade obedece a uma distribuição de Poisson.

Rede livre de escala

Barabási demonstrou que as redes não são formadas de modo aleatório, existindo uma ordem na dinâmica de estruturação das redes: rich get richer, ou seja, quanto mais ligações um nó apresenta, mais hipóteses tem de criar novas ligações. A esta característica Barabási e Albert deram o nome de preferential attachment: um novo nó tende a ligar-se a um nó preexistente, que contém mais ligações. Isto implica que as redes não são constituídas por nós com iguais probabilidades de terem o mesmo número de ligações, havendo sim, um conjunto pequeno de nós altamente conectados e uma maioria de nós com poucas ligações. Para além da ligação preferencial de um nó a nós com mais conexões, também a rede no seu todo está em constante crescimento, evolução e adaptação. Em cada novo passo é criado um nó no qual têm origem outras ligações, existindo como que uma dinâmica de imitação, como se alguns nós atraíssem outros. O modelo apresentado por Barabási e Albert mostra que este tipo de rede tem um grau de conectividade muito baixo, porque apenas alguns nós se encontram muito conectados, apresentando a maioria poucas ligações.

Rede Pequeno mundo

O modelo de rede foi proposto por Watts e Strogatz para explicar o efeito de mundo pequeno subjacente à experiência de Milgram. Consiste em modificar as ligações de uma rede regular com uma probabilidade p. Quando p=0, nada se altera e mantém-se uma topologia regular. Quando p=1, todas as ligações são alteradas (ou seja, modificam-se os seus nós de extremidade) e a rede torna-se aleatória. Para os valores de p contidos entre 0 e 1, sobretudo para valores muito pequenos, a rede assume a topologia de mundo pequeno.

O modelo apresenta as principais características apresentadas no estudo de Milgram, já que possui uma alta comunicabilidade entre pessoas distantes, graças às pouca ligações aleatórias e mantém um grau de regularidade, que representa os núcleos locais de amizade, indicando que as pessoas estariam a poucos graus de separação umas das outras, ou seja, num "mundo pequeno". Mark Granovetter desenvolveu a noção de laços fracos (weak ties), que seriam muito mais importantes na manutenção da rede social, do que os laços fortes (strong ties), para os quais habitualmente os sociólogos dão mais importância. Granovetter mostrou que as pessoas que partilhavam laços fortes (de amigos próximos, por exemplo) em geral participavam num mesmo círculo social (de um mesmo grupo que seria altamente clusterizado). Já aquelas pessoas com quem tinham um laço mais fraco eram igualmente importantes porque conectariam vários grupos sociais e, que sem elas, os vários clusters existiriam como ilhas isoladas e não como uma rede.

A partir destes estudos, Watts e Strogatz, descobrem que a distância média entre quaisquer dois nós de uma rede muito grande não ultrapassa um pequeno número de nós. Para isso, basta que algumas ligações aleatórias entre grupos sejam estabelecidas. Em larga escala, as ligações aleatórias mostram a existência de poucos graus de separação entre as pessoas no planeta, bastando poucas ligações entre vários clusters para tornar um mundo pequeno numa grande rede, transformando a própria rede num grande cluster. É a partir desta noção que se consegue difundir vírus e informação, como boatos, em larga escala.

Rede hierárquicas e modular

Numa rede hierárquica, a relação de lei de potência entre o coeficiente de agregação de um nó e o seu grau, são a característica mais importante. A arquitetura hierárquica implica que nós distantes são partes de áreas de alta agregação e que a comunicação entre estas áreas (também chamadas módulos) é feita por um pequeno número de nós.

Redes Funcionais

Ver Redes Funcionais. Estas são redes formadas na evolução das espécies, como forma de "ganhar" vantagens. Em teoria, estas redes representam como genes comunicam.