Intermediação

 Nota: Para outro significado, veja intermediação financeira .

A intermediação é uma medida de centralidade de um nó em uma rede. Ela é igual ao número de menores caminhos de todos os vértices para quaisquer outros vértices que passam por aquele nó. A intermediação é uma medida mais útil do que apenas a conectividade de um nó. A primeira é mais global para a rede, enquanto a segunda tem apenas um efeito local. O desenvolvimento da intermediação é geralmente atribuído ao sociólogo Linton Freeman, que também desenvolveu várias outras medidas de centralidade.[1] A mesma ideia também foi proposta pelo matemático J. Anthonisse, embora seu trabalho nunca tenha sido publicado.[2]

Ao longo dos últimos anos, a intermediação se tornou uma estratégia popular para lidar com redes complexas. As aplicações incluem redes sociais e de computadores,[3][4] redes biológicas (tais como redes tróficas e de polinização), [5][6]redes de transporte, [7][8] redes de cooperação científica[9] e outras.

Definição

A intermediação de um nó ${\displaystyle v}$ é dada pela expressão:

${\displaystyle g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

onde ${\displaystyle \sigma _{st}}$ é o número total de menores caminhos do nó ${\displaystyle s}$ para o nó ${\displaystyle t}$ e ${\displaystyle \sigma _{st}(v)}$ é o número de menores caminhos que passam por ${\displaystyle v}$.

Vale salientar que a intermediação de um nó escala com o número de pares de nós, indicado pelo somatório dos índices. Portanto o cálculo pode ser redimensioado dividindo pelo número de pares de nós não incluindo ${\displaystyle v}$, de maneira que ${\displaystyle g\in [0,1]}$. A divisão é feita por ${\displaystyle (N-1)(N-2)}$ para grafos direcionados e por ${\displaystyle (N-1)(N-2)/2}$ para grafos não-direcionados, onde ${\displaystyle N}$ é o número de nós no componente grande. Nota-se que o valor escala para o máximo quando um nó é compartilhado por todos os menores caminhos. Este geralmente não é o caso, e a normalização pode ser realizada sem a perda de precisão

${\displaystyle {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}}$

que resulta em:

${\displaystyle \max(normal)=1}$

${\displaystyle \min(normal)=0}$

Este redimensionamento sempre será de uma faixa menor para uma faixa maior, logo não há perda de precisão.

Algoritmos

Calcular a intermediação e a proximidade de todos os vértices de um grafo envolve calcular os menores caminhos entre todos os pares de vértices do grafo. Isto leva um tempo ${\displaystyle \Theta (|V|^{3})}$ com o algoritmo de Floyd-Warshall, modificado para não apenas encontrar um mas contar todos os menores caminhos entre dois nós. Em grafos esparsos, algoritmo de Johnson pode ser mais eficiente, levando um tempo ${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$. Em grafos sem peso, calcular a intermediação leva um tempo ${\displaystyle O(|V||E|)}$ usando o algoritmo de Brandes.[10]

Ao se calcular a intermediação e a proximidade de todos os vértices de um grafo, se assume que o grafo é não-direcionado e suas conexões permitem laços e arestas múltiplas. Ao lidar especificamente com grafos complexos, por vezes os grafos não possuem laços ou arestas múltiplas de modo a manter as relações simples (onde as arestas representam conexões entre duas pessoas ou vértices). Neste caso, o algoritmo de Brandes divide o valor final por 2, considerando que cada menor caminho é contado duas vezes.[10]

Referências

1. Freeman, Linton (1977). «A set of measures of centrality based on betweenness». Sociometry. 40: 35–41 
2. Newman, M.E.J. 2010. Networks: An Introduction. Oxford, UK: Oxford University Press.
3. Brandes, Ulrik (2008). «On variants of shortest-path betweenness centrality and their generic computation». Social Networks. 30: 136–145 
4. Cuzzocrea, Alfredo; Papadimitriou, Alexis; Katsaros, Dimitrios; Manopoulus, Yanis (2012). «Edge betweenness centrality: A novel algorithm for QoS-based topology control over wireless sensor networks». Journal of Network and Computer Applications. 35: 1210–1217 
5. Estrada, Ernesto (2007). «Characterization of topological keystone species Local, global and meso-scale centralities in food webs». Ecological Complexity. 4: 48–57 
6. Martin Gonzalez, Ana M.; Dalsgaard, Bo; Olesen, Jens M. (2010). «Centrality measures and the importance of generalist species in pollination networks». Ecological Complexity. 7: 36–43 
7. Wang, Jiaoe; Huihui, Mo; Wang, Fahui; Jin, Fengjun (2011). «Exploring the network structure and nodal centrality of China's air transport network: A complex network approach». Journal of Transport Geography. 19: 712–721 
8. Rodriguez-Deniz, Hector (2012). «Using SAS® to Measure Airport Connectivity: An Application of Weighted Betweenness Centrality for the FAA National Plan of Integrated Airport Systems (NPIAS)». Proceedings of the SAS Global Forum 2012, Paper 162-2012 
9. Abassi, Alireza; Hossain, Liaquat; Leydesdorff, Loet (2012). «Betweenness centrality as a driver of preferential attachment in the evolution of research collaboration networks». Journal of Informetrics. 6: 403–412 
10. Ulrik Brandes. «A faster algorithm for betweenness centrality» (PDF). Consultado em 27 de abril de 2013. Arquivado do original (PDF) em 28 de fevereiro de 2013 

• Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «Betweenness centrality», especificamente desta versão.