Adaptive model to community detection in dynamic social networks

Abstract

Um problema crucial abordado na análise de redes é a identificação da estrutura da comunidade. Essa estrutura representa a associação dos vértices de uma rede a conjuntos ou comunidades. No entanto, as técnicas atuais de análise de redes se concentram na análise de estruturas estáticas de comunidades, o que cria uma lacuna de pesquisa que não leva em consideração os aspectos dinâmicos dessas estruturas. Algumas soluções para o problema de detecção de comunidades adaptadas à dinamicidade das redes apresentam limitações de desempenho, enquanto outras não se enquadram nesses contextos. Essa situação se agrava à medida que a demanda de análise de redes sociais continua crescendo constantemente. No que diz respeito às classes de solução para o problema de Community Detection (CD), podemos separá-las em duas abordagens: as clássicas, que incluem otimização da modularidade, Random Walk, propagação, entre outros, e as não clássicas, como aquelas baseadas graph embedding, modelagem estatística e aprendizado de máquina. A metodologia utilizada nesta pesquisa inclui uma revisão da literatura, definição do problema de pesquisa, delimitação do escopo do trabalho, desenvolvimento arquitetural do modelo de solução, implementação do modelo, validação por meio de experimentos utilizando redes sociais online (Online Social Network (OSN)) e redação de artigos científicos em conferências e periódicos da área de Ciência da Computação. A revisão da literatura seguiu o protocolo definido por Kitchenham (2004), compreendendo três fases: planejamento (planning), condução (conducting) e relato da revisão (reporting the review). A ferramenta Parsifal (Freitas, 2014) foi utilizada para realização da revisão de literatura. Os repositórios da ACM Digital Library, IEEE Xplore e Springer lInk foram utilizados, considerando o período de 2015 a 2020 e atualização até 2023. As publicações selecionadas incluíram trabalhos em conferências e periódicos da área de Ciência da Computação. Foram identificados inicialmente 49 trabalhos, dos quais 29 foram excluídos por não atenderem aos critérios de inclusão, 3 estavam duplicados e 17 foram aceitos com base nas características definidas pela PICO (Population, Intervention, Comparison, Outcome). Durante a atualização, dois trabalhos de 2023 foram incluídos, totalizando 19 trabalhos como resultado da revisão de literatura. É importante salientar que alguns trabalhos não utilizam técnicas de Inteligência Artificial, mas houve um aumento significativo de interesse a partir de 2019, principalmente no uso de aprendizado de máquina e aprendizado de máquina profundo. No entanto, mesmo nos trabalhos a partir de 2019, não foram encontradas abordagens de CD para lidar com OSN ou redes dinâmicas. Com base nos resultados da revisão da literatura, identificou-se uma lacuna na área de encontrar comunidades em redes dinâmicas desbalanceadas. Esta pesquisa visa preencher essa lacuna, com foco na mudança de topologia ao longo do tempo, aplicando aprendizado por reforço profundo ao problema de detecção de comunidades em redes sociais dinâmicas. Propomos um modelo adaptativo com uma arquitetura de ator-crítico (actor-critic) baseada em aprendizado por reforço. A proposta visa maximizar a densidade de modularidade local de uma estrutura de comunidade, utilizando uma rede neural de grafos para lidar com aspectos mutáveis de grandes redes sociais. Extensos experimentos conduzidos com a arquitetura denominada Actor-Critic to Community Detection (AC2CD), utilizando conjuntos de dados dinâmicos de redes sociais do mundo real, mostraram maior precisão em comparação com as soluções apresentadas na literatura. Uma investigação mais aprofundada concluiu que a arquitetura lida bem com as redes sociais do mundo real, mesmo considerando redes com tamanhos de comunidade desbalanceados. Nossa proposta consiste na combinação de aprendizado por reforço profundo (Deep Reinforcement Learning (DRL)) com rede de atenção em grafo (Graph Attention Network (GAT)) para realizar a descoberta de comunidades em redes dinâmicas. Foi implementada uma arquitetura baseada em actor-critic, que foi validada por meio de experimentos usando conjunto de dados (datasets) que representam redes reais. A arquitetura implementada é composta por dois componentes: o ator actor e o crítico critic. Em cada componente foram utilizadas duas camadas de atenção em grafos como camadas ocultas, uma camada de dropout na entrada e uma camada de softmax na saída. Os experimentos realizados para validar o modelo utilizaram cinco datasets representando redes reais: High School, BlogCatalog3, Email-EU-Core, Flicker e Youtube2. A avaliação dos resultados foi feita com base em medidas de F-measure, como macroF1, micro-F1, além da informação mútua normalizada (Normalized Mutual Information (NMI)). Os resultados obtidos confirmaram a hipótese, demonstrando que o modelo superou as soluções da literatura, como GraphGAN, ComE, SDNE, CLARE e CNN, especialmente em termos de estabilidade diante da complexidade de conjuntos de dados como Flickr ou Youtube. Também foi conduzido um experimento para avaliar o desempenho ao utilizar duas implementações de redes neurais em grafo (Graph Neural Network (GNN)), GAT e rede convolucional em grafo (Graph Convolution Network (GCN)). Foi observado que ambas implementações são equivalentes para o problema de CD, com uma variação de no máximo 0.08 na métrica de NMI no conjunto de dados High School. Além disso, o desempenho alcançado é em grande parte atribuído ao uso de modelo de aprendizado por reforço com arquitetura actor-critic.