On the analysis of centrality measures for complex and social networks

Abstract

Over the last years, centrality measures have gained importance within complex and social networks research, e.g., as predictors of behavior, identification of powerful and influential elements, detection of critical spots in communication networks and in transmission of diseases. New measures have been created and old ones reinvented, but few have been proposed to understand the relation among measures as well as between measures and other structural properties of the networks. Our research analyzes and studies these relations with the objective of providing a guide to the application of existing centrality measures for new environments and new purposes. We shall also present evidence that the measures known as Walk Betweenness, Information, Eigenvector and Betweenness are substantially better than other metrics in distinguishing vertices in a network by their structural properties. Furthermore, we provide evidence that each metric performs better with respect to distinct kinds of networks. In addition, we show that most metrics present a high level of redundancy (over 0.8 correlation) and its simultaneous use, in most cases, is fruitless. The results achieved in our research reinforce the idea that to use centrality measures properly, knowledge about their underlying properties and behavior is valuable, as we show in this dissertation.

Recentemente, as medidas de centralidade ganharam relevância nas pesquisas com redes complexas e redes sociais, atuando como preditores comportamentais, na identificação de elementos de poder e influência, na detecção de pontos estratégicos para a comunicação e para a transmissão de doenças. Novas métricas foram criadas e outras reformuladas, mas pouco tem sido feito para que se entenda a relação existente entre as diferentes medidas de centralidades, assim como sua relação com outras propriedades estruturais das redes em que elas são frequentemente aplicadas. Nossa pesquisa visa analisar e estudar essas relações para que sirvam de guia na aplicação das medidas de centralidade existentes em novos contextos e aplicações. Nós apresentamos também evidencias que indicam um desempenho superior das medidas conhecidas como Walk Betweenness, Information, Eigenvector and Betweenness na distinção de vértices das redes somente pelas suas características estruturais. Ainda, nós propiciamos detalhes sobre o desempenho distinto de cada métrica de acordo com o tipo de rede em que se trabalha. Adicionalmente, mostramos que várias das medidas de centralidade apresentam um alto nível de redundância e concordância entre si (com correlação superior a 0,8). Um forte indício que o uso simultâneo de várias métricas é improdutivo ou pouco eficaz. Os resultados da nossa pesquisa reforçam a ideia de que para usar apropriadamente as medidades de centralidade é de extrema importância que se saiba mais sobre o comportamento e propriedades das mesmas, fato que salientamos nessa dissertação.