Big Graph: Big Data aplicado a grafos gigantes e dinâmicos

BIG GRAPH
BIG DATA APLICADO A GRAFOS GIGANTES E DINÂMICOS

Transcript

1. BIG GRAPH BIG DATA APLICADO A GRAFOS GIGANTES E DINÂMICOS @juanplopes 11/maio/2018
2. VANITY SLIDE Acho que é obrigatório, né? R&D SOFTWARE ENGINEER INTELIE (a RigNet company) DOUTORANDO EM ALGORITMOS COPPE/UFRJ JUAN LOPES, PAPAI DO MIGUEL @juanplopes
3. PROJETO GENOMA HUMANO 1990-2001
4. O Projeto Genoma Humano custou cerca de US$ 3 bilhões ao longo de 11 anos para sequenciar completamente o DNA humano.
5. $100M $10M $1M $100k $10k $1k ‘01 ‘02 https://www.genome.gov/27541954/dna-sequencing-costs-data/ ‘03 ‘04 ‘05 ‘06 ‘07 ‘08 ‘09 ‘10 ‘11 ‘12 ‘13 ‘14 ‘15 ‘16 ‘17 CUSTO DE SEQUENCIAMENTO Genoma Humano LEI DE MOORE
6. Atualmente, é possível realizar sequenciamento parcial do próprio DNA por até US$ 99.
7. Shotgun Sequencing é um método de sequenciamento que quebra a cadeia em pontos aleatórios, fáceis de ler, e depois reagrupa as leituras computacionalmente.
8. ...AGCTGACGATCGGAAGATCAG... O sequenciador quebra a cadeia em vários pontos aleatórios.
9. AGCTGAC GATCGGAAGA TCAG AGCTGACG ATCGGA AGATCAG AGCT GACGATCGGAAGATC AG REMONTAGEM (DE NOVO ASSEMBLY) É preciso remontar a sequência original
10. AGCTG GCTGA CTGAC CTGAC ACGAT TGACG CGATC GACGA AGCTGAC CTGACGATC REMONTAGEM (DE NOVO ASSEMBLY) É preciso remontar a sequência original K-MER (K=5)
11. ... REMONTAGEM (DE NOVO ASSEMBLY) É preciso remontar a sequência original ... ... ... ... ... ... ... ... ... ... ... ... ... https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3421212/
12. Humano 3.3 bilhões de pares (600GB) Drosófila 123 milhões de pares (22GB) Psilotum nudum 250 bilhões de pares (45TB) http://www.biology-pages.info/G/GenomeSizes.html https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5411771/
13. MAS AFINAL, O QUE SÃO GRAFOS?! Você quis dizer: gráficos?
14. LEONHARD EULER 1707-1783
15. SETE PONTES DE KÖNIGSBERG (atual Kaliningrad)
16. SETE PONTES DE KÖNIGSBERG (atual Kaliningrad)
18. Grafos modelam relações. VÉRTICE/NÓ ARESTA/ARCO
19. PODEM MODELAR CIDADES Cada vértice representa a interseção de duas ruas
20. CAMINHO MAIS CURTO Algoritmos: Dijkstra, Bellman-Ford, Floyd-Warshall, etc...
21. DETECÇÃO DE PONTES Algoritmo: Tarjan
22. … SEQUÊNCIAS DE TAREFAS Cada aresta (dirigida) representa uma dependência T1 T2 T3 T4 T5 T6
23. ORDENAÇÃO TOPOLÓGICA Algoritmo: Khan T1 T2 T3 T4 T5 T6
24. … HABILIDADES VS TAREFAS Cada aresta representa habilidade de realizar uma tarefa T1 T2 T3 T4 T5 T6
25. EMPARELHAMENTO MÁXIMO Algoritmos: Ford-Fulkerson, Edmonds-Karp, Dinic, etc... T1 T2 T3 T4 T5 T6
26. … REDES (DIVERSAS) Cada aresta representa o custo de conexão 6 2 8 1 -3 5 6
27. 2 8 6 5 ÁRVORE GERADORA MÍNIMA Algoritmos: Prim, Kruskal, Chazelle, etc... 6 1 -3
28. … REDES (2) Cada aresta representa um link
29. CORTE MÍNIMO S-T (max-flow min-cut theorem) Algoritmos: Ford-Fulkerson, Edmonds-Karp, Dinic, etc...
30. São muitos algoritmos! E continuam surgindo novos. Só se fala de grafos em computação.
31. • Deletion Graph Problems Based on Deadlock Resolution • Número de Ramsey relativo a arestas de potências de caminhos • Uma Aproximação para o Problema de Alocação de Terminais com Capacidade • Representações Implícitas Probabilísticas de Grafos • Vertex-disjoint path covers in graphs • Biclique edge-choosability in some classes of graphs • Facility Leasing with Penalties • Advances in Anti-Ramsey Theory for random graphs • Método Exato para um Problema de Alocação Justa • Hitting all longest cycles in a graph • Coloração arco-íris em grafos resultantes de produto cartesiano • Um algoritmo exato para biclique-coloração • Edge-colouring of triangle-free graphs with no proper majors • Modelos para o Problema de Alocação de Pedágios • Uma versão algoritmica do Lema Local de Lovász • Análise dos Tempos de Setup Dependentes da Sequência em… • New Insights on Prize Collecting Path Problem • Tight bounds for gap-labellings • Grafos do tipo Half Cut • The 1,2,3-Conjecture for powers of paths and powers of cycles ENCONTRO DE TEORIA DA COMPUTAÇÃO CSBC 2017: Somente os 20 primeiros papers http://csbc2017.mackenzie.br/eventos/2-etc
32. • Deletion Graph Problems Based on Deadlock Resolution • Número de Ramsey relativo a arestas de potências de caminhos • Uma Aproximação para o Problema de Alocação de Terminais com Capacidade • Representações Implícitas Probabilísticas de Grafos • Vertex-disjoint path covers in graphs • Biclique edge-choosability in some classes of graphs • Facility Leasing with Penalties • Advances in Anti-Ramsey Theory for random graphs • Método Exato para um Problema de Alocação Justa • Hitting all longest cycles in a graph • Coloração arco-íris em grafos resultantes de produto cartesiano • Um algoritmo exato para biclique-coloração • Edge-colouring of triangle-free graphs with no proper majors • Modelos para o Problema de Alocação de Pedágios • Uma versão algoritmica do Lema Local de Lovász • Análise dos Tempos de Setup Dependentes da Sequência em… • New Insights on Prize Collecting Path Problem • Tight bounds for gap-labellings • Grafos do tipo Half Cut • The 1,2,3-Conjecture for powers of paths and powers of cycles ENCONTRO DE TEORIA DA COMPUTAÇÃO CSBC 2017: Somente os 20 primeiros papers Em laranja os que são diretamente sobre grafos. Em vermelho os que usam teoria de grafos para resolver algum problema. http://csbc2017.mackenzie.br/eventos/2-etc
33. Se a academia fala tanto de grafos, onde eles estão nas aplicações comerciais?
34. EMPRESA FAZ PARCERIA COM Mais perto do que você imagina.
36. https://neo4j.com/blog/graph-compute-neo4j-algorithms-spark-extensions/ MATCH (actor:Person)-[:ACTED_IN]->(movie:Movie) WHERE movie.title STARTS WITH "T" RETURN movie.title AS title, collect(actor.name) AS cast ORDER BY title ASC LIMIT 10; CYPHER Neo4j declarative query language
37. “Neo4j is optimized for online transaction processing (OLTP) and is intended to be used as your primary database. While it wasn’t built specifically with the intention of being used for graph compute or analytics, a lot of customers and open-source users are using Neo4j for those purposes.” https://neo4j.com/blog/graph-compute-neo4j-algorithms-spark-extensions/
38. NETWORKX Biblioteca em Python para algoritmos em grafos # Copyright (C) 2004-2018 by # Aric Hagberg <hagberg@lanl.gov> # Dan Schult <dschult@colgate.edu> # Pieter Swart <swart@lanl.gov> # All rights reserved. # BSD license. import matplotlib.pyplot as plt from networkx import nx G = nx.lollipop_graph(4, 6) pathlengths = [] print("source vertex {target:length, }") for v in G.nodes(): spl = dict(nx.single_source_shortest_path_length(G, v)) print('{} {} '.format(v, spl)) for p in spl: pathlengths.append(spl[p]) print('') print("average shortest path length %s" % (sum(pathlengths) / len(pathlengths))) # histogram of path lengths dist = {} for p in pathlengths: if p in dist: dist[p] += 1 else: dist[p] = 1 print('') print("length #paths") verts = dist.keys() for d in sorted(verts): print('%s %d' % (d, dist[d])) print("radius: %d" % nx.radius(G)) print("diameter: %d" % nx.diameter(G)) print("eccentricity: %s" % nx.eccentricity(G)) print("center: %s" % nx.center(G)) print("periphery: %s" % nx.periphery(G)) print("density: %s" % nx.density(G)) nx.draw(G, with_labels=True) plt.show() https://networkx.github.io/documentation/stable/auto_examples/basic/plot_properties.html
39. GRAPHVIZ Ferramenta para layout visual de grafos graph { rankdir=LR; a -- { b c d }; b -- { c e }; c -- { e f }; d -- { f g }; e -- h; f -- { h i j g }; g -- k; h -- { o l }; i -- { l m j }; j -- { m n k }; k -- { n r }; l -- { o m }; m -- { o p n }; n -- { q r }; o -- { s p }; p -- { s t q }; q -- { t r }; r -- t; s -- z; t -- z; { rank=same; b, c, d } { rank=same; e, f, g } { rank=same; h, i, j, k } { rank=same; l, m, n } { rank=same; o, p, q, r } { rank=same; s, t } } https://graphs.grevian.org/example
40. DINÂMICOS Grafos em tempos de BigData são GIGANTES e Bilhões de vértices. Trilhões de arestas. m = O(n²). Inserção e remoção de vértices e arestas. Poucos algoritmos.
41. Parte do problema de lidar com grafos gigantes é simplesmente uma questão de representação. https://bookstore.ams.org/fim-19/
42. D B C A D Matriz de adjacência REPRESENTAÇÕES DE GRAFOS Cada uma tem vantagens e desvantagens O(n²) bits Lista de adjacência O(m log n) bits A B C D D C C C B C B A A B A B C D 1 0 0 1 1 1 1 0 1 0 1 1 0 C B A 1 1 0
43. A B C D E F F B E A C REPRESENTAÇÕES DE GRAFOS Classes diferentes podem ter diferentes representações ótimas D A B B A E O(n log n) bits
44. GRAFOS DE DEBRUIJN Permitem remontar genoma a partir de fragmentos CTGAC TGACT TGACG TGACA TGACC TTGAC GTGAC ATGAC CTGAC Está no grafo?
45. “We relate changes in local and global graph connectivity to the false positive rate of the underlying Bloom filters and show that the graph’s global structure is accurate for false positive rates of 15% or lower, corresponding to a lower memory limit of approximately 4 bits per graph node.” https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3421212/
46. SPANNERS E SPARSIFIERS Aproximam grafos densos através de grafos esparsos B C D E F H A G B C D E F H A G
47. Cut sparsifier Preserva o peso dos cortes do grafo. Spanner Preserva os caminhos mais curtos. Spectral sparsifier Preserva propriedades da matriz laplaciana do grafo (inclui os cortes).
48. B C A D (-, A, C) B C A D B C A D (+, A, D) GRAFOS DINÂMICOS
49. CONECTIVIDADE DETECÇÃO DE BIPARTIDOS k-CONECTIVIDADE ÁRVORE GERADORA MÍNIMA EMPARELHAMENTO MÁXIMO
50. CONECTIVIDADE EPSTEIN, 1992 Atualização: O(√n) Consulta: O(log n) Memória: O(m) HOLM, 1998 Atualização: O(log² n), Consulta: O(log n) Memória: O(m) Amortizada https://dl.acm.org/citation.cfm?id=2627694
51. CONECTIVIDADE EPSTEIN, 1992 Atualização: O(√n) Consulta: O(log n) Memória: O(m) HOLM, 1998 Atualização: O(log² n), Consulta: O(log n) Memória: O(m) Amortizada KAPRON, 2013 Atualização: O(log⁵n) Consulta: O(log² n) Memória: O(n log³n) https://dl.acm.org/citation.cfm?id=2627694
52. CONECTIVIDADE EPSTEIN, 1992 Atualização: O(√n) Consulta: O(log n) Memória: O(m) HOLM, 1998 Atualização: O(log² n), Consulta: O(log n) Memória: O(m) Amortizada AHN, 2012 Atualização: O(log²n) Consulta: O(n log² n) Memória: O(n log³n) https://dl.acm.org/citation.cfm?id=2627694
53. (x, +1) (y, -5) (y, +3) (z, -4) ℓ0-sampler z = -4 (y, +2) Representa um vetor de n posições com O(log²n) memória e permite sortear a qualquer momento uma coordenada não-nula. https://dl.acm.org/citation.cfm?id=1083599
54. B C D E F H A G ESTE GRAFO NÃO É CONEXO https://dl.acm.org/citation.cfm?id=2095156 https://people.cs.umass.edu/~mcgregor/papers/12-dynamic.pdf
55. B C D E F H A G PARTINDO DO GRAFO VAZIO https://dl.acm.org/citation.cfm?id=2095156 https://people.cs.umass.edu/~mcgregor/papers/12-dynamic.pdf
56. B C D E F H A G UMA ARESTA É SORTEADA PARA CADA VÉRTICE https://dl.acm.org/citation.cfm?id=2095156 https://people.cs.umass.edu/~mcgregor/papers/12-dynamic.pdf
57. B C D E F H A G MAIS UMA VEZ https://dl.acm.org/citation.cfm?id=2095156 https://people.cs.umass.edu/~mcgregor/papers/12-dynamic.pdf
58. B C D E F H A G ESTA É UMA FLORESTA GERADORA DO GRAFO É fácil demonstrar que este algoritmo precisa de O(log n) passos no máximo. https://dl.acm.org/citation.cfm?id=2095156 https://people.cs.umass.edu/~mcgregor/papers/12-dynamic.pdf
59. REPRESENTAÇÕES COMPACTAS ALGORITMOS PARALELIZÁVEIS ESTRUTURAS PROBABILÍSTICAS CONSTRUÇÃO INCREMENTAL
60. DÚVIDAS? Estes slides estão disponíveis em juanlopes.net/qconsp2018