Intermediação

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Disambig grey.svg 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[editar | editar código-fonte]

A intermediação de um nó é dada pela expressão:

onde é o número total de menores caminhos do nó para o nó e é o número de menores caminhos que passam por .

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 , de maneira que . A divisão é feita por para grafos direcionados e por para grafos não-direcionados, onde é 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

que resulta em:

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

Algoritmos[editar | editar código-fonte]

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 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 . Em grafos sem peso, calcular a intermediação leva um tempo 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. a b Ulrik Brandes. «A faster algorithm for betweenness centrality» (PDF)