Implementação do algoritmo de Newman para identificação de comunidades em placas gráficas

Abstract

Communities are present on physical, chemical and biological systems and their identification is fundamental for the comprehension of the behavior of these systems. Recently, available data related to complex networks have grown exponentially, demanding more computational power. The Graphical Processing Unit (GPU) is a cost effective alternative suitable for this purpose. We investigate the convenience of this for network science by proposing a GPU based implementation of Newman community detection algorithm. We showed that the processing time of matrix multiplications of GPUs grow slower than CPUs in relation to the matrix size. It was proven, thus, that GPU processing power is a viable solution for community dentification simulation that demand high computational power. Our implementation was tested on an integrated biological network for the bacterium Escherichia coli

Comunicadades estão presentes nos mais diversos sistemas sejam eles físicos, químicos ou biológicos, e a identificação destas é fundamental para a compreensão do comportamento desses sistemas. Recentemente, a quantidade de dados relacionado a redes complexas tem crescido exponencialmente, demandado mais poder computacional. As placas de processamento de vídeo (GPUs) são uma alternativa com bom custo-benefício adequada para este propósito. Nós investigamos a convivência dessa solução para a ciências de redes propondo uma implementação do algoritmo de Newman baseada em GPU para a detecção de comunidades. Mostramos que o tempo de processamento de multiplicação de matrizes em GPU cresce menos rapidamente que o da CPU em relação ao tamanho da matriz. Desta forma, foi demonstrado que o processamento em GPU é uma alternativa viável para simulações de identificação comunidades que exijam alta capacidade computacional. Nossa implementação foi testada em uma rede biológica integrada para a bactéria Escherichia coli