Search

This work introduces a generic backbone extraction framework exploiting the mesoscopic network structure. Indeed, numerous real-world networks are made of dense groups of nodes called communities, multi-core or local components. To deal with these groups' heterogeneity, we propose to extract the backbones independently from their various components and fuse them. Experimental investigations on real-world networks demonstrate the effectiveness of the proposed approach compared to the classical techniques' agnostic of the mesoscopic structure of real-world networks.

CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico Understanding the collective behavior of (groups of) individuals in complex systems, even in scenarios where the individual properties of their components are known, is a challenge. From the point of view of network models, the collective actions of these individuals are often projected on a graph forming a network of co-interactions, which we here refer to as a many-to-many network. However, the volume and diversity with which these co-interactions are observed in the most varied systems, such as, for example, social media platforms, economic transactions and political behavior in voting systems, impose challenges in the extraction of patterns (structural, contextual and temporal) emerging from collective behavior and that are fundamentally related to a phenomenon under study. Specifically, the frequent presence of a large number of weak and sporadic co-interactions, which, therefore, do not necessarily reflect patterns related to the phenomenon of interest, end up introducing noise to the network model. The large amount of noise, in turn, may obfuscate the most fundamental behavior patterns captured by the network model, that is, the patterns that are essentially relevant to the understanding of the phenomenon under investigation. Removing such noise becomes then a key challenge. Our goal in this dissertation is to investigate the modeling and analysis of collective behavior patterns that emerge in networks formed by co-interactions in different contexts, aiming to extract relevant and fundamental information about a target phenomenon of interest. Specifically, we tackle the extraction of structural, contextual and temporal properties associated with patterns of collective behavior that are fundamentally represented by communities extracted from the network. To this end, we propose a general strategy that addresses the aforementioned challenges. In particular, this strategy includes, as an initial step, the identification and extraction of the network backbone, that is, the subset of the edges that are indeed relevant to the target study. The next steps consist of the extraction of communities from this backbone as a manifestation of the existing collective behavior patterns and the characterization of the structural (topological), contextual (related to the phenomenon of interest) and temporal (dynamic) properties of these communities. Based on this general strategy, we propose specific artifacts for some of the steps that compose it and advance the state-of-the-art, in particular with a new method for backbone extraction, a new temporal node embedding method capable of representing and extracting different temporal patterns of interest from a sequence of networks, and finally a methodology to support the selection and evaluation of backbones from a structural and contextual point of view, considering the most common scenario where there is no ground truth. Furthermore, we explore these artifacts by studying three different phenomena that require different modeling and analysis strategies. Specifically, we investigate: (i) the formation of ideological groups in the Brazilian and U.S. House of Representatives, (ii) online discussions on Instagram in Brazil and Italy, and (iii) information dissemination on WhatsApp. Overall, our results show that the proposed artifacts offer relevant contributions to the field in which this dissertation is inserted. Compreender o comportamento coletivo de (grupos de) indivíduos em sistemas complexos, mesmo em cenários em que as propriedades individuais de seus componentes sejam conhecidas, é um desafio. Do ponto de vista de modelos de redes, as ações coletivas desses indivíduos são, frequentemente, projetadas em um grafo formando uma rede de co-interações, aqui chamado de rede many-to-many. No entanto, o volume e a diversidade com que elas são observadas nos mais variados sistemas atuais como, por exemplo, aplicações de mídia social, transações econômicas e comportamento político em sistemas de votação, impõe desafios na extração de padrões (estruturais, contextuais e temporais) emergentes do comportamento coletivo e que estejam relacionados a um fenômeno alvo de estudo. Especificamente, a frequente presença de um grande número de co-interações fracas e esporádicas e que, portanto, não refletem necessariamente padrões relacionados ao fenômeno de interesse, acabam por introduzir ruído ao modelo de redes. A grande quantidade de ruído, por sua vez, pode mascarar os padrões de comportamento mais fundamentais capturados pelo modelo de rede, ou seja, os padrões que essencialmente são relevantes para o entendimento do fenômeno sob investigação. A remoção deste ruído é, portanto, um desafio importante. Nesta tese, nosso objetivo é investigar a modelagem e análise do comportamento coletivo emergente de redes formadas por co-interações em diferentes contextos, visando extrair informação relevante e fundamental sobre um fenômeno alvo do estudo. Especificamente busca-se abordar a extração de propriedades estruturais, contextuais e temporais que emergem a partir de comportamento coletivo fundamentalmente representadas por comunidades extraídas da rede. Para tal, nós propomos uma estratégia geral que aborda os principais desafios mencionados acima. Em especial, esta estratégia contempla, como passo inicial, a identificação e a extração do backbone da rede, isto é, o subconjunto das arestas relevantes para o estudo alvo. Os próximos passos consistem na extração de comunidades deste backbone, como reflexo de padrões de comportamento coletivo presentes, e a caracterização das propriedades estruturais (topológicas), contextuais (relacionadas ao fenômeno de interesse) e temporais (dinâmica) destas comunidades. Tendo como base essa estratégia geral, nós produzimos artefatos específicos para as etapas que a compõe e avançamos o estado da arte, notavelmente, com um novo método para extração de backbone, um novo método capaz de representar temporalmente uma sequência de redes (temporal node embedding) possibilitando a extração de padrões temporais de interesse, e por fim, uma metodologia para auxiliar na seleção e avaliação de estratégias de extração de backbones do ponto de vista estrutural e contextual considerando o cenário mais comum, em que não há verdade fundamental (ground truth). Além disso, exploramos esses artefatos estudando três fenômenos que requerem diferentes estratégias de modelagem e análise. Especificamente, investigamos: (i) a formação de grupos ideológicos na Câmara dos Deputados do Brasil e dos Estados Unidos, (ii) discussões políticas online ocorrendo no Instagram no Brasil e na Itália e (iii) disseminação de informação no WhatsApp. Em suma, nossos resultados mostram que os artefatos propostos oferecem contribuições relevantes para o campo em que esta tese está inserida.

Collective user behavior in social media applications often drives several important online and offline phenomena linked to the spread of opinions and information. Several studies have focused on the analysis of such phenomena using networks to model user interactions, represented by edges. However, only a fraction of edges contribute to the actual investigation. Even worse, the often large number of non-relevant edges may obfuscate the salient interactions, blurring the underlying structures and user communities that capture the collective behavior patterns driving the target phenomenon. To solve this issue, researchers have proposed several network backbone extraction techniques to obtain a reduced and representative version of the network that better explains the phenomenon of interest. Each technique has its specific assumptions and procedure to extract the backbone. However, the literature lacks a clear methodology to highlight such assumptions, discuss how they affect the choice of a method and offer validation strategies in scenarios where no ground truth exists. In this work, we fill this gap by proposing a principled methodology for comparing and selecting the most appropriate backbone extraction method given a phenomenon of interest. We characterize ten state-of-the-art techniques in terms of their assumptions, requirements, and other aspects that one must consider to apply them in practice. We present four steps to apply, evaluate and select the best method(s) to a given target phenomenon. We validate our approach using two case studies with different requirements: online discussions on Instagram and coordinated behavior in WhatsApp groups. We show that each method can produce very different backbones, underlying that the choice of an adequate method is of utmost importance to reveal valuable knowledge about the particular phenomenon under investigation.