Distributed Assessment of Centrality in Complex Networks

• Klaus Wehmuth LNCC
• Artur Ziviani LNCC / MCTI

Abstract

Among the different centrality definitions, the traditional closeness centrality ranks the nodes by how close each node is to all other nodes in the network. Nevertheless, computing closeness centrality in large complex networks is costly. Here, we present a fully distributed method capable of yielding different kinds of centrality, among them one which node ranking correlates strongly with the closeness centrality ranking, but being cheaper than the traditional algorithm and not requiring full knowledge of the network’s topology.

References

Barabási, A. e Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439):509–512.

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.