A literatura traz quatro medidas básicas relacionadas às distâncias no grafo: tamanho do menor caminho médio (average shortest path length), eficiência topológica (efficiency), grau de proximidade (closeness) e grau de intermediação (betweenness).
3.4.2.1 MENOR CAMINHO MÉDIO
Os menores caminhos entre todos os vértices de uma rede podem ser representados através de uma matriz de distâncias D, cujos elementos dij, expressam o valor do menor caminho entre os
vértices i e j. A média entre os valores na matriz de distâncias (caminhos mínimos) exprime o caminho característico da rede (ou menor caminho médio ou, ainda, tamanho do menor caminho médio), sendo calculada por:
𝐿 = 𝑁(𝑁 − 1) ∑ 𝑑1 𝑖𝑗 𝑖≠𝑗
(7)
Numa rede de transporte aéreo, o tamanho do menor caminho médio reflete o número médio de escalas necessárias para ligar dois pares de aeroportos. Se numa determinada rede há tamanho de menor caminho médio iguais a 1, 2, 3 e 4, isso implicaria que um voo de um aeroporto qualquer i para um aeroporto qualquer j, não teria mais do que três escalas (o tamanho de caminho médio igual a 1 significa um voo direto) (LI-PING et al., 2003).
3.4.2.2 EFICIÊNCIA TOPOLÓGICA
Um problema na definição do menor caminho médio é que seu valor diverge, caso haja vértices desconectados no grafo, já que dij é considerado infinito quando não há um caminho entre i e j
27
Marchiori (2001), que introduziram uma medida chamada eficiência global (global efficiency), cujo cálculo é realizado da seguinte forma:
𝐸 = 1 𝑁(𝑁 − 1) ∑ 1 𝑑𝑖𝑗 𝑖≠𝑗 (8)
Essa medida é um indicador da capacidade de transporte ou comunicação de uma rede, podendo, ainda, ser empregada para determinar quais dos vértices são mais importantes para obtenção de um transporte mais eficiente pela rede. Em muitos casos, os hubs correspondem a esses vértices. No entanto, pode haver uma hierarquia de importância entre vértices, mesmo quando eles têm aproximadamente o mesmo grau (RODRIGUES, 2007).
3.4.2.3 GRAU DE PROXIMIDADE
A centralidade ou grau de proximidade (closeness centrality) de um vértice é definido como o inverso do tamanho do menor caminho médio do vértice para todos os demais vértices do grafo (OKAMOTO et al., 2008). Outras definições ligeiramente diferentes existem (FREEMAN, 1979), mas não serão consideradas neste trabalho.
Essa propriedade pode ser vista como uma medida do quão eficientemente um vértice conseguirá compartilhar informações ou processar fluxos com outros vértices da rede. Quanto maior a centralidade de aproximação de um vértice, menor é a distância média entre esse vértice e os demais e, portanto, mais bem posicionado está o vértice para realização de trocas com outros vértices (OKAMOTO et al., 2008).
O grau de proximidade é calculado pelo inverso da soma de todos os menores caminhos de um vértice i para cada um dos outros vértices da rede:
𝐶𝑙𝑖 = ∑𝑁 − 1𝑑 𝑖𝑗 𝑖≠𝑗∈𝑉
(9)
Sendo que V é a componente conectada que contém todos os vértices alcançáveis pelo vértice
i. Os vértices que possuem alto valor de proximidade apresentam maior centralidade na rede, isto é, todos os outros vértices da mesma componente conectada podem ser facilmente alcançados a partir do vértice com alto grau de proximidade.
28
Na rede de transporte aéreo, a identificação de tais vértices pode ajudar no planejamento do crescimento da rede e na promoção do turismo em cidades que possuem aeroportos que não são alcançáveis facilmente pelos demais (SAPRE, 2011).
3.4.2.4 GRAU DE INTERMEDIAÇÃO
A centralidade ou grau de intermediação (betweenness centrality) é uma propriedade que pode estar associada tanto ao vértice quanto à aresta. Ela mede a razão entre o número de menores caminhos que passam por um determinado vértice/aresta e o total de menores caminhos da rede, ou seja, o quanto um vértice ou aresta está no caminho entre outros vértices (RODRIGUES, 2007).
O cálculo é feito conforme Equação 10, onde duj(i) é o número de menores caminhos entre os
vértices u e j que passam pelo vértice (ou aresta) i e duj é o número total de menores caminhos
entre u e j. A soma é feita sobre todos os pares distintos u, j de vértices (RODRIGUES, 2007). 𝐵𝑖 = ∑𝑑𝑢𝑗𝑑 (𝑖)
𝑢𝑗 𝑢≠𝑗
(10)
A média do grau de intermediação pode ser utilizada como uma medida de caracterização global da rede:
〈B〉 = 𝑁 ∑ B1 𝑖 𝑖
(11)
A partir do grau de intermediação pode-se ainda obter uma medida global chamada dominância do ponto central, que é calculada pela seguinte equação, onde Bmax é o maior valor da
betweenness na rede (FREEMAN, 1977, 1979):
𝐶𝐷 = 𝑁 − 1 ∑(B1 max − B𝑖) 𝑖
(12)
Inicialmente introduzida para análise de redes sociais, essa medida tem sido considerada útil, também, para a análise de redes de transportes (MONECHI, 2015). Quando o valor do
betweenness (Bi) é calculado de forma normalizada, a dominância do ponto central assume o
valor 0 quando a rede é completamente conectada e assume o valor 1 quando se trata de uma rede tipo estrela, na qual um vértice central está incluso em todos os caminhos da rede.
29
Numa rede de transporte aéreo, os aeroportos que possuem alto valor de grau de intermediação podem ser críticos para a integridade da rede, já que a maioria dos voos que envolva uma ou mais paradas (escalas ou conexões) passam por eles. Além disso, esses aeroportos podem representar relevância socioeconômica para a região ou país. Assim, um funcionamento ineficiente nesses vértices pode levar a fragmentação da rede (DALL’ASTA et al., 2006; SAPRE, 2011).
A Figura 3.4 demonstra a relação entres duas características importantes presente em redes complexas. O vértice 5 faz a interligação de dois blocos relativamente grandes, sendo o vértice de maior grau de intermediação. Já os vértices 3 e 7 são considerados hubs, pois são os vértices com maior número de conexões.
Figura 3.4. Relação entre vértice hub e vértice de alto grau de intermediação (Fonte: Silva & Otazu, 2011).
Sobre o cálculo do grau de intermediação numa rede de transporte aéreo, DALL’ASTA et al. (2006) fizeram uma importante contribuição ao proporem o uso do conceito de “distância efetiva”. Os autores partiram do fato, inicialmente discutido por BARRAT et al. (2004), de que em redes com pesos, a heterogeneidade do atributo das arestas faz com que alguns caminhos sejam mais favoráveis ou eficazes do que outros para promover o fluxo entre as conexões da rede. Isso tornou natural a generalização da noção da centralidade de intermediação para outra da centralidade de intermediação valorada, na qual os menores caminhos, medidos em saltos/arestas, seriam substituídos por caminhos que refletissem os pesos das arestas.
Uma maneira direta de generalizar a distância por saltos (ou por número de arestas), proposta pelos autores, consistiu em atribuir à cada aresta um comprimento lij que fosse uma função da
característica associada à aresta.
Para o caso da rede de transporte aéreo, uma característica natural que influencia a distância entre aeroportos é a separação geográfica entre eles. Por outro lado, seria razoável assumir que quanto maior a oferta de transporte, melhores e mais frequentes são as oportunidades de deslocamento de pessoas e mercadorias entre um par de aeroportos. Assim, a distância efetiva
30
(lijw) entre dois pares de aeroportos conectados é função da distância geográfica (dwij) e
inversamente proporcional à oferta de tráfego (wij), conforme Equação 13 (DALL’ASTA et al.
2006).
𝑙𝑖𝑗𝑤 = 𝑑𝑖𝑗 𝑤
𝑤𝑖𝑗
(13)
Dessa forma, para quaisquer dois nós h e j, o menor caminho valorado entre eles (σw) é aquele
em que a soma dos valores da distância valorada (lw) é mínima, independentemente do número
de arestas percorridas no caminho. O grau de intermediação valorado passa a ser calculado da seguinte maneira (DALL’ASTA et al. 2006)
𝐵𝑖𝑤 = ∑𝜎ℎ𝑗𝑤(𝑖)
𝜎𝑢𝑗𝑤 𝑢≠𝑗
(14)
No capítulo 5, quando se descreve sobre a formulação do método de análise de vulnerabilidade da rede de transporte aéreo, o conceito de distância efetiva será resgatado e empregado no processo de cálculo de outros parâmetros valorados e que precisam reconhecer o menor caminho entre pares de nós: tamanho do menor caminho médio, diâmetro, grau de proximidade e eficiência da rede.