Avaliação Distribuída de Centralidade em Redes Complexas
Resumo
Entre os diferentes tipos de centralidade, Closeness Centrality é uma das mais tradicionais e afere a importância de cada nó pela sua proximidade com todos os demais nós da rede. Entretanto, o cálculo desse tipo de centralidade apresenta um alto custo computacional. Por disso, o seu uso se torna impraticável para redes de grande porte. Assim, este trabalho apresenta um método distribuído que pode ser utilizado para calcular vários tipos de centralidades, entre elas uma cuja ordenação dos nós tem um alto grau de correlação com a ordenação obtida pelo uso de Closeness Centrality. O método proposto funciona de maneira totalmente distribuída, baseando-se em conhecimento local dispensando o conhecimento completo da topologia da rede, e é computacionalmente menos custoso que o método tradicional.
Referências
Boguna, M., Pastor-Satorras, R., Diaz-Guilera, A., e Arenas, A. (2004). List of edges of the giant component of the network of users of the Pretty-Good-Privacy algorithm for secure information interchange. Physical Review E, 70(056122).
Brandes, U. e Pich, C. (2007). Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos, 17(07):2303.
CAIDA (2003). Internet Router-Level Topology Measurements. [link]
Colizza, V., Pastor-Satorras, R., e Vespignani, A. (2007). Reaction-Diffusion processes and metapopulation models in heterogeneous networks. Nature Physics, 3:276–282.
Everett, M. e Borgatti, S. (2005). Ego network betweenness. Social Networks, 27(1):31–38.
Jeong, H., Mason, S. P., Barabasi, A.-L., e Oltvai, Z. N. (2001). Lethality and centrality in protein networks. Nature, 411(6833):41–42.
Kermarrec, A.-M., Le Merrer, E., Sericola, B., e Trédan, G. (2011). Second order centrality: distributed assessment of nodes importance in complex networks. Computer Communications, 34(5):619–628.
Marsden, P. (2002). Egocentric and sociocentric measures of network centrality. Social Networks, 24(4):407–422.
Nanda, S. e Kotz, D. (2008). Localized Bridging Centrality for Distributed Network Analysis. ICCCN 17th International Conference on Computer Communications and Networks, pages 1–6.
Newman, M. (2006). Internet – a symmetrized snapshot of the structure of the internet at the level of autonomous systems. [link]
Wehmuth, K. e Ziviani, A. (2011a). Distributed location of the critical nodes to network robustness based on spectral analysis. In 2011 7th Latin American Network Operations and Management Symposium, pages 1–8, Quito, Ecuador. IEEE.
Wehmuth, K. e Ziviani, A. (2011b). Um Novo Algoritmo Distribuído para Avaliação e Localização de Centralidade de Rede. In X Workshop em Desempenho de Sistemas Computacionais e de Comunicação (WPerformance 2011), XXXI Congresso Nacional da Sociedade Brasileira de Computação (CSBC), Natal, RN, Brasil.
Wehmuth, K. e Ziviani, A. (2012a). Distributed Assessment of Network Centralities in Complex Social Networks. In International Workshop on Complex Social Network Analysis CSNA 2012, Istambul, Turkey.
Wehmuth, K. e Ziviani, A. (2012b). Distributed assessment of the closeness centrality ranking in complex networks. In Proceedings of the Fourth Annual Workshop on Simplifying Complex Networks for Practitioners SIMPLEX ’12, number c, page 43, Lyon, France. ACM Press.
Wehmuth, K. e Ziviani, A. (2013). DACCER: Distributed Assessment of the Closeness Centrality Ranking in Complex Networks. Computer Networks, Elsevier, aceito para publicação.
