Terceiro exercício prático: Falhas e ataques
Você vai reproduzir o resultado de um trabalho da equipe de Barabási sobre uma característica importante de redes com distribuição de graus em lei de potência.
O grupo descobriu que uma rede desse tipo é robusta com relação a falhas mas frágil com relação a ataques.
Neste contexto, uma falha é entendida como a retirada da rede de um vértice escolhido aleatoriamente. Já um ataque a retirada de um vértice escolhido de forma a tentar maximizar o dano causado na rede.
A retirada de vértices causa uma degradação da rede, que precisa ser quantificada de alguma forma.
Neste trabalho, os ataques serão direcionados por grau (escolhe-se o vértice, ou um dos vértices, com o maior grau). A verificação da funcionalidade da rede será feita pela fração de vértices que permanecem no maior componente da rede depois da falha ou ataque.
Você deve simular falhas e ataques tanto em redes Barabási-Albert (distribuição de lei de potência) quanto em redes Erdös-Rényi (distribuição de Poisson) e comparar os resultados tanto para falhas como para ataques.
O procedimento é o seguinte:
- Começamos com uma rede gerada pelo modelo.
- Calculamos o número de vértices no maior componente conectado.
- Escolhemos um vértice e o retiramos da rede, junto com todas as suas arestas.
- Repetimos os passos 2 a 3, guardando o valor da fração dos vértices iniciais que restam no maior componente em cada passo.
No passo 2, se estivermos simulando falhas, escolhemos aleatoriamente um dos vértices ainda presentes na rede; se estivermos simulando ataques, escolhemos um dos vértices com o maior grau.
Sugestões de parâmetros:
- Tente fazer com redes com 1000 vértices iniciais. Se estiver muito demorado no seu computador, você pode diminuir o número de vértices.
- Use grau médio 10 (ajuste os parâmetros dos grafos para atingir esse grau médio). Ao comparar as redes Barabási-Albert e Erdös-Rényi, é importante que a comparação seja com o mesmo número de vértices e grau médio inicial.
- Como o processo é estocástico, você precisa fazer várias simulações e calcular médias e desvio padrão. De acordo com os tempos de execução no seu computador, tente rodar um número grande de repetições, mas não menos do que 20.
- Você pode parar o processo de falha ou ataque quando tiver retirado 50% dos vértices inciais. Nesse ponto, já é possível comparar os resultados.
Você precisa realizar dois tipos de comparação:
- Comparar falha com ataque para cada um dos modelos de rede.
- Tanto para falha como para ataque, comparar os dois modelos de rede.
Entregue um notebook Jupyter com o código, os resultados e a discussão dos resultados.