Modularidade de robustez em redes complexas

Uma questão básica na detecção de comunidades em redes é quão modular uma determinada rede é. Isso é geralmente abordado avaliando a qualidade das partições detectadas na rede. A função de modularidade de Girvan-Newman (GN) é a maneira padrão de fazer essa avaliação, mas possui uma série de desvantagens. O mais importante, é que não é claramente interpretável, dado que a medida pode assumir valores relativamente grandes em partições de redes aleatórias sem comunidades. Aqui, propomos uma medida baseada no conceito de robustez: a modularidade é a probabilidade de encontrar partições triviais quando a estrutura da rede é perturbada aleatoriamente. Esse conceito pode ser implementado para qualquer algoritmo de agrupamento capaz de identificar quando uma estrutura de grupo está ausente. Testes em grafos artificiais e reais revelam que a modularidade de robustez pode ser usada para avaliar e comparar a força da estrutura comunitária de diferentes redes. Também introduzimos outras duas funções de qualidade: diferença de modularidade, uma versão adequadamente normalizada da modularidade GN, e modularidade de informação, uma medida de distância baseada na compressão de informação. Ambas as medidas estão fortemente correlacionadas com a modularidade de robustez, mas têm menor complexidade temporal, podendo ser utilizadas em redes cujo tamanho torna o cálculo da modularidade de robustez muito custoso.