Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
Sem resumo de edição |
||
Linha 3:
=== Detecção de Ciclos por Busca em Profundidade ===
Um método eficiente para detectar ciclos em grafos direcionados é por meio do algoritmo de busca em profundidade. Intuitivamente, o algoritmo começa num nó raiz (selecionando algum nó como sendo o raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder <ref name="wikiDFS">http://pt.wikipedia.org/wiki/Busca_em_profundidade</ref><ref name="Cormen">Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, ''Introduction to Algorithms'', The MIT Press, 3rd Ed. (2009).</ref>.
Formalmente, um algoritmo de busca em profundidade realiza uma busca não-informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não possui filhos (nó folha). Então a busca retrocede e começa no próximo nó. Numa implementação não-recursiva, todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração<ref name="wikiDFS"/>.
==== Pseudo-Código ====
Linha 28:
==== Análise do Algoritmo ====
A ordem de complexidade em relação ao custo de tempo de execução do algoritmo de detecção de ciclos por busca em profundidade é Θ(|V| + |E|), onde |V| é o número de vértices do grafo e |E| o número de arestas<ref name="Cormen" />. O custo de armazenamento (espaço em memória) do algoritmo é Θ(|V|).
=== Detecção de Ciclos no Contexto de Dados Massivos ===
Linha 34:
No contexto de dados massivos, a estrutura do grafo pode ser grande o suficiente para saturar facilmente o poder de processamento ou a capacidade de memória de uma única máquina, surgindo a necessidade de paralelizar o algoritmo de detecção de ciclos. Entretanto, principalmente devido à sua característica recursiva, uma desvantagem do algoritmo de busca em profundidade é o fato de ser dificilmente paralelizável, embora o algoritmo seja assintoticamente ótimo.
Portanto, é necessário um algoritmo que divida o problema de detecção de ciclos em subproblemas entre nós de computação, de modo que os nós busquem por cíclos de maneira paralela, garantindo que todos os ciclos serão encontrados. Propõe-se então, um algoritmo para detecção de ciclos de grafo por passagem de mensagens<ref name="ROCHARodrigoCO">ROCHA, Rodrigo C. O., ''A Method of Searching Sociable Numbers Using Graph Theory: An Implementation on Large Computer Clusters'', (2013).</ref> entre os vértices, baseado no modelo Pregel<ref name="Pregel">Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser and Grzegorz Czajkowski, ''Pregel: a system for large-scale graph processing'', Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD '10 (2010), 135--146.</ref> de processamento de grafos da Google. Esse modelo apresenta uma abordagem centrada nos vértices em que os vértices do grafo trabalham juntos para detectar ciclos.
== Algoritmo de Detecção de Ciclos por Passagem de Mensagens ==
Linha 44:
Para cada lista recebida, se o vértice receber uma lista contendo a si próprio em qualquer posição exceto a primeira, o vértice rejeita a mensagem. Se a lista recebida começar com o próprio vértice, então um ciclo foi detectado. Para as demais listas recebidas, o vértice se adiciona ao final da lista e a encaminha para todos os seus vizinhos.
Por definição, temos que
A seguir é apresentado um exemplo da execução do algoritmo de detecção de ciclos por passagem de mensagens. Pode-se observar que no passo (d), o vértice 2 recebe uma mensagem em que a lista de vértices é iniciada pelo próprio vértice 2, detectando assim um ciclo no grafo (2,3,4). No passo (e), o vértice 2 rejeita uma mensagem contendo a si próprio na segunda posição da lista. Pode-se notar que a lista rejeitada contém o ciclo detectado anteriormente, e é por esse motivo que o vértice 2 aparece no meio da lista rejeitada, pois o ciclo é um sub-caminho do caminho representado pela lista rejeitada no passo (e). Por fim, no passo (f) todos os vértices são desativados e não existem mais mensagens sendo enviadas pelo grafo, terminando a execução do algoritmo.
Linha 54:
==== Análise do Algoritmo ====
O número total de iterações do algoritmo paralelo será igual ao tamanho do maior caminho de vértices distintos do grafo mais algumas poucas iterações iniciais ou finais. Portanto o número de iterações do algoritmo paralelo será Θ(|V|), sendo que o maior caminho distinto possível de um grafo seria contendo todos os vértices do grafo<ref name="ROCHARodrigoCO"/>.
==== Pseudo-Código no Modelo Pregel de Programação Paralela ====
Linha 86:
==== Implementação Paralela no Sistema GraphChi ====
Considerando que a implementação principal do modelo Pregel da Google possui código fechado, pode ser interessante avaliar uma alternativa ao modelo Pregel. Uma das alternativas é o sistema GraphChi<ref name="GraphChi">Aapo Kyrola, Guy Blelloch, and Carlos Guestrin, ''GraphChi: Large-scale graph computation on just a PC'', OSDI (2012).</ref> da GraphLab. Esse sistema fornece uma ''engine'' para processamento de grafos, no contexto de dados massivos, em uma única máquina. O sistema apresenta um processamento baseado em disco (memória secundária) para computação eficiente de grafos de grande escala.
Diferentemente do modelo Pregel, GraphChi é uma ''engine'' baseada em memória compartilhada. Em GraphChi, cada vértice e cada aresta armazena um dado. A comunicação entre os vértices durante o processamento paralelo é realizada com base nos dados armazenados pelos vértices e arestas.
Linha 265:
== Experimentos ==
Os experimentos foram realizados em uma aplicação de exemplo, usado a implementação do sistema GraphChi, para encontrar grupos de números sociáveis<ref name="ROCHARodrigoCO"/>, também chamados de ''aliquot cycles'', estudados em Teoria dos Números. O grafo é uma representação de um subconjunto dos números naturais relacionados pela soma dos seus divisores próprios, também chamada de ''aliquot sum''.
Grupos sociáveis são ocorrências raras nos números naturais. O primeiro grupo sociável de ordem maior ou igual a dois é o par amigável (220, 284), o segundo grupos sociável é (1184, 1210).
Linha 292:
Para esse grafo de 18109729 vértices, basicamente representando o intervalo de números naturais [0, 18109729], foram encontrados 78 grupos sociáveis de ordem maior ou igual a dois.
== Referências ==
<references/>
| |||