Centralidade de Proximidade por Múltiplos Caminhos Disjuntos: Aplicação em Redes de Longa Distância
Resumo
As métricas tradicionais de centralidade consideram apenas os caminhos mais curtos, ignorando a existência de caminhos um pouco mais longos entre pares de nós da rede. Em redes dinâmicas, porém, esses caminhos podem ser estratégicos por questões de resiliência a falhas. Assim, este artigo propõe a centralidade de proximidade por múltiplos caminhos disjuntos, que extrapola a proximidade tradicional, considerando um número fixo de múltiplos caminhos disjuntos mais curtos. A ideia é identificar nós multiplamente conectados que possam desempenhar tarefas que exijam maior disponibilidade. A métrica proposta é avaliada através da comparação com outras métricas de centralidade. Os resultados confirmam que os nós mais centrais da métrica proposta são mais acessíveis quando ocorrem falhas em nós aleatórios da rede. Além disso, em caso de múltiplas falhas nos nós mais centrais de cada métrica, o aumento no tamanho médio dos caminhos usados para os nós acessarem uns aos outros é menor para a métrica proposta, quando comparada à proximidade tradicional.
Referências
Bavelas, A. (1950). Communication patterns in task-oriented groups. The Journal of the Acoustical Society of America, 22(6):725–730.
Beauchamp, M. A. (1965). An improved index of centrality. Behavioral science, 10(2):161–163.
Borgatti, S. P. e Everett, M. G. (2006). A graph-theoretic perspective on centrality. Social Networks, 28(4):466 – 484.
Bouet, M., Leguay, J., Combe, T., e Conan, V. (2015). Cost-based placement of vdpi functions in nfv infrastructures. International Journal of Network Management, 25(6):490– 506.
Brandes, U. e Fleischer, D. (2005). Centrality measures based on current flow. Em STACS, pp. 533–544.
Couto, R. S., Secci, S., Campista, M. E. M., e Costa, L. H. M. (2014). Latência versus sobrevivência no projeto de centros de dados geograficamente distribuídos. XXXII SBRC, pp. 809–822.
Croux, C. e Dehon, C. (2010). Influence functions of the spearman and kendall correlation measures. Statistical methods & applications, 19(4):497–515.
Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social Networks, 1(3):215–239.
Maccari, L. e Cigno, R. L. (2016). Pop-routing: Centrality-based tuning of control messages for faster route convergence. Em Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on, pp. 1–9. IEEE.
Medeiros, D. S. V., Campista, M. E. M., Marcelo Dias de Amorim, N. M., e Pujolle, G. (2017a). Eficiência dos caminhos quase mais curtos em redes dinâmicas. Em SBRC, pp. 544–557.
Medeiros, D. S. V., Campista, M. E. M., Mitton, N., Amorim, M. D., e Pujolle, G. (2017b). The power of quasi-shortest paths: -geodesic betweenness centrality. IEEE
Transactions on Network Science and Engineering, 4(3):187–200. Newman, M. J. (2005). A measure of betweenness centrality based on random walks. Social Networks, 27(1):39–54.
Sidhu, D., Nair, R., e Abdallah, S. (1991). Finding disjoint paths in networks. ACM SIGCOMM Computer Communication Review, 21(4):43–51.
Stephenson, K. e Zelen, M. (1989). Rethinking centrality: Methods and examples. Social Networks, 11(1):1–37. Suurballe, J. (1974). Disjoint paths in a network. Networks, 4(2):125–145.