THE WORLD AIR
TRANSPORTATION
NETWORK
R. GUIMERA ET AL (2005)
Ricardo Prudêncio
Tópicos Avançados em
Inteligência Artificial
REDES DE TRANSPORTE AÉREO


Grande impacto nas economias locais, nacionais e
internacionais
Responsável pela mobilidade de milhões de
pessoas e toneladas de carga todos os dias.
REDES DE TRANSPORTE AÉREO

Relacionadas à propagação de doenças
contagiosas
REDES DE TRANSPORTE AÉREO
 Sistema

E.g., atrasos = 150 bilhões de euros em 1999
 Falhas

ainda falho e ineficiente
locais = conseqüências globais
E.g. Mal tempo em Chicago = diminuição de 100 para
72 vôos por hora = atrasos em todo país
PERGUNTAS

Como projetar um sistema melhor?



Como o sistema evolui?
Quais os pontos de risco?
Quais as barreiras e gargalos do
sistema?
DIFICULDADES
 Companhias
 Fatores
 Fatores
tentam maximizar lucros
geográficos limitam ações
políticos e econômicos podem gerar
barreiras
ARTIGO - RESUMO


The worldwide air transportation network:
Anomalous centrality, community structure, and
cities' global roles - R. Guimera, S. Mossa, A.
Turtschi, and L. Amaral – 2005
Objetivos:

Caracterizar a estrutura da rede mundial de
transporte aéreo

Identificar características gerais como efeito de
mundo pequeno

Estudar estrutura de comunidades e papel das
cidades
DADOS UTILIZADOS
 OAG

MAX Database
Escalas de vôos de >800 companhias aéreas
 Rede
gerada (vôos de 1 a 7 de Novembro 2000)

3.883 cidades (nós)

Aresta entre cidades caso pelo menos um vôo direto
(sem escalas) de qualquer aeroportos das cidades

27.051 arestas
DADOS UTILIZADOS
 Alta

redundância de vôos entre cidades
Maior confiabilidade na análise
 Matriz
de adjacência praticamente
simétrica
DADOS UTILIZADOS
ESTRUTURA DE LARGA ESCALA

Propriedade de “Mundo Pequeno”

Média dos distância geodésica = 4,4


56% dos pares são conectados por 4 vôos ou
menos
Diferenças observadas por região

Ásia = caminho médio de 3.5
ESTRUTURA DE LARGA ESCALA
 Maior

distância = 15 passos
Mount Pleasant (Ilhas Malvinas) --> Wasu (Nova Guiné)
ESTRUTURA DE LARGA ESCALA

Coeficiente de clusterização (C):
-

Probabilidade de duas cidades diretamente conectadas
serem ambas diretamente conectadas a uma terceira
Resultado compatível com redes de mundo
pequeno (C = 0,62)
ESTRUTURA DE LARGA ESCALA

Distribuição do grau


Número de outras cidades conectadas por vôos diretos
Rede sem escala

A rede possui alguns nós que são muito mais conectados
do que os demais


Distribuição de lei de potência
Nós com alto grau de conectividade tendem a receber
mais conexões
ESTRUTURA DE LARGA ESCALA
ESTRUTURA DE LARGA ESCALA

Intermediação (Bi)

Número de menores caminhos conectando quaisquer
duas outras cidades que passem pela cidade i
ESTRUTURA DE LARGA ESCALA

As cidades mais conectadas também são as mais
centrais ?
ESTRUTURA DE LARGA ESCALA
ESTRUTURA DE LARGA ESCALA
• As 25 cidades
mais conectadas
• As 25 cidades
mais centrais
ESTRUTURA DE LARGA ESCALA
ESTRUTURA DE LARGA ESCALA

Anomalias:


Alta intermediação e baixo grau
O caso do Alasca (Anchorage):





Pouco populoso
Isolado dos EUA
Aeroportos se conectam a outros dentro do próprio
estado
Poucos se conectam aos EUA continental
Menos ainda ao Canadá
ESTRUTURA DE COMUNIDADES
 Anomalias
podem ser explicadas pela
estrutura de comunidades na rede
 Nós
tem diferentes graus de influência intra
e inter comunidades
 Detecção

de comunidades
Maximização da modularidade da rede
ESTRUTURA DE COMUNIDADES
ESTRUTURA DE COMUNIDADES
 Não
pode ser explicada por razões
puramente geográficas.



E.g. Algumas cidades distantes da Europa estão no
cluster europeu
E.g., Aparentemente existe uma linha divisória entre
Índia e Paquistão
E.g., Cuba é uma ilha!!!
PAPEL GLOBAL DAS CIDADES


Cidades foram classificadas conforme
conectividade inter e inter comunidades
Intracomunitárias:

Grau do nó dentro da comunidade


zi score: grau padronizado.
Hubs e Não-hubs
Hubs: z ≥ 2,5
 Não-hubs: z <2,5

PAPEL GLOBAL DAS CIDADES
 Intercomunitárias:

Coeficiente de participação do nó i (Pi)

Pi -> 1


Links uniformemente distribuídos entre todas as comunidades
Pi -> 0

Links concentrados na sua própria comunidade
PAPEL GLOBAL DAS CIDADES
 Foram
definidos sete diferentes "papéis
universais“
 Não-hubs

Ultraperiféricos


Periféricos


A maioria dos links dentro seu cluster (0,05 <P ≤ 0,62)
Não-hub conectores


Todos os seus links dentro de seu cluster (P ≤ 0,05)
Muitos links para outros cluster (0,62 <P ≤ 0,80)
Nós não-hub kinless

Com ligações distribuídas entre todos os cluster (P> 0,80)
PAPEL GLOBAL DAS CIDADES
 Hubs

Hub provincial


Hub conector


Grande maioria dos links dentro de seu cluster (P ≤ 0,30)
Muitos links para a maioria dos outros cluster s (0,30 <P ≤ 0,75)
Hub sem parentes

Links distribuídos entre todos os módulos (P> 0,75).
PAPEL GLOBAL DAS CIDADES
•
Ultraperiféricos (preto) e
periféricas (vermelho) = 95%.
•
Não-hub conectores (verdes) =
0.5%.
•
Hub = 4.1%
•
Proporção similar de hubs
provinciais (amarelo) e conectores
(marrom).
PAPEL GLOBAL DAS CIDADES
Rede Observada
Rede Aleatória
PAPEL GLOBAL DAS CIDADES
CONCLUSÕES
 Rede
de transporte aéreo é uma rede pequeno
mundo e livre de escala

Os nós com mais conexões nem sempre são as mais
centrais na rede


Estrutura multi-comunidade da rede
A estrutura das comunidades se deve a fatores geográficos,
políticos e econômicos
REFERÊNCIA

R. Guimera, S. Mossa, A. Turtschi, and L.A.N.
Amaral . The worldwide air transportation network:
Anomalous centrality, community structure, and
cities' global roles. PNAS, vol. 102 (22), 2005.