Tópicos Avançados em Inteligência Artificial - 2011.2
Centro de Informática - UFPE
Redes de Transporte Aéreo
João Victor Wanderley Ramos
Rafael Barbosa Gonçalves
{jvwr, rbg2} @ cin.ufpe.br
Roteiro
• Motivação
• Dados utilizados
• A Estrutura de Larga Escala
• Estrutura de Comunidades
• Papel Global das Cidades
• Conclusão
• Referências
Motivação
• A rede de transporte aéreo tem um grande
impacto nas economias locais, nacionais e
internacionais
• Responsável pela mobilidade de milhões de
pessoas e toneladas de carga todos os dias.
• Indiretamente responsável pela propagação de
doenças contagiosas, principalmente as
relacionadas com sistema respiratório.
Motivação
• Alguns fatores podem resultar em atrasos e
cancelamentos de vôos
• Falhas e ineficiências do sistema de transporte
aéreo têm grandes custos econômicos
- atrasos nos vôos resultaram em custo para os países
europeus de mais 150 bilhões de euros no ano de 1999
Motivação
• O que levou o sistema a esse ponto?
• Por que não podemos conceber um sistema
melhor?
• Para responder a estas perguntas, é fundamental
caracterizar a estrutura da rede mundial de
transporte aéreo e os mecanismos
responsáveis pela sua evolução
• Solução não é simples:
- Companhias aéreas visam lucros;
- Fatores geográficos, políticos e econômicos.
Dados Utilizados
• 3.883 localidades
• Cada localidade possui pelo menos um aeroporto
e está conectada a uma outra localidade por um
voo direto (sem escalas)
• Base de dados oriunda da OAG:
o Mais de 800 linhas aéreas do mundo
o Período de 01/11/2000 a 7/11/2000
o Apenas voos de passageiros agendados (regulares)
Dados Utilizados
• No período considerado, a rede apresentou
o 531.574 voos ou segmentos de voos
o 27.051 pares distintos de cidades com conexões sem
escalas
• Alta redundância acrescenta mais confiança e
credibilidade à análise.
Dados Utilizados
A Estrutura de Larga Escala
• Propriedade de “Mundo Pequeno”
• Média dos menores caminhos d = 4,4
• 56% dos pares são conectados por 4 vôos ou
menos
• d cresce com o número total de cidades (S) em
proporção logarítmica (d log S)
A Estrutura de Larga Escala
• Exemplo:
-
Cidades mais “afastadas” do mundo: Mount Pleasant
(Ilhas Malvinas) e Wasu (Nova Guiné)
A Estrutura de Larga Escala
• Coeficiente de clusterização (C):
- Probabilidade de duas cidades diretamente conectadas
serem ambas diretamente conectadas a uma terceira
• Coeficiente aumenta com o crescimento da rede
• Resultado condizente com a expectativa de
mundo pequeno (C = 0,62)
A Estrutura de Larga Escala
• Grau de Distribuição
o Número de outras cidades conectadas por vôos diretos
• Rede sem escala
o A rede possui alguns nós que são muito mais conectados
do que os demais
o Distribuição decai semelhante à lei de potência
o Nós com alto grau de conectividade tendem a receber
mais conexões
A Estrutura de Larga Escala
A Estrutura de Larga Escala
• Centralidade (Bi)
o Número de caminhos curtos conectando quaisquer duas
outras cidades que envolvam a cidade i
• Centralidade normalizada (bi)
o <B> representa a média das centralidades da rede
A Estrutura de Larga Escala
A Estrutura de Larga Escala
• As cidades mais conectadas também são as mais
centrais?
A Estrutura de Larga Escala
A Estrutura de Larga Escala
• As 25 cidades
mais conectadas
• As 25 cidades
mais centrais
A Estrutura de Larga Escala
A Estrutura de Larga Escala
• Anomalias:
o Fato incomum em redes complexas como a internet
• O caso do Alasca:
o Pouco populoso
o Isolado dos EUA
o Aeroportos se conectam a outros
dentro do próprio estado
o Poucos se conectam aos EUA
continental
Estrutura de comunidades
• Modularidade
o A modularidade de uma determinada partição de nós em
grupos é máxima quando os nós que estão densamente
conectados entre eles são agrupados e separados dos
outros nós na rede.
• Algoritmo Simulated Annealing
o Técnica de otimização
o Objetivo de encontrar a partição que maximiza a
modularidade
Estrutura de comunidades
Estrutura de comunidades
• Não pode ser explicada por razões puramente
geográficas.
o Maioria das cidades na Europa + Rússia Asiática
o Cidades Chinesas + Japonesas + Cidades em outros países do
sudeste Asiático
o Índia + Península Árabe + Norte da África
Papel mundial das cidades
• Caracterizamos o papel de cada cidade na rede
de transporte aéreo com base em seu padrão de
conexões intracomunitárias e intercomunitárias.
• Intracomunitárias:
o Hubs e Não-hubs
o Grau de um nó dentro da comunidade
• zi score: mede o quanto o nó i é “bem-conectado” com os
outros nós da comunidade.
Papel mundial das cidades
• Intercomunitárias:
o Coeficiente de participação do nó i (Pi)
o Pi -> 1
• Links uniformemente distribuídos entre todas as comunidades
o Pi -> 0
• Links concentrados na sua própria comunidade
Papel mundial das cidades
• Papel dos nós
o Foram definidos sete diferentes "papéis universais“
• De acordo com seus padrões na intracomunidade e
conecção intercomunidades
o Cada um corresponde a uma região de zP diferente
o Grau dentro do módulo:
• Hubs: z ≥ 2,5
• Não-hubs: z <2,5
Papel mundial das cidades
• Podem ser mais finamente classificados utilizando o Pi
• Não-hubs
o Nós ultraperiféricos
• Todos os seus links dentro de seu módulo (P ≤ 0,05)
o Nós periféricos
• A maioria dos links dentro seu módulo (0,05 <P ≤ 0,62)
o Nós não-hub conectores
• Muitos links para outros módulos (0,62 <P ≤ 0,80)
o Nós não-hub sem parentes
• Com ligações homogeneamente distribuídas entre todos os módulos (P> 0,80)
• Hubs
o Hub provincial
• Grande maioria dos links dentro de seu módulo (P ≤ 0,30)
o Hub conector
• Muitos links para a maioria dos outros módulos (0,30 <P ≤ 0,75)
o Hub sem parentes
• Links distribuídos de forma homogênea entre todos os módulos (P> 0,75).
Papel mundial das cidades
• Para cada cidade na rede mundial de transporte aéreo,
foi calculado grau intra-comunidade zi e seu coeficiente
de participação Pi.
o 95,4% das cidades são classificadoa como periféricas ou ultraperiféricas.
o O,5% de não-hub conectores.
• As cidades que não são hubs em suas respectivas comunidades
raramente têm links para muitas outras comunidades na rede de
transporte aéreo.
• Contraste gritante com o que acontece em algumas
redes biológicas (conectores não-hub parecem ser
relativamente freqüente e desempenham um papel
importante)
Papel mundial das cidades
•
A maioria das cidades são
classificadas como nós
ultraperiféricos (preto) ou
periféricas (vermelho) .
•
Número pequeno de nós nãohub desempenham o papel de
conectores (verdes).
•
Frações aproximadamente
iguais de provincial (amarelo) e
conector de hubs (marrom).
Papel mundial das cidades
•
A ausência de comunidades
se manifesta na maioria dos
hubs - rubs sem parentes
(cinza)
•
Aparecimento de nonhubs
sem parentes (azul).
•
Muitos hubs sem parentes ou
nonhubs sem parentes
•
A rede contém essencialmente
nenhum hub provincial ou
conector.
Papel mundial das cidades
Conclusão
• A rede de transporte aéreo em todo o mundo
é uma rede pequeno mundo em que:
o O número de conexões nonstop a partir de uma
determinada cidade e o número de caminhos mais curtos
passando por uma determinada cidade tem distribuições
que são livres de escala.
• Os nós com mais conexões nem sempre são as
mais centrais na rede
o Estrutura multi-comunidade da rede
o A estrutura das comunidades na rede é devido a fatores
tanto geográficos quanto políticos
Conclusão
• A análise da estrurura das cumunidades na rede é
de grande importância
o Permite identificar as maneiras mais eficientes para
projetar a estrutura da rede
• tendo identificado as comunidades, é possível identificar quais os
que estão mal conectadas e as formas de minimizar esse problema
o Cidades conectadas com diferentes comunidades têm um
papel desproporcional na dinâmica de processos
importantes
• Propagação de infecções
• Encontrar as comunidades é o primeiro passo para identificar essas
cidades.
?
Obrigado!
Referências
• The worldwide air transportation network: Anomalous
centrality, community structure, and cities' global roles - R.
Guimera, S. Mossa, A. Turtschi, and L.A.N. Amaral – 2004
• http://www.lx97.com/maps/
• http://www.youtube.com/watch?v=US4mKjYeklM&feature=BF
a&list=SP3416E39D02A5BFE9&lf=list_related
• http://www.youtube.com/watch?v=G1L4GUA8arY&feature=B
Fa&list=SP3416E39D02A5BFE9&lf=list_related
• http://www.youtube.com/watch?NR=1&v=bo1ZtpKqlYw
• The role of the airline transportation network in the prediction
and predictability of global epidemics - Vittoria Colizza, Alain
Barrat, Marc Barthélemy and Alessandro Vespignani - 2005