An external memory algorithm for listing triangles

Abstract

Este trabalho propõe um novo algoritmo de memória externa para contagem e listagem de triângulos em grafos massivos. Outra grande contribuição é uma melhor análise do algoritmo de listagem de triângulos de memória externa proposto por Roman Dementiev [8]. Além disso, há uma revisão bibliográfica das soluções (tanto para memória interna, quanto para memória externa) para os problemas de busca, contagem e listagem de triângulos. Muitas aplicações atuais precisam processar uma quantidade imensa de dados. Lidar com esse problema é um desafio para a área de projeto de algoritmos. Algoritmos de memória externa, ou algoritmos I/O-eficientes, objetivam reduzir o número de leituras e escritas (I/Os) na mídia externa, tipicamente um disco rígido, pois o custo de um I/O para um dispositivo esterno é muito maior que um I/O realizado em memória interna. A mídia externa é utilizada para armazenar as informações que a memória principal, normalmente uma RAM (Random Access Memory), não consegue lidar por falta de espaço. Em grafos, Triângulos são conjuntos de 3 vértices tal que cada possível aresta entre eles está presente. Usualmente, o número ou a lista de triângulos em um grafo não é uma informação útil por si só. Entretanto ela pode ser utilizada para outros propósitos como o cálculo de propriedades do grafo, por exemplo, o coeficiente de clustering ou o coeficiente de transitividade; análise de redes complexas; busca de outros subgrafos especiais, por exemplo, em redes de interação entre proteínas; e também detecção de intrusão, de comunidades e de atividades de spam. Em um grafo com m arestas, a complexidade de I/O do algoritmo que propomos _e O(Scan(m3/2 )). Com o algoritmo proposto, é possível calcular o número de triângulos em um grafo com 800 milhões de arestas em pouco mais de 9 horas usando apenas 1.5GiB de memória principal.

In this work, we propose a new external memory algorithm for counting and listing triangles in huge graphs. Another major contribution is a better analysis of the external memory algorithm for listing triangles proposed by Roman Dementiev [8]. Besides that, there is a review of solutions (in internal and external memory) for the problems of nding, counting and listing triangles. Many real world applications need to process a large amount of data. Dealing with massive data is a challenge for algorithm design. The goal for external memory algorithms, or I/O-e cient algorithms, is to reduce the number of reads and writes (I/Os) to external devices, typically a hard disk, wich has a huge cost per I/O when compared to another made for internal memory. The external device is used to store informations that the main memory, usually a RAM (Random Access Memory), can not deal because it lacks of space. In a graph, a triangle is a set of three vertices such that each possible edge between them is present. Usually, the number of triangles, for example, is not an useful information by itself. However, they can be used for other purposes like the calculation of graph properties, for example, the clustering coe cient and transitivity coe cient; analysis of complex networks; nding special subgraphs, for example, in protein interaction networks; and also intrusion detection, spamming or community detection. In a graph with m edges, the I/O complexity of our proposed algorithm is O(Scan(m 3/2)). With this algorithm is possible to count the number of triangles in a graph with 800 million edges in about 9 hours using only 1.5 GiB of main memory.