Identification of influential spreaders in complex networks

Esta monografia apresenta um estudo de acessibilidade e dinâmicas de propagação de redes reais e artificiais. A teoria das redes complexas tem sido amplamente utilizada para se modelar sistemas reais. Identificar os propagadores mais influentes nas redes é importante para controlar e entender as capacidades de propagação do sistema, bem como para garantir uma difusão de informação eficiente, como na dinâmica de rumor. Trabalhos recentes têm sugerido que a identificação de propagadores de influentes não é independente da dinâmica a ser estudada. Por exemplo, os propagadores de doença chaves pode não ser necessariamente assim, quando se trata de analisar contágio social ou propagação de rumor. Além disso, demonstrou-se que diferentes métricas (grau, coreness, etc.) podem identificar diferentes nós influentes mesmo para os mesmos processos dinâmicos com diversos graus de precisão. Neste trabalho, vamos investigar como medidas de centralidade se correlacionam com as capacidades de propagar doenças e rumores dos vértices que constituem as diferentes redes sintética e do mundo real (ambas espaciais e não-espaciais). Propomos também uma generalização da acessibilidade de caminhada aleatória como uma nova medida de centralidade, e derivar expressões analíticas desta última medida para simples configurações de rede. Nossos resultados mostram que, para redes não-espaciais, as centralidades k-core e grau são mais correlacionada com a epidemia, enquanto o grau médio da vizinhança e as medidas de proximidade e acessibilidade são mais relacionados à dinâmica de rumor. Pelo contrário, para as redes espaciais, a medida de acessibilidade supera o restante das medidas de centralidade em quase todos os casos, independentemente do tipo de dinâmica considerada. Portanto, uma consequência importante da nossa análise é que estudos anteriores realizados em redes aleatórias sintéticas não podem ser generalizados para o caso de redes espaciais.This monograph presents a study of accessibility and dynamic propagation of real and artificial networks. Identify of the most influential spreaders in networks is important to control and understand the spreading capabilities of the system as well as to ensure an efficient information diffusion such as in rumor-like dynamics. Recent works have suggested that the identification of influential spreaders is not independent of the dynamics being studied. For instance, the key disease spreaders might not necessarily be so when it comes to analyze social contagion or rumor propagation. Additionally, it has been shown that different metrics (degree, coreness, etc.) might identify different influential nodes even for the same dynamical processes with diverse degree of accuracy. In this work, we investigate how centrality measures correlate with the disease and rumor spreading capabilities of the nodes that made up different synthetic and real-world (both spatial and non-spatial) networks. We also propose a generalization of the random walk accessibility as a new centrality measure and derive analytical expressions for the latter measure for simple network configurations. Our results show that for non-spatial networks, the k-core and degree centralities are most correlated to epidemic spreading, whereas the average neighborhood degree, the closeness centrality and accessibility are most related to rumor dynamics. On the contrary, for spatial networks, the accessibility measure outperforms the rest of centrality metrics in almost all cases regardless of the kind of dynamics considered. Therefore, an important consequence of our analysis is that previous studies performed in synthetic random networks cannot be generalized to the case of spatial networ