Share
Embed
Representações implícitas probabilísticas de grafos
Apresentado no II ETC/CSBC
Juan Lopes
November 25, 2017
Transcript
35 slides
-
REPRESENTAÇÕES DE GRAFOS IMPLÍCITAS PROBABILÍSTICAS Ç JUAN P. A. LOPES
FABIANO DE S. OLIVEIRA PAULO E. D. PINTO DICC/IME/UERJ -
Uma representação é ótima se requer O(f(n)) bits para representar
uma classe contendo 2ϴ(f(n)) grafos de n vértices. Jeremy P SPINRAD. Efficient graph representations. American mathematical society, 2003. John Harold MULLER. Local structure in graph classes, 1988. Sampath KANNAN, Moni NAOR, e Steven RUDICH. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 1992. -
1 3 2 5 4 1 2 3 4 5
2 1 3 2 2 4 1 3 3 5 LISTA DE ADJACÊNCIA 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 2 3 4 5 1 2 3 4 5 MATRIZ DE ADJACÊNCIA -
0 1 1 0 1 1 0 1 0 1
1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 2 3 4 5 1 2 3 4 5 MATRIZ DE ADJACÊNCIA 1 3 2 5 4 -
1 3 2 5 4 ESTE É O #42 1
3 2 5 4 ESTE É O #41 1 3 2 5 4 ESTE É O #43 -
REPRESENTAÇÃO IMPLÍCITA Versão generalizada de Spinrad • ASSINTOTICAMENTE ÓTIMA O(f(n))
bits para representar uma classe com 2ϴ(f(n)) grafos de n vértices; • DISTRIBUI INFORMAÇÃO ENTRE OS VÉRTICES Cada vértice precisa de O(f(n)/n) bits para representar a adjacência; • TESTE DE ADJACÊNCIA É LOCAL Para testar a adjacência entre dois vértices, apenas informações locais são usadas. -
REPRESENTAÇÃO IMPLÍCITA Versão generalizada de Spinrad • ASSINTOTICAMENTE ÓTIMA O(f(n))
bits para representar uma classe com 2ϴ(f(n)) grafos de n vértices; • DISTRIBUI INFORMAÇÃO ENTRE OS VÉRTICES Cada vértice precisa de O(f(n)/n) bits para representar a adjacência; • TESTE DE ADJACÊNCIA É LOCAL Para testar a adjacência entre dois vértices, apenas informações locais são usadas. • TESTE DE ADJACÊNCIA É PROBABILÍSTICO Possui uma probabilidade relativa fixa de causar falsos positivos ou falsos negativos. -
Na prática, funções hash, permitem simular uma distribuição uniforme, porém
mantendo informações sobre os dados originais. -
FILTRO DE BLOOM Permite realizar consultas de pertinência em um
conjunto com O(1) bits por elemento. • APLICAÇÃO DIRETA DA ESTRUTURA Representa-se o conjunto de arestas para permitir teste de adjacência eficiente com O(1) espaço por aresta, isto é, tão eficiente quanto a matriz de adjacência no pior caso. • EFICIENTE PARA GRAFOS ESPARSOS Apenas O(m) memória necessária para representar qualquer grafo. • ERRO RELATIVO A ESPAÇO UTILIZADO 10 bits por elemento = <1% de falsos positivos 4 bits por elemento = <15% de falsos positivos -
MINHASH Hashing sensível a localidade. • VARIÁVEL DE BERNOULLI •
ÍNDICE DE JACCARD -
MINHASH Hashing sensível a localidade. • CADA FUNÇÃO DEFINE UM
ESTIMADOR NÃO-ENVIESADO • MÚLTIPLOS ESTIMADORES COMPÕEM UMA ASSINATURA • COMPARAÇÃO DE ASSINATURAS -
MINHASH Hashing sensível a localidade. h 1 A 197 98
11 86 Arthur Dent 71 82 57 204 137 68 172 6 Tricia McMillan 132 40 238 106 247 6 253 138 Zaphod Beeblebrox 225 220 229 120 71 182 221 96 Ford Prefect 237 63 209 201 11 193 29 192 Marvin 186 182 113 150 118 207 1 251 Fenchurch 80 34 116 143 h 2 h 3 h 4 h 5 h 6 h 7 h 8 11 6 1 6 MinHash(A) 71 34 57 106 CONJUNTO A -
MINHASH Hashing sensível a localidade. h 1 B 208 8
198 81 Slartibartfast 195 181 195 153 171 178 130 196 Prostetnic Vogon Jeltz 145 237 73 88 247 6 253 138 Zaphod Beeblebrox 225 220 229 120 71 182 221 96 Ford Prefect 237 63 209 201 11 193 29 192 Marvin 186 182 113 150 118 207 1 251 Fenchurch 80 34 116 143 h 2 h 3 h 4 h 5 h 6 h 7 h 8 11 6 1 81 MinHash(B) 80 34 73 88 CONJUNTO B -
MINHASH Hashing sensível a localidade. 6 MinHash(A) 71 57 106
81 MinHash(B) 80 34 73 88 6 71 57 106 81 80 73 88 11 6 1 34 11 6 1 34 -
MINHASH Representação baseada em hashing sensível a localidade 1 3
2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} {1, 2, 5, 6} {1, 2, 7, 8} {1, 3, 9, 10} {1, 5} δ A = 1/3 δ B = 1/2 -
MINHASH Representação baseada em hashing sensível a localidade 1 2
3 4 5 6 7 8 a 1 a 2 1 3 5 7 1 3 6 8 1 4 5 8 1 4 6 7 S 0000 0011 0101 0110 a 3 a 4 a 5 a 6 a 7 a 8 s δ A = 1/3 δ B = 1/2 -
MINHASH Representação baseada em hashing sensível a localidade 0 0
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 x4 x4 0 1 2 3 0 1 2 3 0 1 0 1 0 0 M[i][j] = popcount(i&j)&1; δ A = 1/3 δ B = 1/2 -
MINHASH Representação baseada em hashing sensível a localidade 1 3
2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} inicial subconjunto -
MINHASH Representação baseada em hashing sensível a localidade 1 3
2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} {1, 2, 5, 6} {1, 2, 7, 8} {1, 3, 9, 10} inicial subconjunto extensão -
MINHASH Representação baseada em hashing sensível a localidade 1 3
2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} {1, 2, 5, 6} {1, 2, 7, 8} {1, 3, 9, 10} {1, 5} inicial subconjunto extensão subconjunto -
Esta é uma representação probabilística para árvores com complexidade menor
que a melhor representação determinística. Cada vértice é representado com O(1) bits, usando b-bit MinHash. Ping LI, and Christian KÖNIG. b-Bit minwise hashing. Proceedings of the 19th international conference on World wide web. ACM, 2010. -
Uma classe hereditária C contém 2ϴ(n²) grafos de n vértices
se e somente se ela contém todos os grafos bipartidos, todos os co-bipartidos ou todos os grafos split. Jeremy P SPINRAD. Efficient graph representations. American mathematical society, 2003. -
GRAFOS BIPARTIDOS É sempre possível representá-los? 1 2 3 4
5 6 K 3,3 δ A = 0.4 δ B = 0.6 -
MODELAGEM EM PROGRAMAÇÃO INTEIRA Objetivo: mostrar que uma instância não
possui solução viável. x A x AB S A S B S C x B x C x AC x BC x ABC A B C -
TRANSFORMAÇÃO PARA BIPARTIDO Se há representação eficiente para bipartidos, co-bipartidos
ou split, há para todos os grafos. 1 3 2 5 4 1 2 3 4 5 1 2 3 4 5