Upload
trinhquynh
View
216
Download
0
Embed Size (px)
Citation preview
Departamento de Física
VULNERABILIDADE DE REDES COMPLEXAS
Alunos: Antonio Rossano e João Pedro Mano
Orientador: Celia Anteneodo
Introdução
Dado um conjunto de elementos discretos interagentes (por exemplo, indivíduos,
proteínas, computadores ou aeroportos), as informações detalhadas sobre quais elementos
interagem entre si e com qual intensidade podem ser resumidas num grafo ou rede. Cada
vértice de um grafo corresponde a cada elemento individual do sistema em estudo. As
ligações, entretanto, dependem da característica que se quer estudar. Por exemplo, indivíduos
podem estar ligados por conexões de amizade ou devido ao compartilhamento de alguma
opinião. Aeroportos poderão estar ligados se possuem alguma rota (vôo) que os conectam.
Neste caso, dado uma mesma malha aérea podem surgir diferentes redes, segundo sejam
consideradas rotas de transporte de passageiros ou de carga, direcionadas ou não, com pesos
ou não (que podem ser atribuídos segundo número de assentos disponíveis, número efetivo de
passageiros, capacidade de carga ou distância percorrida, dentre outras possibilidades).
Assim, as redes constituem a base para descrever e modelar uma grande variedade de
sistemas naturais e artificiais. O seu amplo campo de aplicabilidade tem motivado o estudo
das redes complexas por pesquisadores de diversas áreas, como físicos, matemáticos,
biólogos, engenheiros e sociólogos. O seu estudo fundamenta-se em conceitos da teoria de
grafos e da física estatística.
As redes podem ser caracterizadas por diversas grandezas estatísticas relativas
principalmente a sua topologia, a exemplo do grau ou conectividade média k e do mínimo
caminho médio l. O primeiro diz respeito ao número médio de primeiros vizinhos, o segundo
do comprimento mínimo entre dois vértices quaisquer. Por exemplo, em redes sociais a
distância média típica entre dois indivíduos é pequena (entre 5 e 6). Esta é a propriedade
conhecida como "mundo pequeno" [1].
(a) (b) (c)
Fig. 1 Exemplos de redes, desde completamente regular (a) até completamente aleatória (c).
Extraído de [1].
As redes podem ser completamente regulares como a mostrada na Fig. 1(a) ou
completamente aleatórias, como na Fig. 1(c). Dentre esses dois casos extremos, encontram-se
as redes ditas complexas que ocorrem em muitas redes naturais e sociais [2]. Elas apresentam
padrões estatísticos peculiares, a exemplo da propriedade de "mundo pequeno" (Fig. 1(b))
e/ou de características "livres de escala", ou seja, com distribuição de graus seguindo uma lei
de potência.
Departamento de Física
Outra propriedade que permite caracterizar uma rede, e que será focada neste trabalho,
é a sua vulnerabilidade a ataques. Com a remoção de partes estruturais da rede, a mesma sofre
um determinado impacto em sua eficiência, o qual permite medir a vulnerabilidade da rede.
Esta medida é relevante em muitas redes reais, como as de transporte (seja de passageiros,
carga ou correspondência) e outras redes de comunicação como a WWW. Sua relevância
reside tanto na antecipação de danos quanto na possibilidade da sua prevenção mediante
modificações para tornar a rede mais robusta.
Objetivos
Estudar as propriedades estruturais de redes complexas e aplicar estes conceitos para
caracterizar redes reais tais como as de tráfego aéreo de passageiros. Principalmente estudar a
vulnerabilidade de redes aéreas a ataques a aeroportos e/ou a trajetos entre aeroportos.
Metodologia
I. Obtenção de dados e confecção de redes reais
Grandes malhas aéreas já têm sido estudadas na literatura [3-5]. No presente trabalho
escolhemos malhas aéreas moderadamente pequenas, com o mesmo número de cidades
atendidas, porém com mercados diferentes, para efetuar estudos comparativos. Escolhemos as
malhas aéreas das companhias Gol e Air France (apenas a malha Européia). Os dados foram
obtidos a partir da WWW, diretamente dos sites das empresas (www.voegol.com.br e
www.airfrance.fr), em 2009.
As Figuras 2 e 3 ilustram as respectivas redes. Os vértices correspondem a aeroportos
(indicados nas Tabelas I e II) e as ligações indicam a existência de vôos entre aeroportos.
Ainda, as ligações podem ser caracterizadas por pesos, correspondendo, por exemplo, ao
número de vôos em cada ligação.
Fig. 2: Rede da Companhia Aérea Gol
Departamento de Física
1 - AJU 12 - XAP 23 - JPA 34 - NVT 45 - ROS
2 - ASU 13 - COR 24 - JOI 35 - PMW 46 - SSA
3 - BEL 14 - CZS 25 - JDO 36 - PNZ 47 - STM
4 - CNF 15 - CGB 26 - LDB 37 - POA 48 - SCL
5 - BVB 16 - CWB 27 - MCP 38 - BPS 49 - SLZ
6 - BSB 17 - FLN 28 - MCZ 39 - PVH 50 - CGH
7 - EZE 18 - FOR 29 - MAO 40 - PPB 51 - GRU
8 - CPV 19 - IGU 30 - MAB 41 - REC 52 - VVI
9 - CPQ 20 - GYN 31 - MGF 42 - RBR 53 - THE
10 - CGR 21 - IOS 32 - MVD 43 - GIG 54 - UDI
11 - CXJ 22 - IMP 33 - NAT 44 - SDU 55 - VIX
Tabela I: Aeroportos da rede da Gol
Fig. 3: Rede da Companhia Aérea Air France (malha Européia)
Departamento de Física
1 - Ajaccio 12 - Le Havre 23 - Nice 34 - Argel 45 – Lisboa
2 – Annecy 13 - Lille 24 - Paris 35 - Amsterdam 46 – Londres
3 – Bastia 14 - Limoges 25 - Pau 36 - Barcelona 47 – Madrid
4 – Biarritz 15 - Lorient 26 - Perpignan 37 - Birmingham 48 – Milão
5 – Bordeaux 16 - Lourdes/Tarbes 27 - Quimper 38 - Bolonha 49 – Monique
6 – Brest 17 - Lyon 28 - Rennes 39 - Bruxelas 50 – Praga
7 – Caen 18 - Marseille 29 - Rodez 40 - Copenhague 51 – Roma
8 - Calvi 19 - Metz-Nancy 30 - Rouen 41 - Dusseldorf 52 – Stuttgart
9 - Clermont-Ferrand 20 - Montpellier 31 - Strasbourg 42 - Florença 53 – Tunis
10 - Figari 21 - Mulhouse 32 - Toulon 43 - Genebra 54 – Veneza
11 – Lannion 22 - Nantes 33 - Toulouse 44 - Hambourg 55 – Viena
Tabela II: Aeroportos da rede da Air France
II. Medidas de análise das redes
As redes estudadas foram caracterizadas por diversas medidas, tanto medidas
relacionadas à conectividade da rede (força dos vértices, coeficiente de assortatividade),
medidas relacionadas a ciclos (coeficiente de aglomeração), quanto medidas relacionadas a
distâncias (caminho médio, eficiência), segundo as definições a seguir [6].
Como primeiro passo, uma rede ou grafo pode ser representada por uma matriz de
adjacências a, cujos elementos aij assumem o valor 1 caso o vértice i tenha uma conexão
direta com o vértice j, e 0, caso contrário. Já numa matriz de peso w, os elementos assumem o
valor do peso da aresta que conecta os vértices i e j. Se o grafo é direcionado as matrizes
podem ser assimétricas. Uma medida do grau de simetria é dado pelo coeficiente de
reciprocidade
,
2
,
( )( )
( )
ij ji
i j i
ij
i j i
a a a a
Ra a
onde ,
/[ ( 1)]ij
i j i
a a N N
. Dado que nos casos aqui analisados as matrizes são simétricas,
definiremos as grandezas estudadas a seguir, apropriadas para o caso simétrico.
Conectividade:
1
N
i ij
j
k a
Essa medida avalia a conectividade de cada vértice, baseado no número de conexões de
cada vértice pertencente à rede. Através desta medida é possível encontrar os chamados
“hubs” (do inglês, concentradores), ou seja, vértices com uma conectividade bem maior do
que a maioria dos demais vértices. Também interessa o seu valor médio dado por
1
1 N
i
i
k kN
que representa uma característica global da rede.
Departamento de Física
Força:
1
N
i ij
j
s w
Essa medida avalia a força dos vértices, baseado nos pesos das conexões de cada
vértice. O seu valor médio é dado por
1
1 N
i
i
s sN
Coeficiente de Assortatividade:
ij ij
ijjiijji
ij ij
ijjiijji
akkM
akkM
akkM
akkM
r2
22
2
2
11
2
11
2
111
Mede a tendência dos vértices de conectividades semelhantes estabelecerem ligações
entre si. Caso o coeficiente de assortatividade seja maior do que 0, a rede é dita assortativa, ou
seja, os vértices de conectividades semelhantes tendem a se ligar. Caso seja menor do que 0, é
dita dissassortativa e os vértices com mais conexões tendem a se ligar com os de menos
conexões. Se for igual a zero, não há correlação.
Coeficiente de aglomeração:
1
1 1
ii
N
j
N
m
mijmij
ikk
aaa
cc
jmimij
mj
imij
ii
w
i aaaww
kscc
21
1
Os coeficientes de aglomeração medem o nível de aglomeração de cada vértice de uma
rede complexa. Dependendo das características da rede que está sendo estudada, pode ser
medido de duas formas diferentes, a primeira medida mostrada acima, mede o grau de
aglomeração sem pesos nas ligações, já a segunda numa rede com pesos nas ligações entre os
vértices. Como nos casos anteriores, os coeficientes da rede como um todo, são obtidos
calculando os respectivos valores médios cc e ccw. Em redes sociais este coeficiente assume
valores intermediários entre o característico das redes aleatórias (baixa aglomeração) e o das
regulares (alta aglomeração) [1].
Caminho médio: O caminho médio de uma rede complexa é dado pela média entre as
distâncias mínimas entre todos os vértices, segundo a expressão abaixo:
ji
ijdNN
l1
1
Esta grandeza permite caracterizar, por exemplo, a propriedade de mundo pequeno.
As distâncias mínimas podem ser determinadas pelo algoritmo de Dijkstra: este
algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A
Departamento de Física
cada passo do algoritmo, busca-se nas adjacências dos vértices pertencentes a S aquele vértice
com menor distância relativa a I e adiciona-o a S e então repetindo os passos até que todos os
vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são
desconsideradas.
Eficiência Global: A eficiência de uma rede é medida através da média do inverso das
distâncias entre todos os vértices. Quanto menor a distância percorrida entre os vértices da
rede, maior a sua eficiência.
ji ijdNNE
1
1
1
Vulnerabilidade da Rede: A vulnerabilidade de uma rede é medida através da análise do
impacto sofrido pela mesma frente a ataques em sua estrutura. Ao remover um vértice ou uma
aresta da rede, a mesma sofre um determinado dano em sua eficiência global. A
vulnerabilidade pode ser medida segundo: *
* E EV
E
Onde E* é a eficiência da rede modificada, por exemplo, pela remoção de um vértice.
A vulnerabilidade global da rede é definida como o valor máximo V= max(V*).
III. Resultados
As tabelas III-VI apresentam os valores das conectividades (número de
vizinhos ou conexões) e forças (número de vôos em um sentido) de cada vértice das malhas
aéreas da Gol (tabelas III e V) e da Air France (tabelas IV e IV).
1 3 15 7 29 7 43 21
2 2 16 13 30 2 44 4
3 9 17 7 31 2 45 2
4 14 18 10 32 1 46 11
5 1 19 3 33 5 47 2
6 27 20 6 34 1 48 1
7 6 21 3 35 1 49 4
8 2 22 2 36 1 50 20
9 4 23 4 37 10 51 21
10 6 24 1 38 4 52 1
11 1 25 2 39 4 53 2
12 1 26 2 40 2 54 2
13 1 27 1 41 10 55 5
14 1 28 4 42 3
Tabela III: Conectividade dos vértices da rede da Gol
Departamento de Física
1 24 15 67 29 90 43 442
2 14 16 271 30 14 44 277
3 103 17 112 31 20 45 24
4 307 18 139 32 14 46 214
5 7 19 34 33 42 47 26
6 563 20 96 34 19 48 7
7 79 21 29 35 13 49 41
8 21 22 14 36 14 50 693
9 81 23 20 37 206 51 451
10 47 24 18 38 21 52 8
11 12 25 14 39 35 53 21
12 13 26 19 40 19 54 19
13 5 27 17 41 195 55 98
14 7 28 41 42 21
Tabela IV: Força dos vértices (número de vôos) da rede da Gol
1 4 15 2 29 1 43 2
2 1 16 1 30 1 44 1
3 4 17 29 31 12 45 2
4 2 18 18 32 1 46 2
5 12 19 2 33 12 47 1
6 3 20 3 34 2 48 3
7 2 21 2 35 8 49 2
8 3 22 13 36 2 50 4
9 9 23 18 37 1 51 5
10 3 24 49 38 1 52 2
11 1 25 2 39 1 53 4
12 1 26 1 40 2 54 2
13 8 27 1 41 1 55 2
14 2 28 6 42 1
Tabela V: Conectividade dos vértices da rede da Air France
Departamento de Física
1 10 15 7 29 3 43 10
2 4 16 3 30 1 44 4
3 10 17 101 31 47 45 5
4 9 18 66 32 6 46 15
5 48 19 4 33 64 47 12
6 12 20 18 34 5 48 14
7 5 21 13 35 27 49 9
8 3 22 39 36 12 50 12
9 23 23 58 37 6 51 18
10 4 24 380 38 5 52 8
11 3 25 13 39 3 53 8
12 2 26 4 40 6 54 9
13 22 27 4 41 6 55 10
14 7 28 14 42 6
Tabela VI: Força dos vértices (número de vôos) da rede da Air France
As figuras 4 e 5 mostram os gráficos de força (número de vôos) x conectividade
(número de vizinhos) para cada vértice (aeroporto) das respectivas malhas da Gol e da Air
France. Podemos observar que, a pesar da tendência de que aeroportos com mais conexões
possuem mais vôos, a relação não é linear.
No caso da Gol, quebram a linearidade principalmente os aeroportos de Congonhas
(50) e Santos Dumont (44) com maior número de vôos em proporção ao número de conexões
em comparação com os outros aeroportos servidos pela companhia.
No caso da Air France, a exceção é o aeroporto de Paris com aproximadamente três
vezes mais vôos em relação à tendência quase linear seguida pelos outros aeroportos da malha
européia.
Fig. 4: Força x conectividade para cada vértice da Gol
Departamento de Física
Fig. 5: Força x conectividade para cada vértice da Air France
Na Figura 6 são apresentadas as distribuições de graus das duas companhias. Podemos
observar que não possuem a propriedade livre de escala, dado que as distribuições não
seguem uma lei de potência, e sim uma lei tipo exponencial esticada [3].
k1 10 100
P(k
)
10-3
10-2
10-1
100
GOL
Air France
10 20 30 40 50
0.01
0.1
1
Fig. 6: Distribuição acumulada de graus da Gol e da Air France. O gráfico inserido mostra os mesmos
dados em escala log-linear.
O número de vôos entre aeroportos (dados não exibidos por limitações de espaço)
permitem definir tanto a matriz de adjacências a (sendo aij=1 se existem vôos entre i e j, 0 em
caso contrário) quanto a dos pesos w (sendo no presente trabalho wij=número de vôos de i
para j).
Departamento de Física
A Tabela VII resume os valores das grandezas definidas na secção I que caracterizam
globalmente as redes estudadas. Para fins comparativos, a tabela inclui também resultados da
rede nacional (obtidos da referência [3]) e da rede mundial (das referências [4,5]).
Tanto a malha aérea da Gol quanto a malha da Air France possuem 55 cidades (vértices)
e suas conectividades médias, isto é, a quantidade de vértices vizinhos que cada cidade possui
é de 5,309 e 5,073 vizinhos respectivamente. A força de cada aresta, ou seja, a quantidade de
vôos que cada cidade tem, por média, é de 94,872 e 22,110 vôos respectivamente.
Medidas Gol Air France RBA(1)
[3] WAN(2)
Número de vértices da rede N 55 55 142 3880 [4]
Reciprocidade R da matriz a 1 1 0,869
Conectividade média dos vértices k 5,309 5,073 10,28 9,70 [4]
Força média dos vértices s 94,872 22,110
Assortatividade r -0,297 -0,505
Coeficiente de aglomeração cc 0,469 0,605 0,63 0,62 [5]
Coeficiente de aglomeração ccw 0,495 0,616
Caminho médio l 2,458 1,894 2,34 4,37 [6]
Eficiência E 46,3% 51,9%
Tabela VII: Resultados obtidos para as malhas aéreas da Gol e da Air France
(1) RBA=Rede Brasileira de Aeroportos, dados referentes ao ano de 2006 [3].
(2) WAN=Rede Mundial de Aeroportos (World Airport Network), dados referentes a 2002 [4] e 2000 [5].
A partir da matriz de adjacências foi possível calcular o coeficiente de assortatividade
das redes e os valores obtidos foram -0,297 para a Gol e -0,505 para a Air France. Por ambos
os valores serem negativos, nos indica que as duas redes são dissassortativas (sendo a Gol
menos dissortativa). Esta característica é típica deste tipo de redes de transporte, os vértices
com mais conexões tendem a se ligar com os de menos conexões e é exatamente isso que
podemos observar. No caso da Gol, a maioria das cidades tendem a se ligar com Brasília e
Guarulhos (São Paulo), já no caso da Air France as cidades tendem a se ligar com Paris.
Entretanto, aeroportos pequenos não têm conexões diretas entre si, especialmente no segundo
caso.
Também foram calculados os coeficientes de aglomeração da rede, baseados tanto na
conectividade quanto na força de cada vértice. Os valores encontrados para a rede da Gol
foram cc = 0,469 e ccw= 0,495 e para a rede da Air France, cc = 0,605 e cc
w= 0,616, valores
dentro do esperado, pois em redes de comunicação esse coeficiente assume valores
intermediários. Nota-se que os coeficientes de aglomeração da Gol são menores que os da Air
France e inclusive que os da rede nacional brasileira, são próximos dos da Air France.
Outra medida calculada foi o caminho médio da rede, ou seja, a distância (em arestas)
média entre dois vértices. Para a Gol, o caminho médio é de 2,458 arestas e para a Air France
é de 1,894 aresta. Isto mostra que ambas as redes possuem a propriedade de "mundo pequeno"
típica das redes de comunicação.
A partir do inverso da distância de todos os vértices, é possível calcular a eficiência da
rede que no caso da Gol é de 46,3% e da Air France é de 51,9%. Quanto menor for a caminho
médio de uma rede, maior é a sua eficiência.
Foi estudado o comportamento de cada rede frente a ataques pontuais, isto é, o impacto
(vulnerabilidade) que ela sofre em sua eficiência quando um dos vértices é retirado. As
tabelas VIII e IX apresentam o impacto da retirada de cada um dos aeroportos de cada malha.
Departamento de Física
Observamos que os hubs tendem a ser, geralmente, os vértices cuja remoção é capaz de
mais danificar a rede. No caso da Gol o maior impacto na rede (14,9%) é com a remoção do
aeroporto de Congonhas (São Paulo), com 693 vôos, já no caso da Air France o maior
impacto da rede (48,4%) é com a remoção do aeroporto de Paris, com 380 vôos.
1 3,46 % 15 4,10 % 29 4,32 % 43 5,83 %
2 3,02 % 16 5,18 % 30 6,48 % 44 3,89 %
3 6,69 % 17 6,69 % 31 3,24 % 45 3,02 %
4 5,18 % 18 4,32 % 32 2,81 % 46 4,54 %
5 2,59 % 19 3,46 % 33 3,67 % 47 2,81 %
6 14,5 % 20 4,10 % 34 3,02 % 48 2,38 %
7 6,05 % 21 3,46 % 35 3,24 % 49 3,67 %
8 3,46 % 22 3,46 % 36 2,59 % 50 14,9 %
9 3,89 % 23 3,67 % 37 9,93 % 51 5,83 %
10 6,48 % 24 3,02 % 38 3,46 % 52 2,59 %
11 3,02 % 25 2,81 % 39 3,67 % 53 3,46 %
12 2,81 % 26 3,24 % 40 3,24 % 54 3,24 %
13 2,81 % 27 2,59 % 41 6,91 % 55 3,89 %
14 2,38 % 28 3,46 % 42 5,83 %
Tabela VIII: Vulnerabilidade na eficiência da rede Gol
1 3,66 % 15 3,47 % 29 3,28 % 43 3,47 %
2 3,27 % 16 3,28 % 30 2,89 % 44 3,28 %
3 3,66 % 17 11,4 % 31 4,05 % 45 3,47 %
4 3,47 % 18 4,43 % 32 3,28 % 46 3,47 %
5 4,24 % 19 3,08 % 33 4,05 % 47 3,28 %
6 3,47 % 20 3,47 % 34 3,47 % 48 3,47 %
7 3,47 % 21 3,47 % 35 3,85 % 49 3,47 %
8 3,47 % 22 4,24 % 36 3,47 % 50 3,66 %
9 3,85 % 23 4,62 % 37 3,28 % 51 3,66 %
10 3,47 % 24 48,4 % 38 3,28 % 52 3,47 %
11 3,27 % 25 3,47 % 39 2,89 % 53 3,47 %
12 2,89 % 26 3,28 % 40 3,47 % 54 3,47 %
13 3,47 % 27 3,28 % 41 3,28 % 55 3,47 %
14 3,47 % 28 3,66 % 42 3,28 %
Tabela IX: Vulnerabilidade na eficiência da rede Air France
Analisamos possíveis correlações entre a vulnerabilidade e diversas grandezas como a
conectividade, a forca e o coeficiente de aglomeração do vértice removido.
Com a análise das figuras 7-9, é possivel perceber que o impacto na rede pela remoção
de um vértice na malha aérea da Gol não possui uma conecção e/ou dependência direta com
sua conectividade ou com a quantidade de vôos que o aeroporto retirado possui ou mesmo
com o coeficiente de aglomeração do vértice. Com a remoção dos hubs da rede, obtemos os
maiores impactos, como era de se esperar, porém, de uma maneira geral, com a remoção de
um vértice, mesmo sem alta conectividade ou força, mas que conecta dois hubs, haverá um
grande impacto na rede, pois assim aumentará o caminho médio da rede e,
consequentemente, diminuirá a eficiência da mesma.
Departamento de Física
Já nas figuras 10-12, percebemos que na malha aérea da Air France, o impacto na rede
pela remoção de um vértice está nitidamente com as grandezas consideradas. O impacto
cresce com a conectividade e com a força do vértice. Isto pode ser explicado pois os
aeroportos com baixa conectividade e/ou força têm poucos vizinhos, assim, com a sua
remoção não aumenta consideravelmente o caminho médio da rede. Entretanto o impacto
decresce com o coeficiente de aglomeração (quando não nulo), isto pode ser explicado porque
para um vértice com alta aglomeração existem conexões alternativas que compensam a
remoção do vértice.
Fig. 7: Vulnerabilidade x conectividade do vértice removido, para a Gol
Fig. 8: Vulnerabilidade x força (número de vôos) do vértice removido, para a Gol
Departamento de Física
Fig. 9: Vulnerabilidade x coeficiente de aglomeração, para a Gol
Fig. 10: Vulnerabilidade x conectividade do vértice removido, para a Air France
Departamento de Física
Fig. 11: Vulnerabilidade força do vértice removido (número de vôos), para a Air France
Fig. 12: Vulnerabilidade x coeficiente de aglomeração, para a Air France
Na tabela IX observamos que, com exceção dos aeroportos de Paris (24) e Lyon (17),
com vulnerabilidades de 48,4 e 11,4% respectivamente, os restantes aeroportos da malha da
Air France apresentam baixos valores do coeficiente de vulnerabilidade: concentrados entre
2,89 e 4,62%. Estas características podem ser observadas também nas Figs. 10-12.
No caso da Gol, na tabela VIII, e também nas Figs. 7-9, observamos que com exceção
dos aeroportos de Congonhas (50), Brasilia (6) e Porto Alegre (37) que apresentam
vulnerabilidades de 14,9, 14,5 e 9,93% respectivamente, os restantes aeroportos possuem
valores entre 2,38 e 6,91%, ou seja com uma dispersão maior que no caso da Air France.
Departamento de Física
Também a partir dos resultados apresentados na tabela VII podemos concluir que a
estrutura da malha da Gol é em algum sentido mais homogênea, de acordo com a menor
dissortatividade (assortatividade r menos negativa).
Assim, a rede da Air France possui principalmente um ponto (hub) muito vulnerável
(segundo medido pela diferença relativa de eficiências) frente ao fechamento do aeroporto
(com impacto de 50%), entretanto a estrutura menos centralizada da malha da Gol faz com
que, apesar da maior dispersão dos valores de vulnerabilidade, seja como um todo mais
robusta frente a esse tipo de danos (o impacto causado não superando o 15%).
Conclusões
As propriedades comumente consideradas para analisar redes complexas foram aqui
utilizadas para caracterizar quantitativamente redes reais de companhias aéreas como a GOL e
a Air France.
Este estudo permitiu uma análise comparativa de duas redes relativamente pequenas e
de tamanhos semelhantes associadas a companhias de dois diferentes mercados. Observamos
que apresentam a propriedade de mundo pequeno, porém não são livres de escala. As
propriedades das pequenas malhas consideradas foram também comparadas com as de
grandes redes como a nacional brasileira e a mundial, mostrando que mesmo malhas pequenas
preservam as principais características e tendências das grandes redes.
Em particular foi caracterizado o grau de vulnerabilidade de cada rede frente à remoção
de vértices (fechamento de aeroportos), baseado na medida de eficiência definida na seção II.
Observamos a maior robustez da malha da Gol em termos globais, porém com exceção de
alguns hubs a grande maioria dos aeroportos da Air France apresenta valores menores de
vulnerabilidade.
O estudo da vulnerabilidade de uma rede é importante para a antecipação de danos e
conseqüentemente a prevenção dos mesmos. Os resultados deste tipo de estudo pode também
guiar a reestruturação uma rede para torná-la menos susceptível a ataques ou acidentes.
Os programas computacionais desenvolvidos neste trabalho para estudar as
propriedades estruturais e o impacto da remoção de partes da rede poderão ser aplicados ao
estudo futuro de outras redes reais.
Referências
1 - WATTS. D. J.. STROGATZ S. H.. Collective dynamics of small world networks. Nature.
393. 440–442. 1998.
2 - BARABASI. A.-L.. ALBERT R. Emergence of scaling in random networks. Science.
v.286. 509-512. oct. 1999.
3 - ROCHA. Luis. Structural evolution of the Brazilian airport network. J. Stat. Mech.. v.04.
P04020. 2009.
4 - GUIMERA R.; AMARAL. L.A.N. Modeling the world-wide airport network. Eur. Phys.
J. B. v.38. 381-385. 2004.
5 - BARRAT A, BARTHELEMY M, PASTOR-SATORRAS R, VESPIGNANI A The
architecture of complex weighted networks. PNAS v.101. n 11 3949-3752. 2004.
6 - RODRIGUES. F.A. Caracterização, classificação e análise de redes complexas. Tese de
doutorado - Instituto de Física de São Carlos (USP). 2007.