Metaheurísticas para detecção de líderes e comunidade em redes sociais

Abstract

Detecção de comunidades é um assunto que vem fascinando a comunidade científica pela necessidade de controlar o consumo e demanda de recursos e infraestruturas em sistemas complexos como são as redes sociais e a sua geração massiva de informações no atual paradigma do Big Data. Uma comunidade é definida como um conjunto de nós em uma rede que possuem propriedades similares. Em determinadas comunidades, alguns nós chamados de líderes de comunidade possuem uma grande capacidade para difundir informação e ideias. Muitos algoritmos de detecção de comunidades têm sido propostos na literatura. No entanto, poucos trabalhos têm abordado o problema de selecionar os líderes dessas comunidades. Nesse sentido, algoritmos como o Leader Rank, LCDA 1 e LCDA 2 foram desenvolvidos com esse propósito. Nesse trabalho propomos quatro novos algoritmos baseados na metaheurística GRASP e GRASP Reativo que utilizam adaptações do LCDA na fase de construção. Além destes algoritmos, desenvolvemos um método de avaliação da qualidade de detecção de comunidade e líderes de algoritmos através da geração de redes sintéticas que contém essas estruturas de comunidade e liderança. Os resultados experimentais mostram que, a qualidade da solução para a detecção de líderes e comunidades em redes sociais com os algoritmos propostos performam eficientemente e são tão competitivos como os relatados atualmente na literatura. Além disto, nosso gerador apresenta possibilidades de estruturas de grafos, trazendo uma representação de diversas topologias de grafos/redes, além de incluir e revelar como a estrutura de liderança influência na estrutura de comunidade e vice-versa.