Redes complexas, uma abordagem concisa

O início das pesquisas em Redes Complexas foi em 1930, nas quais eram baseadas na centralidade (o vértice mais central) e a conectividade (vértices com maior número de conexões), aquela época ainda eram utilizados indivíduos nas redes, para seguir qual tinha mais influência por exemplo.

Atualmente já sabemos que a topologia e a evolução das redes do mundo real apresentam propriedades organizacionais bastante robustas e distintas das redes aleatórias. Simplificadamente, podemos dizer que as redes complexas não seguem um padrão regular.

Uma rede é um grafo (Euler, 1736), onde cada aresta tem uma direção ou sentido que conecta um vértice de origem até um vértice de destino. Nem todo grafo pode ser considerado uma rede complexa.

Propriedades:

Coeficiente de Aglomeração: Também conhecido como Fenômeno de Transitividade, representa de forma análoga um triângulo, no qual três vértices estão ligados entre si.

Distribuição de Graus: Indica a probabilidade de um determinado vértice ter grau fixo, tal grau que é de um vértice qualquer em uma rede e o qual define o número de arestas que conectam aquele vértice.

Resistência: Capacidade quanto às remoções de alguns vértices, sem que haja perda de sua funcionalidade.

Mistura de Padrões: Capacidade de alguns tipos de redes apresentarem diferenças onde os vértices podem representar diferentes tipos de objetos.

Correlação de Graus: Indica se as arestas em uma rede associam vértices com graus parecidos.

Tipos de redes:

Redes Aleatórias: Arestas não direcionadas são adicionadas aleatoriamente entre um número fixo de N vértices.

“Quanto mais complexa a rede for, maiores as chances de a mesma ser aleatória”.

Modelo ER: É obtido conectando os vértices selecionados aleatoriamente até o número       de arestas do grafo ser igual a k.

Redes Pequeno-Mundo: É observado nas redes em que a maioria dos vértices se conecta  a outros através de um caminho mínimo (geodésico).

Redes Livres de Escalas: Uma das principais características é a conexão preferencial, que é a tendência de um novo vértice se conectar a um vértice da rede que tem um grau elevado de conexões.

Aplicações:

Avaliação da qualidade de textos: Cada palavra é um vértice e cada aresta representa uma relação de adjacência entre dois vértices.

Textos de boa qualidade = Reta.

Avaliação de sumários: (I) Eliminação de “stopwords”;

                                      (II) Lematização de palavras;

Segundo ‘Antiquira et al’, o desvio diminui na medida em que aumenta a qualidade dos   textos.

Detecção de comunidades:

Clustering: É uma técnica de “Data Mining” para fazer agrupamentos automáticos de dados segundo seu grau de semelhança.

Clustering Hierárquico - Abordagem Aglomerativa: Cada exemplo (vértice da rede) é considerado um cluster unitário;

                                 -Abordagem Divisiva: Inicia com apenas um grafo contendo todos os vértices e procede dividindo esse grafo em sub-grafos cada vez menores.

Betweenness: É uma medida (baseada em um caminho mínimo) utilizada para identificar arestas que conectam comunidades, apresentando valores altos para essas arestas e penalizando as arestas que conectam vértices de um mesmo sub-grafo.

Rede Artificial: 128 vértices divididos em 4 comunidades de tamanho uniforme.

Rede Social sobre Dados Reais: Modularidade alta.

Congestionamento em Redes:

Tráfego de pacotes – Hosts: Criam pacotes com endereço de destinatário e recebem pacotes vindos de outros hosts;

                      – Roteadores: São responsáveis por encontrar o melhor caminho entre os hosts remetente e destinatário e encaminhar

     os pacotes por este caminho ao longo do tempo.

Controle do Congestionamento de Pacotes: A quantidade de pacotes entregues por um vértice em uma iteração é definida pelo valor de sua capacidade de processamento de pacotes.

Além da fila de pacotes, cada vértice possui uma tabela de roteameto (criada através do algoritmo de Dijkstra) que contém o próximo vértice do caminho mínimo entre aquele vértice e o destino, para o qual o pacote será enviado.

O tempo de entrega de um nó depende da quantidade de vértices que tem no caminho, do tamanho da fila de pacotes e da capacidade de entrega dos vértices da rede.

Curvas de crescimento que são suavizadas sinalizam um aumento de congestionamento tardio.