Centralidade de Proximidade por Múltiplos Caminhos Disjuntos: Aplicação em Redes de Longa Distância

  • Mariana S. Maciel Barbosa Universidade Federal do Rio de Janeiro
  • Dianne S. V. Medeiros Universidade Federal Fluminense
  • Miguel Elias M. Campista Universidade Federal do Rio de Janeiro

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.

Palavras-chave: Redes Dinâmicas, Métricas de Centralidade, Resiliência

Referências

Bavelas, A. (1948). A mathematical model for group structures. Human Organization, 7(3):16–30.

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.
Publicado
06/05/2019
Como Citar

Selecione um Formato
BARBOSA, Mariana S. Maciel; MEDEIROS, Dianne S. V.; CAMPISTA, Miguel Elias M.. Centralidade de Proximidade por Múltiplos Caminhos Disjuntos: Aplicação em Redes de Longa Distância. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 37. , 2019, Gramado. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . p. 85-98. ISSN 2177-9384. DOI: https://doi.org/10.5753/sbrc.2019.7352.