Share
Embed
Big Graph: Big Data aplicado a grafos gigantes e dinâmicos
BIG GRAPH
BIG DATA APLICADO A GRAFOS GIGANTES E DINÂMICOS
Juan Lopes
May 11, 2018
Transcript
60 slides
-
BIG GRAPH BIG DATA APLICADO A GRAFOS GIGANTES E DINÂMICOS
@juanplopes 11/maio/2018 -
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 -
O Projeto Genoma Humano custou cerca de US$ 3 bilhões
ao longo de 11 anos para sequenciar completamente o DNA humano. -
$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 -
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. -
AGCTGAC GATCGGAAGA TCAG AGCTGACG ATCGGA AGATCAG AGCT GACGATCGGAAGATC AG REMONTAGEM
(DE NOVO ASSEMBLY) É preciso remontar a sequência original -
AGCTG GCTGA CTGAC CTGAC ACGAT TGACG CGATC GACGA AGCTGAC CTGACGATC
REMONTAGEM (DE NOVO ASSEMBLY) É preciso remontar a sequência original K-MER (K=5) -
... REMONTAGEM (DE NOVO ASSEMBLY) É preciso remontar a sequência
original ... ... ... ... ... ... ... ... ... ... ... ... ... https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3421212/ -
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/ -
… HABILIDADES VS TAREFAS Cada aresta representa habilidade de realizar
uma tarefa T1 T2 T3 T4 T5 T6 -
… REDES (DIVERSAS) Cada aresta representa o custo de conexão
6 2 8 1 -3 5 6 -
2 8 6 5 ÁRVORE GERADORA MÍNIMA Algoritmos: Prim, Kruskal,
Chazelle, etc... 6 1 -3 -
São muitos algoritmos! E continuam surgindo novos. Só se fala
de grafos em computação. -
• 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 -
• 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 -
Se a academia fala tanto de grafos, onde eles estão
nas aplicações comerciais? -
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 -
“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/ -
NETWORKX Biblioteca em Python para algoritmos em grafos # Copyright
(C) 2004-2018 by # Aric Hagberg <[email protected]> # Dan Schult <[email protected]> # Pieter Swart <[email protected]> # 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 -
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 -
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. -
Parte do problema de lidar com grafos gigantes é simplesmente
uma questão de representação. https://bookstore.ams.org/fim-19/ -
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 -
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 -
GRAFOS DE DEBRUIJN Permitem remontar genoma a partir de fragmentos
CTGAC TGACT TGACG TGACA TGACC TTGAC GTGAC ATGAC CTGAC Está no grafo? -
“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/ -
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 -
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). -
B C A D (-, A, C) B C A
D B C A D (+, A, D) GRAFOS DINÂMICOS -
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 -
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 -
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 -
(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 -
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 -
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 -
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 -
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 -
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