Método Rápido de Agrupamento de Vértices para Detecção de Comunidades em Redes Complexas de Larga-escala

This paper tackles the problem of community detecion in large-scale graphs. In the literature devoted to this topic, an iterative algorithm, called Louvain Method (ML), stands out as an effective and fast solution for the problem. However, the first iterations of the ML are the most costly. To overcome this, this paper introduces a fast algorithm for vertice groupping (MRAV), which can be a way faster option than the first iterations of the ML, yet similarly effective. The performance of the proposed multistage scheme for community detection, called MRAV+ML, is confronted against that of the ML using real-world networks from small to large sizes. Experimental results show that, for large-scale graphs, the MRAV+ML detects communities with mean modularity about 3% lower than the ML, but with a mean reduction of about 42% in computation time. Resumo. Este artigo reporta resultados de uma investigação sobre o problema de detecção de comunidades em redes complexas. Na literatura dedicada a esse assunto, um algoritmo iterativo, denominado Método de Louvain (ML), se destaca como opção eficaz e rápida para o problema. Entretanto, as primeiras iterações do ML são sua parte mais custosa. Neste artigo, propõe-se um Método Rápido de Agrupamento de Vértices (MRAV) em grafos como uma opção mais rápida do que as primeiras iterações do ML. Através de experimentos envolvendo redes grandes do mundo real, demonstra-se que o sistema proposto MRAV+ML identifica comunidades com modularidade similar ao ML (redução média menor de 3%), mas com redução média de aproximadamente 42% no tempo de execução. 1. Introdução Um grafo é uma estrutura composta por um conjunto de objetos que podem estar conectados por arestas indicando a existência de uma relação entre um par de objetos. Convenientemente, grafos podem então ser utilizados para representar várias redes complexas do mundo real [Bondy et al., 1976]. Grafos de grande porte podem ser criados na representação de grandes serviços como Facebook e Twitter ou em outros que são comuns em domínios como o WWW [Kwak et al., 2010, Mislove et al., 2007]. De forma similar, grandes grafos encontram aplicação na representação de redes complexas de larga-escala em diversas áreas do conhecimento. Em diversas redes complexas reais, a distribuição de arestas entre os vértices apresenta-se de forma altamente heterogênea. Isso leva, nesses casos, a uma alta concentração de arestas entre agrupamentos de vértices e uma baixa concentração de arestas entre esses agrupamentos. Essa característica de redes reais é tipicamente chamada de estrutura de comunidades. Comunidades, também chamadas de agrupamentos, são grupos de vértices que provavelmente compartilham algumas propriedades comuns ou desempenham papéis semelhantes no grafo em estudo. Nesse contexto, considerando a análise de grafos que representam redes complexas reais, um problema comum é a detecção de comunidades [Fortunato, 2010, Harenberg et al., 2014, Khan e Niazi, 2017, Zhao, 2017], que será o alvo principal de investigação deste artigo. 1.1. Detecção de comunidades em redes complexas O problema de detecção de comunidades consiste em encontrar, em um grafo, agrupamentos de vértices que possuam uma ou mais características em comum. Uma dessas características pode ser a vizinhança em comum entre vértices, que pode ser dada pelo número de arestas que os vértices de um mesmo agrupamento (i.e., uma comunidade) compartilham entre si. Várias métricas podem ser utilizadas para avaliar os agrupamentos e as semelhanças existentes em cada comunidade [Chakraborty et al., 2017]. Nesse contexto, uma métrica muito utilizada para avaliar a qualidade das comunidades é a modularidade Q [Girvan e Newman, 2002, Newman, 2006]. Intuitivamente, −1 < Q < 1 é uma medida do quão densamente conectados entre si estão os vértices do mesmo tipo ou classe. O valor de Q se torna mais positivo (resp. negativo) quanto maior (resp. menor) for o número de arestas conectando vértices de uma mesma classe, se comparado com uma distribuição aleatória de arestas entre os mesmos vértices. O problema de detecção de comunidades, pode ser tratado como um problema de maximização da modularidade das partições encontradas em um grafo. Formalmente, a modularidade é dada por [Girvan e Newman, 2002, Newman, 2006]: