Um Novo Algoritmo Distribuído para Avaliação e Localização de Centralidade de Rede
Resumo
Nós propomos um novo algoritmo distribuído para avaliação de centralidade em redes complexas. Esse algoritmo usa somente informação localizada em cada nó, não necessitando do conhecimento da topologia completa da rede. Além do cálculo do valor de centralidade em cada nó, nossa proposta também provê um meio para a localização dos nós mais centrais, também somente usando informação localizada em cada nó. Nós avaliamos experimentalmente o algoritmo proposto comparando-o a um algoritmo recente e concluímos que nosso algoritmo alcança resultados similares, porém com custo para sua aplicabilidade prática significativamente menor. Esse resultado permite ao nosso algoritmo ser aplicado a redes reais de larga-escala, o que demonstramos aplicando-o a um registro (trace) de uma rede real de roteadores.Referências
Barabási, A. e Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439):509–512. Borgatti, S. (2005). Centrality and network flow. Social Networks, 27(1):55–71.
Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177.
Brin, S. e Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. In Seventh International World-Wide Web Conference (WWW 1998).
Dinh, T., Xuan, Y., Thai, M., Park, E., e Znati, T. (2010). On approximation of new optimization methods for assessing network vulnerability. In Proc. of the IEEE INFOCOM. IEEE.
Erdos, P. e Renyi, A. (1959). On random graphs I. Publ. Math. Debrecen. Freeman, L. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1):35–41.
Kermarrec, A.-M., Le Merrer, E., Sericola, B., e Trédan, G. (2011). Second order centrality: Distributed assessment of nodes criticity in complex networks. Computer Communications, 34(5):619–628.
Lehmann, K. e Kaufmann, M. (2003). Decentralized algorithms for evaluating centrality in complex networks. Technical Report WSI-2003-10, Wilhelm Schickard Institut.
Nanda, S. e Kotz, D. (2008). Localized Bridging Centrality for Distributed Network Analysis. In Proc. of Int. Conference on Computer Communications and Networks (ICCCN). IEEE.
Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177.
Brin, S. e Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. In Seventh International World-Wide Web Conference (WWW 1998).
Dinh, T., Xuan, Y., Thai, M., Park, E., e Znati, T. (2010). On approximation of new optimization methods for assessing network vulnerability. In Proc. of the IEEE INFOCOM. IEEE.
Erdos, P. e Renyi, A. (1959). On random graphs I. Publ. Math. Debrecen. Freeman, L. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1):35–41.
Kermarrec, A.-M., Le Merrer, E., Sericola, B., e Trédan, G. (2011). Second order centrality: Distributed assessment of nodes criticity in complex networks. Computer Communications, 34(5):619–628.
Lehmann, K. e Kaufmann, M. (2003). Decentralized algorithms for evaluating centrality in complex networks. Technical Report WSI-2003-10, Wilhelm Schickard Institut.
Nanda, S. e Kotz, D. (2008). Localized Bridging Centrality for Distributed Network Analysis. In Proc. of Int. Conference on Computer Communications and Networks (ICCCN). IEEE.
Publicado
19/07/2011
Como Citar
WEHMUTH, Klaus; ZIVIANI, Artur.
Um Novo Algoritmo Distribuído para Avaliação e Localização de Centralidade de Rede. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 10. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 1967-1980.
ISSN 2595-6167.
