Detecção de Network Motifs

Transcrição

Vinícius Rosa Máximo
Trabalho de conclusão de curso apresentado ao
Instituto de Ciência e Tecnologia – UNIFESP,
como parte das atividades para obtenção do
título de Bacharel em Ciência da Computação.
Orientador: Prof. Dr. Arlindo Flavio da Conceição
Co-orientador: Prof. Dr. Luis Augusto Angelotti Meira
São José dos Campos – SP
março, 2013
Trabalho de conclusão de curso apresentado ao
Instituto de Ciência e Tecnologia – UNIFESP,
como parte das atividades para obtenção do
título de Bacharel em Ciência da Computação.
Orientador: Prof. Dr. Arlindo Flavio da Conceição
Co-orientador: Prof. Dr. Luis Augusto Angelotti Meira
Banca Examinadora:
——————————————
Prof. Dr. Arlindo Flavio da Conceição
——————————————
Prof. Dr. Luis Augusto Angelotti Meira
——————————————
Prof. Dr. Reginaldo Massanobu Kuroshu
Aprovado em:
À minha esposa e aos meus pais.
Agradecimentos
Agradeço a Deus por ter me dado saúde, paz e força para lutar.
Aos meus pais por todo amor, carinho e pelos exemplos de perseverança e de garra que foram
essenciais para a minha formação.
À minha esposa pela compreensão e pelo imenso apoio durante toda a graduação.
Ao meu irmão pelo companheirismo e amizade.
Aos meus orientadores pela confiança, paciência e boa convivência.
Aos professores pela educação que com grande sabedoria me foi transmitida.
Aos meus amigos de turma pelos bons momentos de descontração e às infindáveis horas de
estudo.
Resumo
Motifs se tornou um tópico de pesquisa após Milo et al.
publicarem seu resultados na revista Science no ano de 2002.
Sua descoberta permitiu caracterizar uma rede por meio de Motifs que são blocos elementares de redes complexas. O problema de Detecção de Network Motifs é uma tarefa de elevado custo computacional.
Neste trabalho são abordadas algumas estratégias utilizadas pelos melhores algoritmos disponíveis atualmente, bem como suas vantagens e
desvantagens. Também será apresentado o acc-Motif que é um novo algoritmo para enumeração exata de padrões isomorfos implementado para
Motifs de tamanho 3 e 4. Este algoritmo utiliza técnicas de otimização
combinatória e seu desempenho é bastante expressivo em comparação
aos outros algoritmos.
N
Etwork
Palavras-chave: Network Motifs, Redes Complexas, Enumeração de
Subgrafos, Detecção de Motifs, Motifs, Subgrafos isomorfos, Problema
de Isomorfismo em Grafos, acc-Motif.
i
Abstract
Motifs has become a research topic after Milo et al. publish their results in the journal Science in 2002. His discovery led to characterize a network through Motifs that are Simple Building Blocks of Complex Networks. The problem Detection of
Network Motifs is a task of high computational cost. This paper discusses
some strategies used by the best algorithms currently available, as well as
its advantages and disadvantage.Also featured will be acc-Motif is a new
algorithm for exact enumeration of isomorphic patterns implemented for
Motifs of size 3 and 4. This algorithm uses combinatorial optimization
techniques and their performance is quite expressively compared to other
algorithms.
N
Etwork
Keywords: Network Motifs, Complex Networks, Counting Motifs, Enumerating subgraphs, Detection Motifs, Motifs, Subgraphs isomorphic,
Graph isomorphism problem, acc-Motif.
iii
Sumário
Resumo
i
Abstract
iii
1 Introdução
1.1 Definição do Problema .
1.2 Solução para o Problema
1.3 Objetivos . . . . . . . .
1.4 Organização do texto . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
4
5
7
7
2 Network Motifs
2.1 Frequência de subgrafos . . . . . . . . . . . . . . . . . . . .
2.2 Classificação dos algoritmos . . . . . . . . . . . . . . . . . .
2.3 Enumeração de subgrafos . . . . . . . . . . . . . . . . . . . .
2.3.1 Algoritmo de Força Bruta . . . . . . . . . . . . . . .
2.3.2 Algoritmo Elementar . . . . . . . . . . . . . . . . . .
2.4 Classificação quanto ao isomorfismo . . . . . . . . . . . . . .
2.4.1 Algoritmo de Força Bruta . . . . . . . . . . . . . . .
2.4.2 Algoritmo de Força Bruta com Refinamento Estrutural
2.4.3 Isomorfismo Polinomial . . . . . . . . . . . . . . . .
2.4.4 Primeira Função de hash: Assinatura de Grau . . . . .
2.4.5 Assinatura de Grau com Permutação . . . . . . . . . .
2.4.6 Gradiente . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Geração de Grafos Aleatórios . . . . . . . . . . . . . . . . . .
2.5.1 Primeira Abordagem . . . . . . . . . . . . . . . . . .
2.5.2 Segunda Abordagem . . . . . . . . . . . . . . . . . .
2.6 Identificação de Motifs . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
9
10
11
11
11
14
16
16
19
21
23
26
29
29
29
31
3 Algoritmo acc-Motif para k=3
3.1 Grafos não direcionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Grafos direcionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
35
39
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3
Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Avaliação em grafos aleatórios . . . . . . . . . . . . . . . . . . . . . .
45
48
4
Algoritmo acc-Motif para k=4
4.1 Grafos não direcionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Grafos direcionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
52
57
62
5
Conclusão
5.1 Comparativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
68
69
69
Referências Bibliográficas
71
A Tabela de Resultados
75
vi
C APÍTULO
1
Introdução
Network Motifs ganhou notoriedade após Milo et al. [15] publicarem seus resultados na revista
Science no ano de 2002. De lá até os dias de hoje, o conceito vem sendo utilizado em muitas
áreas da ciência, em especial em biologia e bioinformática [9, 10, 12, 19].
O uso de Motifs não se reduz a bioinformática. Em [25], Yang et al. usam o conceito de
Network Motifs para remover ambiguidade na busca de informações de uma pessoa na Web.
A informação utilizada para construir a rede é formada pela estrutura da página e pelos seus
links. Em outro trabalho, Lin, Guanqun e Li [11] utilizam o conceito de Motifs em programas
de computadores. Após comparar 110 programas desenvolvidos segundo o modelo de software
livre, os autores detectaram três tipos distintos de rede, criando um agrupamento dos programas
em três blocos. Em [1], Allan et al. usam o conceito de Network Motifs para analisar tráfego
em uma rede de computadores.
No que se refere a resolução do problema e não à sua aplicação, Network Motifs é um
tema de pesquisa. Em [13], Marcus et al. mostraram métodos para contar Motifs de maneira
eficiente. Em [22], Wang et al. apresentaram um algoritmo paralelo para encontrar Motifs
usando um cluster paralelo.
Este tema tem muita aplicação na área biológica, principalmente nas redes regulatórias de
genes ou interações entre as proteínas também chamando de PPI (protein–protein interaction)
[15, 24]. Milo mostrou que tanto em redes biológicas quanto não biológicas existem pequenos padrões topológicos que são tão frequentes que seria improvável que acontecessem com a
1
2
mesma frequência em grafos aleatórios. Diferentes tipos de redes tendem a ter diferentes conjuntos de estruturas básicas chamadas de Network Motifs. Estes padrões são considerados como
“blocos elementares de redes complexas”.
Redes complexas ocorrem em diversas áreas do conhecimento. Por exemplo, uma rede pode
representar uma cadeia alimentar, onde cada vértice é uma espécie e uma aresta direcionada de
a para b significa que a espécie a se alimenta da espécie b, por exemplo a → b.
Dentro de uma rede podemos contar o número de ocorrências de cada padrão. Por exemplo,
se a se alimenta de b e b se alimenta de c temos o padrão a → b → c, também chamado de
Cadeia de Três, conforme mostra a Figura 1.1. Por outro lado, se a se alimenta de b e de c, e b e c
se alimenta de d, temos um padrão conhecido como Dois em Paralelo, conforme ilustra a Figura
1.1. Em uma cadeia alimentar, esperamos encontrar muito o padrão a → b → c, pois representa
uma transferência de energia e de nutriente, cada nível trófico passa para o nível seguinte parte
da energia que adquiriu. A presença do padrão Dois em Paralelo indica que duas espécies que
são presas do um mesmo predador ambas tendem a compartilhar a mesma presa. Com base em
sete ecossistemas distintos incluindo habitats aquáticos e terrestres, Milo [15] identificou que
os padrões descritos na Figura 1.1 ocorreram com uma frequência extremamente alta. Estes
padrões indicam comportamentos e tendências em uma cadeia alimentar.
a
a
b
c
c
b
d
Cadeia de Três
Dois em Paralelo
Figura 1.1: Representação dos padrões mais comuns em cadeias alimentares.
Outro exemplo de redes complexas ocorre na representação de conexões neurais. Os vértices são representados pelos neurônios e as arestas pelas conexões sinápticas. Nestas redes
ocorrem com maior frequência os padrões Circuito de Alimentação Direta e Duplo Ventilador
conforme ilustrado na Figura 1.2. Redes neurais tendem a funcionar como meio de transporte
para informações entre os componentes sensoriais. O padrão Circuito de Alimentação Direta
desempenha uma função importante no processamento da informação. Geralmente os nós de
entrada são neurônios sensoriais, assim as informações só serão propagadas se a entrada se
manter constante. Por exemplo, suponhamos que a receba uma informação e a repasse para b e
Capítulo 1. Introdução
3
b a repasse para c, o neurônio c só transmitirá a informação se a continuar constante, caso contrário podemos considerar que a informação recebida por c foi apenas um ruído. Esta estrutura
tem a finalidade de filtrar possíveis flutuações de entrada ou variações no ambiente.
a
b
c
Circuito de Alimentação Direta
a
b
d
c
Duplo Ventilador
Figura 1.2: Representação dos padrões que ocorrem com maior frequência em redes neurais.
Em uma rede World Wide Web, podemos representar os vértices como sendo os sites e as
arestas representando os links. Neste tipo de rede, por exemplo, ocorre uma alta frequência de
padrões de três vértices onde existe um link ligando todos os vértices nos dois sentidos conforme
Figura 1.3. Este padrão é chamado de Triângulo Completamente Conectado e representa uma
forte conexão entre nós adjacentes. Se este padrão fosse encontrado numa cadeia alimentar,
poderia representar uma anomalia na rede, pois este comportamento não é comum para este
tipo de rede.
a
b
c
Triângulo Completamente Conectado
Figura 1.3: O padrão mais encontrado em rede World Wide Web.
Podemos concluir que os Motifs representam algumas funcionalidades da rede, ou seja,
podem indicar tendências de comportamento e podem caracterizar uma rede qualquer. Deste
modo, podemos analisar uma rede complexa desconhecida e classificá-la a partir de seus Motifs.
Por exemplo, se numa rede desconhecida ocorrer o Motif a → b → c, podemos dizer
que ela se aproxima de uma cadeia alimentar. Já se ocorrer o Motif Triângulo Completamente
1.1. Definição do Problema
4
Conectado conforme Figura 1.3, então esta pode ter um comportamento parecido com o de uma
rede social ou WWW.
De pouco vale receber um genoma com milhões de genes e observá-lo de maneira direta,
ou seja, sem um tratamento computacional. Agora, a partir de Motifs, podemos classificar tais
genes e suas relações de semelhança ou de proximidade em relação a outros genomas.
Genomas, cadeias alimentares, redes sociais, redes neuronais, redes de informação e redes
obtidas da web podem ser representadas como grafos direcionados e analisados a luz da teoria
sobre Network Motifs.
Neste sentido, Motifs consistem em uma ferramenta com amplo espectro de aplicações.
1.1 Definição do Problema
O problema de Network Motifs visa analisar um grafo direcionado qualquer e identificar os seus
componentes básicos. A detecção dos Network Motifs é uma tarefa de elevado custo computacional. Nos últimos anos diversas ferramentas foram implementadas, visando a otimização e
permitindo analisar redes cada vez maiores [7, 16, 17, 20, 21]. Podemos dividir o problema em
quatro partes, conforme sugerido por [7]:
1. Enumeração de todos os subgrafos de tamanho k.
2. Classificação do subgrafo quanto ao isomorfismo.
3. Geração de grafos aleatórios.
4. Análise estatística dos padrões para identificar os possíveis Motifs.
1
2
3
4
5
6
7
Entrada: Um grafo G.
Saída: Os Motifs identificados.
para cada grafo ∈ (G ∪ Aleatrios(G)) faça
Enumeração de todos os subgrafos de tamanho k.
para cada subgrafo de tamanho k faça
Classificação quanto ao isomorfismo.
fim
fim
Análise estatística dos padrões para identificar os possíveis Motifs [7].
Algoritmo 1: Definição genérica para o Problema de Network Motifs.
Basicamente, podemos definir o problema de forma genérica conforme o Algoritmo 1.
5
Motifs ocorrem tanto em grafos não orientados como em dígrafos. Como dígrafos é um
caso mais geral e abrange os grafos sem orientação, neste trabalho, o foco será voltado para
encontrar Network Motifs em dígrafos.
1.2 Solução para o Problema
Figura 1.4: Representação do resultado gerado pelo gerador de subgrafos tendo como entrada
o grafo da Celebridade.
Vamos iniciar a apresentação do problema com um exemplo prático. Na Figura 1.4 temos a
representação de uma rede social onde o elemento central é uma celebridade e a sua adjacência
os fãs. Network Motifs são representados por subgrafos conexos de uma rede qualquer. Para
contabilizar os padrões precisamos gerar todos os subgrafos conexos induzidos de tamanho k.
No exemplo do grafo da celebridade para k = 3 temos os subgrafos A, B, C, D, E e F , descritos
na Figura 1.4. É necessário agora classificá-los quanto ao isomorfismo.
Considere os subgrafos A e B, descritos na Figura 1.4, em que A possui os vértices {a0 , a1 , a2 }
e B os vértices {b0 , b1 , b3 }. Se existe uma mudança dos rótulos, de forma que A e B possuam
o mesmo conjunto de vértices e arestas, dizemos que A e B, são isomorfos. Neste exemplo,
A e B, são isomorfos, rotulando (b0 , b1 , b3 ) ← (a0 , a1 , a2 ). Outro exemplo pode ser visto nos
subgrafos C e D que são isomorfos por meio da permutação (c0 , c1 , c4 ) ← (d0 , d2 , d3 ).
É interessante observar que existem 13 padrões de dígrafos conexos para k = 3. Para
k = 4 e k = 5 são respectivamente 199 e 9364 padrões distintos [23]. O número de subgrafos
possíveis cresce de modo exponencial conforme o tamanho de k aumenta. Na Figura 1.5 temos
a representação dos 13 padrões de tamanho 3.
Neste processo, o classificador precisa identificar se dois subgrafos são isomorfos ou não
e em seguida contabilizar os padrões idênticos e separar os distintos. O exemplo ilustrado
1.2. Solução para o Problema
6
Figura 1.5: Lista dos 13 dígrafos conexos para k = 3 numerados de 1 a 13.
na Figura 1.6, os padrões {A, B, E, F } são agrupados como um único padrão isomorfo e os
subgrafos {C, D}, são agrupados em um padrão diferente. Conforme ilustrado na Figura 1.6
temos apenas dois padrões distintos, o primeiro ocorre 2 vezes e o segundo 4. Para representar
esta distinção, podemos utilizar um histograma com os padrões isomorfos no eixo X e o número
de ocorrências no eixo Y .
Figura 1.6: Representação dos subgrafos passando por um classificador quanto ao isomorfismo.
Para identificar os Motifs é necessário comparar o histograma gerado a partir do grafo original com os histogramas dos grafos aleatórios. Conforme Milo et al. [15], o número total de
grafos aleatórios é variável, mais tipicamente estão entre 100 a 1000 grafos aleatórios. Então,
os dois passos anteriores, que são: gerar todos os subgrafos de tamanho k e classificá-los quanto
ao isomorfismo, deverão ser aplicados 1 vez no grafo original e pelo menos 100 vezes em grafos
aleatórios. Este é o grande gargalo do problema de Network Motifs. A tarefa mais custosa é
a geração de subgrafos, mas como o processo de classificação será aplicado a cada subgrafo,
7
podemos concluir que as duas primeiras etapas do processo detém a maior parcela de relevância
no custo computacional.
Os padrões do grafo original que ocorrerem com uma frequência incomumente maior que
a dos padrões dos grafos aleatórios serão classificados como Motifs [15]. A relevância do
Motif na rede será indicado pelo número de desvios padrões contidos na diferença entre o grafo
original e a média dos grafos aleatórios. Por exemplo se o número de ocorrências no grafo
original for igual a 10, o valor médio nos grafos aleatórios for 2, e o desvio padrão dos grafos
aleatórios for 1, então este padrão ocorre 8 desvios padrões acima da média.
1.3 Objetivos
O principal objetivo deste trabalho é propor um novo algoritmo para identificação de Network
Motifs, demostrar seu funcionamento e comparar seu desempenho em relação aos demais. O
grande gargalo deste problema é a enumeração de todos os padrões de tamanho k [24]. A
classificação dos padrões por meio do isomorfismo cresce exponencialmente com relação ao
tamanho do grafo.
A estratégia pretendida é enumerar os padrões não um a um e sim em bloco. Deste modo
conseguiremos analisar vários padrões ao mesmo tempo. Esta abordagem será apresentada pelo
algoritmo acc-Motif (Accelerated Motif) [14].
Serão apresentadas também algumas estratégias utilizadas pelos melhores algoritmos existentes na literatura e iremos comparar seus desempenhos com relação ao acc-Motif.
1.4 Organização do texto
No Capítulo 2, apresentamos uma visão mas detalhada do problema de Network Motifs. Serão
apresentados algumas classificações dos algoritmos que resolvem o problema e os tipos de
frequências que podem ser adotadas para gerar os subgrafos. Também apresentaremos as quatro
etapas necessárias para resolver o problema descritas na Seção 1.1 de forma mais detalhada.
Os Capítulos 3 e 4 apresentam a descrição do acc-Motif [14], que é um algoritmo desenvolvido para resolver o problema de Network Motifs. Este algoritmo possui uma característica
bastante peculiar e inovadora, pois as duas primeiras etapas do problema são resolvidas de uma
única vez, diminuindo bastante o custo computacional. Esta abordagem está modelada para
k = 3 e k = 4, contudo esta metodologia pode ser utilizada para resolver problemas maiores.
Neste trabalho será tratado apenas estes tamanhos devido à elevada sofisticação do algoritmo.
Por fim, o Capítulo 5 contém nossas considerações finais.
C APÍTULO
2
Network Motifs
Existem diversos algoritmos voltados à identificação de Network Motifs, alguns deles são: FANMOD [21], MFinder[16], MAVisto[20], Kavosh[7], MODA[17], Grochow[6], entre outros.
Cada algoritmo possui uma peculiaridade com relação às tarefas necessárias para resolver o
problema. A maior parte das diferenças estão relacionadas à enumeração de todos os subgrafos
de tamanho k.
2.1 Frequência de subgrafos
Existem 3 tipos de frequência de subgrafos F1 , F2 , F3 , conforme citado por Elisabeth [24]. F1
permite que vértices e arestas sejam sobrepostos, ou seja, ao gerar os subgrafos conexos de
tamanho k, será permitido que vértices e arestas sejam contados em mais de um subgrafo. Contudo os conjuntos de vértices não devem ser idênticos. A frequência F2 permite que apenas os
vértices sejam sobrepostos, deste modo uma aresta só poderá pertencer a um único subgrafo.
Esta frequência permite que diferentes conjuntos de subgrafos sejam construídos, podendo variar de acordo com a ordem de varredura. Isto ocorre pelo fato de que as arestas não podem
ser sobrepostas. Para F3 restou o requisito mais forte, ou seja, não permitir qualquer sobreposição de vértices e de arestas. O exemplo de gerador de subgrafo descrito na Seção 1.2 utiliza
a frequência F1 , ou seja, os padrões {A, B, C, D, E, F } serão criados. Utilizando-se F2 podemos ter 3 conjuntos de subgrafos diferentes {A, F } ou {B, E} ou {C, D}. Para F3 teremos
9
2.2. Classificação dos algoritmos
10
apenas um dos conjuntos: {A}, {B}, {C}, {D}, {E}, {F }. A maioria dos algoritmos utilizam
a frequência F1 , pois o resultado será o mesmo em todas as varreduras.
2.2 Classificação dos algoritmos
Existem duas estratégias utilizadas para fazer a varredura do grafo, os algoritmos centrados no
Grafo e os algoritmos centrados no Motif [24]. Os algoritmos centrados no Grafo iniciam as
buscas a partir da rede. Uma das vantagens é que subgrafos que não existem na rede não serão processados. Estes algoritmos necessitam gerar todos os subgrafos para poderem computar
as suas respectivas frequências. Os algoritmos centrados no Motif são capazes de calcular a
frequência de determinado padrão no grafo de forma isolada, deste modo ao calcular a média deste padrão nos grafos aleatórios, já podemos dizer se este padrão é um Motif ou não.
Se o pesquisador tiver interesse em encontrar um padrão específico, então esta abordagem é
a mais apropriada, pois não será necessário gerar todos os subgrafos de tamanho k. Para calcular todas as ocorrências de padrões na rede, os algoritmos centrados no Motif tem como
pré-processamento a enumeração de todos os subgrafos isomórficos de tamanho k.
Outra abordagem é com relação à enumeração dos subgrafos, podendo ser exata ou por
amostragem. A enumeração exata, como o nome já diz, calcula todos os subgrafos tendo como
resultado a enumeração exata dos subgrafos. Já a enumeração por amostragem utiliza uma
abordagem probabilística e com uma boa quantidade de amostras pode-se chegar perto do resultado esperado, mas alguns subgrafos podem ser perdidos. A grande vantagem da abordagem
por amostragem consiste no fato de que o algoritmo fica insensível ao tamanho do grafo. Na
Tabela 2.1 indicamos alguns algoritmos presentes na literatura e sua classificação conforme
características descritas acima.
Tabela 2.1: Classificação dos algoritmos de Network Motifs [24]
Exata
Amostragem
Centrado no Grafo
MAVisto[20]
Kavosh[7]
FANMOD [21]
MFinder[16]
Centrado no Motif
Grochow[6]
MODA[17]
Capítulo 2. Network Motifs
11
2.3 Enumeração de subgrafos
Para executar esta tarefa, alguns requisitos devem ser respeitados. O primeiro deles é que o
subgrafo gerado precisa ser conexo. No problema de Network Motifs, padrões desconexos não
trazem nenhuma informação relevante com relação aos vértices desconexos. Também o número
de subgrafos possíveis aumentaria ainda mais se o requisito de conexidade fosse retirado.
Seja G(V, E) o grafo a ser analisado e n = |V |. Desprezando a conexidade do grafo
podemos combinar todos os n vértices em conjuntos de tamanho k. Sabemos que
n!
n
=
k!(n − k)!
k
Outra importante característica é que cada subgrafo isomórfico deve ser contado apenas
uma vez. Suponha agora k = 3 e um subgrafo conexo formado pelos vértices {a, b, c} esta
combinação só poderá ser contabilizada uma única vez.
2.3.1
Algoritmo de Força Bruta
Para introduzir o assunto pode-se apresentar um método que, apesar de baixa eficiência, é elucidativo e resolve o problema de forma intuitiva. Como os Motifs são representados pelos
subgrafos conexos, as combinações que não forem serão desprezadas. No exemplo do grafo da
Celebridade descrito na Seção 1.2, como o grafo possui 5 vértices e o tamanho do subgrafo é
3, teríamos 10 combinações, mas destas 10 apenas 6 são utilizadas. A complexidade de gerar
todas as combinações k a k é Θ(nk ), ou seja, combinar todos os vértices sem analisar se o subgrafo gerado será conexo ou não, possui um elevado custo computacional. Para grafos densos
pode ser que a abordagem seja eficiente, mas na maioria dos casos diversas combinações serão
desprezadas devido à falta de conexidade.
No Algoritmo 2 pode-se observar um algoritmo recursivo para o método de Força Bruta
descrito acima.
2.3.2
Algoritmo Elementar
Uma abordagem interessante seria uma varredura que gerasse apenas combinações de vértices
conexos. A vantagem consiste em não ter que chamar o método que verifica a conexidade. O
fato de não gerar combinações desnecessárias aumenta a eficiência do gerador. Para ter este
comportamento, o algoritmo precisa varrer os vértices do grafo tendo como base os seus vizinhos. Se a combinação for gerada respeitando a relação de adjacência, teremos um algoritmo
que terá uma complexidade bem mais interessante do que o método apresentado na Seção 2.3.1.
2.3. Enumeração de subgrafos
12
1
2
3
4
5
6
7
8
9
10
11
12
13
Dados: As variáveis index e t iniciam em 0. O k é o tamanho do subgrafo gerado e n é o
número de vértices do grafo. R é um vetor de tamanho k contendo a sequência
de vértices que será gerada.
Entrada: int R[k], int index, int t, int n, int k
Saída: Histograma contendo todos os subgrafos
Combinacao(R, index, t, n, k)
se k == index então
Gerar uma matriz com os vértices contidos em R.
se O subgrafo for conexo então
Adiciona a matriz ao Histograma
fim
fim
senão
para i = 0 ; i < (n − k − t) ; i + + faça
R[index] = index + t + i
Combinacao(R, index + 1, t + i, n, k)
fim
fim
Algoritmo 2: Exemplo de algoritmo gerador de subgrafos para tamanho k
A implementação deste algoritmo, para o caso geral, possui um elevado nível de dificuldade
devido à sofisticação do algoritmo. Neste caso o requisito mais difícil de ser respeitado é o de
gerar cada combinação apenas uma vez.
Devido à dificuldade de implementação será apresentado um algoritmo para k = 3 e outro
para k = 4. A abordagem que iremos descrever se assemelha a uma busca em largura. Para
facilitar a implementação do algoritmo, ele foi dividido em níveis de iteração. O primeiro nível
será uma iteração por todos os vértices do grafo e os níveis seguintes apenas os vizinhos do
nível anterior e assim sucessivamente.
Algoritmo para k=3
Definição 2.3.1. Seja G(V, E) um grafo simples, onde V é o conjunto de vértices do grafo e E o
conjunto de arestas. Quando oportuno, utilizaremos a notação VG para representar o conjunto
de vértices do grafo G. Definimos δ(v) como sendo o conjunto de vértices adjacentes a v ∈ V ,
tanto para grafos direcionados quanto para grafos não direcionados. Ou seja, para e ∈ E tal
que e = a → b, b ∈ δ(a) e a ∈ δ(b). Definimos também o grau do vértice v como sendo |δ(v)|.
Para subgrafos de 3 vértices utilizaremos os vértices, i, j e k tal que i ∈ V e j ∈ δ(i) e
k ∈ δ(j).
13
Analisando padrões com 3 vértices existem 2 configurações que precisamos varrer para
que todos os subgrafos possíveis sejam gerados. A primeira delas é quando temos um vértice
em cada nível de adjacência, por exemplo, um subgrafo formado pelos vértices {i, j, k}. Esta
configuração poderá formar um caminho de tamanho 3. Outra configuração seria um subgrafo
formado pelos vértices {i, j1 , j2 }. Neste caso podemos encontrar um ciclo de tamanho 3. Na
Tabela 2.2, temos a descrição das 2 configurações necessárias.
Tabela 2.2: Descrição das 2 configurações necessárias para o gerador k = 3.
1o Configuração
u
i
2o Configuração
u
u
j
k
u
j
u
PP
PP
i
PP u
j
1
2
3
4
5
6
7
8
9
10
Entrada: Grafo G(V, E) e δ(v) ∀v ∈ V .
Saída: Histograma contendo todos os subgrafos.
para cada i ∈ V faça
para cada j ∈ δ(i) & j > i faça
para cada k ∈ δ(j)\δ(i) & k > i faça
Gera um subgrafo com os vértices i, j e k.
1o Configuração
Adiciona o subgrafo ao Histograma.
fim
fim
para cada j1 , j2 ∈ δ(i) & j1 6= j2 & j1 , j2 > i faça
Gera um subgrafo com os vértices i, j1 e j2 .
2o Configuração
fim
fim
Algoritmo 3: Exemplo de algoritmo gerador de subgrafos de tamanho 3.
Podemos visualizar a implementação do Algoritmo 3. Para que as combinações não gerem
vértices repetidos, a intersecção entre os conjuntos de níveis diferentes deve ser vazia. Por este
motivo na 1o configuração do Algoritmo 3, o vértice k ∈ δ(j)\δ(i) tal que k > i.
Para que não haja repetição das combinações geradas é necessário verificar que vértices pertencentes aos níveis seguintes, sejam estritamente maiores que os vértices dos níveis anteriores.
2.4. Classificação quanto ao isomorfismo
14
Algoritmo para k=4
Para o gerador de tamanho 4 utilizaremos os vértices i, j, k, p. Para este algoritmo teremos 5
configurações necessárias para que todas as combinações sejam geradas. Na Tabela 2.3, temos
a descrição das 5 configurações.
Tabela 2.3: Descrição das 5 configurações necessárias para o gerador k = 4.
1o Configuração
u
i
2o Configuração
u
u
u
j
k
p
u
k
u
P
PP
j
PP
Pu
u
i
k
3o Configuração
u
j
u
PP
PP
i
PP u
j
4o Configuração
u
k
u
j
u
P
P
PP
i
PP u
j
5o Configuração
u
k
u
j
u
u
H
j
i HH
HH
Hu
j
Podemos visualizar a implementação do algoritmo por meio do Algoritmo 4.
2.4 Classificação quanto ao isomorfismo
Identificar se dois grafos são isomórficos é um dos poucos problemas que estão em NP, mas
não se sabe se está na classe NP-Completo ou se é solúvel em tempo polinomial [8]. Algumas
técnicas utilizadas para reduzir o tempo de processamento analisa cada grafo separadamente
e tenta distinguir diferenças estruturais nos vértices do grafo. Assim podemos agrupá-los de
acordo com as suas semelhanças, diminuindo o espectro de possibilidades de permutação, que
no caso geral é n!.
Quando dizemos que dois grafos são isomórficos quer dizer que eles possuem a mesma
forma, ou seja, são estruturalmente equivalentes. Para analisarmos a estrutura do grafo devemos
ignorar os seus rótulos, pois estes podem estar permutados.
Definição 2.4.1. Um isomorfismo entre dois grafos G e H é uma bijeção b de VG em VH tal que
dois vértices u e v são adjacentes em G se e somente se b(u) e b(v) são adjacentes em H.
Teorema 2.4.2. Se A e B, são isomórficos, então A e B, devem possuir o mesmo número de
vértices e de arestas.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
15
Entrada: Grafo G(V, E) e δ(v) ∀v ∈ V .
Saída: Histograma contendo todos os subgrafos.
para cada i ∈ V faça
para cada j ∈ δ(i) & j > i faça
para cada k ∈ δ(j)\δ(i) & k > i faça
para cada p ∈ δ(k)\(δ(j) ∪ δ(i)) & p > i faça Gera um subgrafo com os vértices i, j, k e p.
1o Configuração
fim
fim
para cada k1 , k2 ∈ δ(j) & k1 6= k2 & k1 , k2 > i faça
Gera um subgrafo com os vértices i, j, k1 e k2 .
2o Configuração
fim
fim
para cada j1 , j2 ∈ δ(i) & j1 6= j2 & j1 , j2 > i faça
para cada k ∈ δ(j1 )\δ(i) & k > i faça
Gera um subgrafo com os vértices i, j1 , j2 e k.
3o Configuração
fim
para cada k ∈ δ(j2 )\δ(i) & k > i faça
Gera um subgrafo com os vértices i, j1 , j2 e k.
4o Configuração
fim
fim
para cada j1 , j2 , j3 ∈ δ(i) & j1 6= j2 , j2 6= j3 , j1 6= j3& j1 , j2 , j3 > i faça
Gera um subgrafo com os vértices i, j1 , j2 e j3 .
5o Configuração
fim
fim
Algoritmo 4: Exemplo de algoritmo gerador de subgrafos de tamanho 4.
Demonstração. Suponhamos por absurdo que dois grafos A e B, isomórficos e que possuem
o número de vértices diferentes, ou seja, |VA | =
6 |VB |. Como a cardinalidade dos conjuntos é
diferente então não é possível estabelecer uma bijeção entre VA e VB . Suponhamos agora que
|VA | = |VB | e que |EA | =
6 |EB |. Sem perda de generalidade podemos dizer que existe uma
aresta uv ∈ EA tal que b(u) e b(v) não são adjacentes em B.
Conforme Figura 2.1 podemos perceber que esta condição não é suficiente para garantir o
isomorfismo, pois |VA | = |VB | e |EA | = |EB |, contudo A não é isomórfico a B.
16
2.4.1
Algoritmo de Força Bruta
Este método foi desenvolvido para resolver o isomorfismo em grafos de qualquer tamanho.
Para saber se dois grafos são isomórficos, basta testar todas as permutações dos vértices de
um dos grafos e comparar com o segundo. Se ficarem iguais para alguma permutação, então
são isomórficos. Se após todas as permutações possíveis dos vértices os grafos não ficarem
iguais, então eles definitivamente não são isomórficos. A identificação da igualdade é feita por
meio da matriz de adjacência. Neste caso as matrizes dos dois grafos deverão ficar idênticas.
Este método tem complexidade Θ(n2 n!), onde n! é o número de permutações e n2 o tempo de
comparação das duas matrizes. Este método resolve o problema do isomorfismo, mas seu custo
computacional é elevado. O Algoritmo 5 apresenta o método.
1
2
3
4
5
6
7
Entrada: m1 [][], m2 [][] e P , onde P é o conjunto de todas as permutações possíveis.
Saída: Resposta se os grafos são isomórficos ou não
Dados: aux[][] é uma matriz auxiliar
para cada p ∈ P faça
aux=Permutação de m2 por meio de p.
se m1 == aux então
retorna verdadeiro
fim
fim
retorna falso
Algoritmo 5: Algoritmo de identificação de isomorfismo por meio de Força Bruta.
Este método não faz uso de nenhuma propriedade de teoria dos grafos, apenas testa exaustivamente todas as possibilidades de permutação dos vértices. Existem muitas informações
disponíveis a partir de uma análise mais detalhada dos grafos de modo a eliminar permutações
desnecessárias.
2.4.2
Algoritmo de Força Bruta com Refinamento Estrutural
Este método visa refinar o espectro de busca com o intuito de diminuir o número de permutações
necessárias para identificar o isomorfismo.
Definição 2.4.3. Definimos assinatura de grau como sendo um vetor contendo todos os graus
dos vértices ordenados em ordem crescente.
No contexto de emparelhamento isomórfico, se analisarmos os graus dos vértices, podemos
identificar que não é possível emparelhar vértices cujos graus sejam distintos, ou seja, não tem
como emparelhar um vértice de grau 2 com outro de grau 3 na permutação.
A
17
B
Figura 2.1: Exemplo de dois grafos que possuem o mesmo número de vértices e arestas mas
não são isomórficos.
No exemplo descrito na Figura 2.1 temos dois grafos A e B que possuem o mesmo número
de vértices e de arestas, respeitando os requisitos do Teorema 2.4.2. Podemos perceber que o
grafo A possui uma estrutura diferente de B. Analisando as suas assinaturas de graus percebemos que o grafo A possui um vértice de grau 3 e B não. Então não existe possibilidade de
emparelhar os vértices de A de modo que A e B, possuam a mesma matriz de adjacência. Neste
caso podemos dizer que A e B não são isomórficos.
Teorema 2.4.4. Se A e B, são isomórficos, então A e B, devem possuir assinatura de graus
idênticas, mas esta condição não é suficiente para garantir o isomorfismo.
Demonstração. Suponhamos por absurdo que dois grafos G e H sejam isomórficos e que possuam assinaturas de grau distintas. Sejam u ∈ VG e v ∈ VH dois vértices que possuem graus
distintos, ou seja, este par de vértices não pode ser emparelhado, pois a relação de adjacência
não será mantida devido a cardinalidade dos vértices adjacentes. Deste modo não poderá existir
uma bijeção entre u e v, e portanto, G e H não são isomórficos.
Por outro lado, uma mesma assinatura de graus não garante o isomorfismo. Um exemplo
pode ser visto nos grafos C e D da Figura 2.2, pois ambos possuem a mesma assinatura de
graus mas não são isomórficos.
Nosso algoritmo verifica se os dois grafos atendem ao Teorema 2.4.4 antes de fazer qualquer
permutação, pois se as assinaturas de graus forem diferentes já podemos dizer que os grafos não
são isomórficos.
Como não é possível emparelhar vértices que possuam graus distintos, podemos diminuir o
espectro de permutações. Este procedimento acelera o método, pois será necessário permutar
apenas vértices cujos graus sejam iguais.
18
c3
c1
c2
c4
c5
C
d4
d3
d1
d2
d5
D
Figura 2.2: Exemplo de dois grafos que possuem o mesmo número de vértices, arestas e assinatura de grau mas não são isomórficos.
Na Figura 2.2 temos os grafos C e D que possuem a mesma assinatura de grau, mas que
não são isomórficos. Para o grafo C vamos definir os respectivos graus como d(ci ) e para o
grafo D como d(di ). Podemos representar a assinatura de graus dos grafos descritos na Figura
2.2 como:
d(c1 ) = 2
d(c2 ) = 3
d(c3 ) = 2
d(c4 ) = 2
d(c5 ) = 1
d(d1 ) = 2
d(d2 ) = 3
d(d3 ) = 2
d(d4 ) = 2
d(d5 ) = 1
O algoritmo de Refinamento Estrutural faz uso destas características e só permuta vértices
que possuam o mesmo grau.
Para testar o isomorfismo precisamos emparelhar (c1 , c3 , c4 ) com uma permutação de (d1 , d3 , d4 )
que possuem grau 2. O vértice c2 só pode ser permutado com d2 pois são os únicos que possuem
grau 3 e c5 só pode ser emparelhado ao vértice d5 , ambos com grau 1. Com este refinamento,
passamos a fazer 3!1!1! = 6 permutações ao invés de 5! = 120 permutações.
Este método é uma especialização do Método de Força Bruta. A única diferença é que serão
permutados apenas vértices que possuam os graus idênticos. Assim sua complexidade estará
diretamente ligada à estrutura do grafo. No pior caso, onde todos os graus são idênticos, sua
complexidade é Θ(n2 n!). No melhor caso, onde todos os vértices são distintos, sua complexidade é Θ(n2 ). Este método é completo, ou seja, resolve o problema do isomorfismo para grafos
com n vértices.
Para o problema de Network Motifs não basta saber se dois grafos são isomórficos ou não, é
necessário identificar a qual padrão isomórfico este grafo pertence. Assim, se existirem muitos
padrões isomórficos, teremos que fazer o teste de isomorfismo com todos os padrões existentes
no histograma, até que seja encontrado o padrão a qual este grafo pertence.
19
Tabela 2.4: Número de padrões em relação a k [23]
Número de Padrões distintos
n de vértices Quantidade de Padrões
2
2
3
13
4
199
5
9.364
6
1.530.843
7
880.471.142
8
1.792.473.955.306
o
Na Tabela 2.4 temos o número de padrões isomórficos existentes para determinado valor de
k. Por exemplo para k = 3 temos 13 padrões isomórficos. O histograma gerado a partir do
classificador terá 13 barras, indicando o número de ocorrências de cada padrão. Se quisermos
utilizar o método descrito anteriormente na Seção 2.4.2, para adicionar um subgrafo ao histograma teremos que testar o isomorfismo com 13 padrões, ou seja, se este subgrafo que queremos
adicionar for isomórfico ao 13o padrão da lista teremos feito no final 13 teste de isomorfismo.
Conforme descrito na Tabela 2.4, se tivermos k = 6 e acontecesse o mesmo episódio descrito
anteriormente teríamos feito 1,5 milhões de testes quanto ao isomorfismo. Este procedimento é
extremamente custoso, pois a complexidade para cada teste no pior caso é Θ(n2 n!).
2.4.3
Isomorfismo Polinomial
Seria interessante que a complexidade do teste fosse polinomial e que não fosse necessário testar
todos os padrões isomórficos para saber a qual padrão um determinado subgrafo pertence. Para
contornar este problema criamos o conceito de hash aplicado a identificação de isomorfismo.
Uma função de hashf (x) recebe como entrada um valor x e devolve como saída um inteiro
f (x), que é um número com menos dígitos. A função de hash faz uma diminuição do domínio
facilitando operações de busca. Por outro lado, podem ocorrer colisões, ou seja, f (x1 ) = f (x2 ),
para x1 6= x2 .
No problema de Network Motifs, calcularemos uma função f (x) onde x será a representação binária da matriz de adjacência do grafo. Nestas condições, espera-se o seguinte comportamento:
Propriedade 2.4.5. Se x1 e x2 correspondem a grafos isomórficos, então f (x1 ) = f (x2 ).
20
Desta forma, ao calcular f (x1 ) 6= f (x2 ) já sabemos que x1 e x2 não são isomórficos. Desejamos entretanto a seguinte propriedade:
Propriedade 2.4.6. f (x1 ) = f (x2 ) se e somente se x1 e x2 são grafos isomórficos.
Neste segundo caso, mais forte, a função de hash é suficiente para detectar o isomorfismo
entre dois grafos.
Os métodos de identificação de isomorfismo em grafos, descritos abaixo, utilizam o valor
de saída da função hash, que será chamado de chave, para identificar o isomorfismo.
Teste de Completude
Para auxiliar no processo de descoberta dos padrões isomórficos, foi desenvolvido um algoritmo
que gera todos os grafos de tamanho k. Considerando, para tanto, uma matriz de adjacência
2
k × k e todas as suas possibilidades de preenchimento binário, desta forma teremos 2k grafos
gerados. Assim os algoritmos utilizados para identificar o isomorfismo poderão ser testados
quanto a sua completude. Aplicando este método em conjunto com os algoritmos abaixo, iremos identificar quantos padrões existem e qual a quantidade de matrizes possíveis para cada
padrão. Podendo assim, auxiliar na certificação dos métodos mais elaborados.
O Algoritmo 6 apresenta a implementação do método.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Dados: A variável ini é inicializada em 0 e fim em n2 . O valor k é o tamanho do subgrafo
gerado e (i, j) é a posição da matriz em função de k, entre (0, 0) e (k − 1, k − 1).
Gerador(int ini, int f im, int k, boolean matriz[k][k])
i = ⌊ini/k⌋
j = ini mod k
se ini = f im e o subgrafo for conexo então
Adiciona o subgrafo ao Histograma
fim
senão
matriz[i][j]=falso
Gerador(ini+1, fim, k, matriz)
se i 6= j então
matriz[i][j] = verdadeiro
Gerador(ini + 1, f im, k, matriz)
fim
fim
Algoritmo 6: Algoritmo para o Teste de Completude.
Agora iremos descrever alguns métodos utilizados para identificar o isomorfismo.
2.4.4
21
Primeira Função de hash: Assinatura de Grau
v1
v2
v4
v3
Figura 2.3: Exemplo de subgrafo cujos graus são distintos.
Este método utiliza a assinatura de grau do grafo como função de hash. Como o foco deste
trabalho é o grafo direcionado, um determinado vértice pode ter arestas que saem e que chegam.
Nesse caso, o grau será composto por um índice positivo que representa o número de arestas
que saem do vértice e um índice negativo que representa as que chegam. Cada vértice do grafo
irá possuir um par de graus e os graus deverão ser ordenados na função de hash.
Agora vamos exemplificar o método de acordo com o grafo da Figura 2.3. Vamos denominar
os seus respectivos graus como d(vi ) = (d+ (vi ), d− (vi )). Neste caso d+ (vi ) será o número de
arestas que saem do vértice e d− (vi ) as que entram. Para este exemplo teremos:
d(v1 ) = (0, 2)
d(v2 ) = (3, 0)
d(v3 ) = (1, 1)
d(v4 ) = (1, 2)
Para facilitar, vamos juntar esses dois dados em um inteiro, positivo à esquerda e negativo à
direita. Assim temos:
d(v1 ) = 02
d(v2 ) = 30
d(v3 ) = 11
d(v4 ) = 12
Ordenando os vértices de acordo com a ordem crescente dos graus, temos:
d(v1 ) = 02
d(v3 ) = 11
d(v4 ) = 12
d(v2 ) = 30
A chave pode ser representada pelo inteiro 2111230, resultante da concatenação dos graus.
Um grafo isomórfico com vértices permutados gerará a mesma chave de hash. Este método
é utilizado como base para vários outros métodos. Sua aplicação é eficaz, devido à facilidade e
o baixo custo computacional Θ(n2 ). Quanto a completude, este método resolve o isomorfismo
para grafos com até 3 vértices. Para testar sua eficiência foram gerados todas as matrizes de
adjacência para subgrafos conexos de tamanho 3, conforme o Teste de Completude apresentado
na Seção 2.4.3.
22
Teorema 2.4.7. Para k = 3, f (x1 ) = f (x2 ) se e somente se x1 for isomórfico a x2 . Ou seja, o
cálculo desta função é suficiente para resolver o isomorfismo para grafos com 3 vértices.
Demonstração. Na Figura 2.4 temos a representação de todos os padrões isomórficos para k =
3 e suas respectivas assinaturas.
Figura 2.4: Lista dos 13 padrões isomórficos de dígrafos conexos numerados de 1 a 13.
O histograma é representado por uma tabela hash. Quando um valor f (x) aparece pela
primeira vez, colocamos na tabela uma nova coluna passando (f (x), 1) indicando sua chave e
valor. Caso f (x) já esteja na tabela, basta incrementar o valor inteiro. O custo por subgrafo
será o cálculo da chave e a inserção no histograma. O procedimento de adição esta descrito no
Algoritmo 7.
1
2
3
4
5
6
7
8
Entrada: Uma matriz[k][k] booleana.
Dados: Hash <Long,Integer> histograma
chave=hash(matriz)
se O histograma contém a chave então
ocorrencias = histograma.get(chave)
histograma.put(chave,ocorrencias+1)
fim
else
histograma.put(chave,1)
end
Algoritmo 7: Algoritmo que adiciona um subgrafo ao histograma.
2.4.5
23
Assinatura de Grau com Permutação
É esperado que a função de hash implementada pela assinatura de grau não resolva o problema
para todos os valores de k. Para k = 4 já percebemos algumas colisões, ou seja, grafos não
isomórficos com mesma assinatura de grau.
Para identificar estas colisões foi utilizado o algoritmo de teste de completude para k = 4. A
Figura 2.5 ilustra uma das 46 colisões existentes no método de Assinatura de Grau para tamanho
4.
d = 13
d = 12
d = 13
d = 12
v1
v2
v1
v2
v4
v3
v4
v3
d = 21
d = 20
d = 21
d = 20
Figura 2.5: Grafos que não são isomórficos mas possuem as assinaturas iguais e todos os graus
são distintos.
Este método consiste em:
1. Permutar os vértices garantindo uma ordem crescente dos graus.
2. Converter a matriz em um número inteiro.
Caso os vértices possuam graus distintos, após a ordenação ocorrerá um casamento entre
os vértices de G e G′ . Assim, se a matriz de adjacência for igual, eles são isomórficos, caso
contrário eles não são.
Aplicando o procedimento descrito no método da Força Bruta com Refinamento Estrutural,
ou seja, permutando apenas vértices com mesmo grau, temos apenas uma forma de casar os
vértices. Suponhamos G e G′ dois grafos a serem analisados quanto ao isomorfismo. Consideremos que os graus de G sejam:
d(v1 ) = 01
E de G′ :
d(v2 ) = 10
d(v3 ) = 11
d(v4 ) = 12
24
d(v1 ) = 01
d(v2 ) = 10
d(v3 ) = 11
d(v4 ) = 12
Se G′ for isomórfico a G, então a matriz de adjacência de G deve ser idêntica a matriz de
G′ . Agora, caso G′ possua os graus:
d(v1 ) = 10
d(v2 ) = 01
d(v3 ) = 11
d(v4 ) = 12
Mesmo que G seja isomórfico a G′ suas matrizes de adjacência serão diferentes. Então para
identificar o isomorfismo devemos permutar a matriz de G′ com relação aos vértices v1 e v2
para que sua matriz fique idêntica à matriz de G.
Este método visa permutar a matriz de adjacência de acordo com a ordem crescente dos
graus. Desta forma, se um grafo for isomórfico a outro e os graus forem distintos suas matrizes
deverão ser idênticas. Como o isomorfismo só é garantido por meio da matriz, temos que passar
este valor para a chave.
Para fazer esta conversão podemos escrever o valor da matriz de adjacência convertida em
um inteiro e usá-lo como chave. Vamos demonstrar a utilização do método por meio de um
exemplo.
Seja H o grafo representado pela Figura 2.3 e A sua matriz de adjacência:

0 0 0

 1 0 1
A=
 0 0 0

1 0 0

0

1 

1 

0
Sejam os graus de H:
d(v1 ) = 02
d(v2 ) = 30
d(v3 ) = 11
d(v4 ) = 12
Ordenando pela ordem crescente dos graus, temos:
d(v1 ) = 02
d(v3 ) = 11
d(v4 ) = 12
d(v2 ) = 30
Agora devemos permutar a matriz de acordo com a ordem: v1 , v3 , v4 , v2 . Temos agora uma
nova matriz de adjacência A′ :

0 0 0

 0 0 1
A′ = 
 1 0 0

1 1 1

0

0 

0 

0
25
Uma vez obtida a matriz de adjacência permutada, precisamos transformar esta informação
em uma chave.
Como os valores da diagonal são sempre zero, então estes não precisam ser inseridos. Para
processar esta operação utilizaremos a função I(A′ ) onde aij são os elementos da matriz.
′
I(A ) =
n−1 X
n−1
X
2ni+j a(n−1−i)(n−1−j)
(2.1)
i=0 j=0
A função I(A′ ) é implementada pelo Algoritmo 8 descrito abaixo para gerar a chave.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Saída: O valor do subgrafo convertido num inteiro.
long chave=1
para int i=0; i<k ; i++ faça
para int j=0; j<k ; j++ faça
se i 6= j então
se Matriz[i][j] então
chave*=2+1
fim
senão
chave*=2
fim
fim
fim
fim
retorna chave
Algoritmo 8: Algoritmo que converte uma matriz binária num número inteiro.
Ao passarmos a matriz A′ para o Algoritmo 8 teremos no final o valor inteiro 4263 e este
valor será igual para todos os subgrafos isomórficos a H.
Teorema 2.4.8. Seja G e H dois grafos com todos os graus dos vértices distintos. I(A′G ) =
I(A′H ) se e somente se G for isomórfico a H.
Demonstração. O isomorfismo é identificado por meio de uma função bijetora. Para encontrar esta bijeção conforme o método de Refinamento Estrutural precisamos apenas emparelhar
vértices que possuem graus iguais. Como para cada grafo os graus são distintos então existe
apenas uma escolha para fazer o emparelhamento.
Este método resolve o problema do isomorfismo para grafos que não possuem repetição
nos graus dos vértices, pode ser combinado também com outros métodos e sua complexidade
26
é Θ(n2 ). Para grafos não orientados, a priori, não é possível aplicar este método pois como os
graus variam no intervalo [1, n − 1], então sempre teremos pelo menos dois graus iguais, mas
algumas informações podem ser inseridas nos valores dos graus de modo a deixá-los distintos.
2.4.6
Gradiente
Este método também é uma especialização do método Assinatura de Grau. Sua aplicação inicial
tinha o intuito de distinguir graus iguais. Por este motivo o método só é aplicado nestes vértices.
A distinção dos graus é obtida por meio das informações de seus vizinhos que podem ser, os
graus dos vizinhos e a relação entre eles. Para ser vizinho basta que exista uma aresta entre
eles, independente de sua orientação. Estes dados podem ser adicionados ao vértice em questão
de várias formas, por exemplo, soma, subtração, multiplicação etc. Agora vamos ilustrar a
aplicação do método adotando a soma.
v1
v2
v4
v3
Figura 2.6: Exemplo de grafo que possui dois graus iguais
Vamos primeiramente analisar o grafo da Figura 2.6. Temos inicialmente os graus:
d(v1 ) = 01
d(v2 ) = 20
d(v3 ) = 11
d(v4 ) = 01
d(v4 ) = 01
d(v3 ) = 11
d(v2 ) = 20
Após a ordenação temos:
d(v1 ) = 01
Neste caso aplicaremos o método aos vértices v1 e v4 . O v1 tem com adjacente o v2 , então
d(v1 ) = d(v1 ) + d(v2 ) = 01 + 20 = 21. E v4 tem como adjacente v3 , então d(v4 ) = d(v4 ) +
d(v3 ) = 01 + 11 = 12.
O intuito deste método é tornar todos os graus distintos para que o método de Permutação
apresentado na Seção 2.4.5, possa ser utilizado. Assim conseguimos distinguir os dois graus que
eram iguais. Este método possui um poder de distinção interessante, no entanto, a soma sofre
uma perda de generalidade. Por exemplo 11 + 11 = 22 e 10 + 12 = 22. Para evitar o ocorrido
27
mudaremos a forma de inserção. O uso apenas da concatenação para este caso já resolveria,
pois 11.11 = 1111 e 10.12 = 1012, mas o problema da concatenação é que a quantidade de
informação no grau vai aumentar muito, em consequência, a chave ficará maior ainda. Neste
caso, o uso da função hash é uma boa opção, pois independentemente do tamanho do grau,
passando por uma função hash, este valor poderá ser reduzido para uma determinada faixa de
variação e a dispersão será a mesma.
Com a função hash, podemos inserir ainda mais informações como, por exemplo, que tipo
de ligação existe entre o vértice e o seu adjacente. Se a relação for uma aresta de entrada então
adicione 1, se for de saída 2 e se for de entrada e saída 3. A função de hash pode ser:
h(k) = 50 + ⌊m(kc − ⌊kc⌋)⌋
√
5−1
onde m = 900 e c =
. Esta função retorna valores entre 50 e 950, ou seja, um valor
2
inteiro com no máximo 3 dígitos. A constante c é a mesma sugerida por Cormen et al. [5], pois
possui grande capacidade de dispersão dos dados.
Agora vamos demonstrar a utilização do método para o grafo apresentado na Figura 2.6.
Após a Assinatura de Grau temos:
d(v1 ) = 01
d(v4 ) = 01
d(v3 ) = 11
d(v2 ) = 20
Para aplicar o método em v1 , primeiro precisamos identificar seus vizinhos e qual a sua
relação com cada um. O v1 relaciona-se com v2 por meio de uma aresta de entrada, então a
relação é 1. Assim, passaremos para a função hash, k = grau.relação. No caso de v1 para
k = 201, temos que h(201) = 252.
Para o v4 , temos como vizinho o v3 e relação 1. Para k = 111, então h(111) = 591.
d(v3 ) = 11
d(v2 ) = 20
d(v1 ) = 252
d(v4 ) = 591
Após a ordenação dos graus a chave passa a ser o inteiro 1120252591.
Este método tem complexidade Θ(n2 ). Combinado com o método de Permutação descrito
na Seção 2.4.5, ele consegue resolver o isomorfismo por meio de um hash perfeito para grafos de
até 4 vértices. A quantidade de informação armazenada é pequena perto do poder de distinção
dos grafos.
Ao fazer uma análise detalhada deste método para grafos de 5 vértices, foi identificado
que o método chegava muito perto da completude total. Os grafos que não eram identificados
possuíam apenas uma diferença nos graus que eram distintos dos demais. Por esse motivo, o
28
método foi modificado para que seja aplicado em todos os vértices e não apenas nos graus que
eram iguais. Sua complexidade permaneceu em Θ(n2 ) e a distinção dos grafos aumentou ainda
mais.
Mesmo assim, alguns grafos de 5 vértices não eram resolvidos, então identificamos que
uma passagem do grafo no método não era suficiente, pois quando os graus eram todos iguais,
uma passagem distinguia apenas alguns vértices dos demais. Então foi criado um método de
gradiente genérico, que possibilita sua aplicação n vezes. O valor n foi estabelecido como sendo
o número de graus que eram iguais. Essa modificação resolveu o problema do isomorfismo para
grafos de até 5 vértices. Sua complexidade no pior caso é Θ(n3 ), que ocorre quando todos os
graus são iguais. O melhor caso ocorre quando todos os graus são distintos e sua complexidade
é Θ(n2 ). O Algoritmo 9 apresenta a função de hash utilizada para identificar o isomorfismo
eficientemente para k 6 5.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Saída: A chave da função de Hash
Dados: assinaturaGraus é um vetor contendo todos os graus dos vértices
Inicializa a assinaturaGraus por meio da matriz
se |matriz| > 3 então
se O número de graus iguais for 0 então
A chave recebe a conversão da matriz para inteiro
fim
else
assinaturaGraus=gradiente(matriz)
se O número de graus iguais for 0 então
A chave recebe a conversão da matriz para inteiro
fim
else
A chave recebe a conversão da assinaturaGraus para inteiro
end
end
fim
else
A chave recebe a conversão da assinaturaGraus para inteiro
end
retorna chave
Algoritmo 9: Função de hash.
Este algoritmo foi testado quanto a completude para k = 6. Infelizmente ocorreram em
torno de trezentas colisões, ou seja, grafos que possuem a mesma assinatura mas que não são
isomórficos. Contudo, este método conseguiu distinguir 1, 5 milhões de padrões, diminuindo
muito o número de testes.
29
Para instâncias maiores existem colisões que não permitem que o algoritmo resolva o problema de isomorfismo por completo, mas o poder de distinção do método é muito bom e sua
complexidade é baixa. Este algoritmo pode ser utilizado pelo algoritmo de Refinamento Estrutural descrito na Seção 2.4.2 evitando assim a necessidade de testes excessivos. Assim, para
k > 5 apenas a Propriedade 2.4.5 será respeitada. Deste modo, o algoritmo de Refinamento Estrutural só fará o teste de isomorfismo para padrões que possuam a mesma chave e que possam
ser isomórficos.
2.5 Geração de Grafos Aleatórios
No problema de Network Motifs é necessário que sejam gerados diversos grafos aleatórios para
que o algoritmo compare os resultados do grafo original com os resultados dos grafos aleatórios.
Existem várias formas para se gerar grafos aleatórios, cada problema utiliza uma abordagem
diferente. As diferenças entre uma abordagem e outra, são os requisitos exigidos por cada uma.
Um requisito fundamental para gerar grafos aleatórios é manter as propriedades básicas do
grafo, tais como o número de vértices e arestas.
2.5.1
Primeira Abordagem
Agora iremos descrever o algoritmo mais simples para gerar grafos aleatórios.
Definição 2.5.1. Seja G(V, E) o grafo aleatório que iremos construir. Fixemos n = |V | e m =
|E|. Podemos iniciar a construção do grafo a partir de uma matriz de adjacência n × n vazia.
As arestas podem ser inseridas aleatoriamente em qualquer posição respeitando o tamanho da
matriz. O Algoritmo 10 apresenta a implementação do método.
2.5.2
Segunda Abordagem
Para o problema de Network Motifs os grafos aleatórios são criados com a finalidade de comparação com o grafo original. Sendo assim, não é interessante um grafo aleatório com uma
estrutura muito diferente da existente no grafo original. Deste modo, a primeira abordagem não
é interessante pelo fato de que os grafos gerados podem ser completamente diferentes do grafo
original. Conforme Milo [15], é interessante que os grafos aleatórios possuam a mesma sequência gráfica do grafo original, ou seja, o grau dos vértices devem ser mantidos. Os algoritmos
que resolvem o Network Motifs geralmente fazem uso desta propriedade.
2.5. Geração de Grafos Aleatórios
30
1
2
3
4
5
6
7
8
Entrada: boolean matriz[n][n], número de vértices n e arestas m
Saída: A matriz preenchida
Dados: x, y indica as posições a serem setadas na matriz
para int i=0 ; i<m ; i++ faça
x e y recebem um inteiro aleatório entre 0 e n
enquanto matriz[x][y] faça
x e y recebem outro inteiro aleatório entre 0 e n
fim
matriz[x][y]=verdadeiro
fim
retorna matriz
Algoritmo 10: Primeira abordagem para geração de Grafos Aleatórios.
A abordagem mais eficiente para atender este requisito consiste em trocar diversos pares de
arestas pertencentes ao grafo original de modo a deixá-lo aleatório. Com isto, o algoritmo não
precisa construir um grafo novo, pode simplesmente utilizar o grafo original.
Existem várias situações possíveis quando pretende-se trocar duas arestas, neste trabalho
veremos duas delas.
Requisito mais fraco
Podemos escolher aleatoriamente duas arestas, por exemplo e1 = u1 → v1 e e2 = u2 → v2 , e
trocar a ponta das arestas, de modo que e1 = u1 → v2 e e2 = u2 → v1 . A Figura 2.7 exemplifica
esta troca.
u1
v1
u1
v1
u2
v2
u2
v2
Figura 2.7: Caso básico de troca.
Antes de fazer a troca precisamos verificar se tais arestas já não existem, para que não
tenhamos duas arestas idênticas. Nesta abordagem, arestas bidirecionais podem ser perdidas ou
criadas conforme mostra as Figuras 2.8 e 2.9.
31
u1
v1
u1
v1
u2
v2
u2
v2
Figura 2.8: Exemplo no qual uma aresta bidirecional se perde.
u1
v1
u1
v1
u2
v2
u2
v2
Figura 2.9: Exemplo onde uma aresta bidirecional é criada.
Requisito mais forte
Este algoritmo é mais restritivo, pois evita que o número de arestas bidirecionais sejam diferentes do grafo original. Este método é o mais utilizado pelos pesquisadores da área [21]. Para que
o número de arestas bidirecionais seja mantido, as trocas devem certificar que quando existir
uma aresta bidirecional esta só seja trocada por outra aresta bidirecional.
Nesta abordagem é comum o uso de dois parâmetros: o número de trocas por aresta e o
número de tentativas. O número total de trocas = k.m e k é o número de trocas por aresta. O
número de tentativas é necessário pois quando o grafo é muito denso fica difícil permutar arestas
respeitando todos os requisitos. Para fazer uma troca simples, temos que certificar que a nova
aresta não exista, como o grafo é denso, encontrar esta aresta pode ser difícil. Este parâmetro
evita que o algoritmo fique indefinidamente tentando encontrar uma possível troca.
2.6 Identificação de Motifs
Para identificar os Motifs é necessário encontrar os padrões que ocorrem com uma frequência
incomumente alta em relação aos grafos aleatórios. A comparação pode ser feita por meio da
média das ocorrências dos grafos aleatórios com os respectivos valores no grafo original. Como
existem diversos padrões, é necessário que a comparação seja feita com valores percentuais,
2.6. Identificação de Motifs
32
pois a média de subgrafos gerados a partir dos grafos aleatórios é diferente do total gerado a
partir do grafo original. Se o percentual de ocorrências de um determinado padrão for maior que
o percentual da média então dizemos que este padrão é um Motif. Para identificar a relevância
do Motif utilizamos o número de desvios padrões ocorridos entre a média e o valor real.
Tabela 2.5: Dados para a identificação de Motifs
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
13
chave
11011
1120
21010
111111
11121
21120
101112
22121
111221
121220
111122
122122
222222
Dados para a identificação de Motifs
Grafo Original
Grafos Aleatórios (Valor Médio)
365887 16,97% 1127569,70
35,37%
165661
7,68%
517159,50
16,22%
1115548 51,73% 1532649,50
48,08%
561
0,03%
372,90
0,01%
152105
7,05%
1806,30
0,06%
26104
1,21%
2765,70
0,09%
208174
9,65%
5348,10
0,17%
12406
0,58%
2,80
0,00%
1886
0,09%
8,70
0,00%
25490
1,18%
11,00
0,00%
58077
2,69%
9,00
0,00%
6574
0,30%
0,10
0,00%
18161
0,84%
0,00
0,00%
DP
1398,33
263,19
1147,39
18,90
280,22
84,46
1156,34
2,15
4,69
5,14
5,46
0,32
0,00
No de DP
-419,60
-1034,60
101,30
24,10
795,90
424,10
261,50
8527,90
592,30
7324,50
15729,50
30727,50
0,00
A Tabela 2.5 contém todos os dados necessários para a identificação de Motifs de tamanho
3. Estes dados foram gerados a partir do grafo Foldoc [3] que possui 13356 vértices e 109092
arestas. Como o intuito foi demonstrar os dados, foram gerados apenas 10 grafos aleatórios.
A Figura 2.10 mostra as diferenças ocorridas no número de padrões do grafo original com
relação ao valor médio dos grafos aleatórios. Ela representa graficamente os dados da Tabela
2.5 e os padrões seguem a mesma ordem dos padrões descritos na Figura 2.4.
Figura 2.10: Número de padrões no grafo original com relação à média.
33
C APÍTULO
3
A ideia central deste algoritmo é contabilizar todos os subgrafos existentes a partir de uma
estrutura básica analisando apenas a sua adjacência imediata, ou seja, para cada estrutura, calcular os possíveis subgrafos analisando um determinado número de vizinhos. Cada estrutura
deve ser única para evitar duplicidade na enumeração dos subgrafos. Por exemplo, para Motifs
de tamanho 3 podemos partir de uma estrutura básica composta por um vértice e analisar a sua
adjacência combinando seus vizinhos 2 a 2. Deste modo, teremos um vértice central v como
referência e por meio de otimização combinatória os subgrafos serão contabilizados. Se este
procedimento for aplicado a v, ao final teremos calculado todos os subgrafos existentes com v
em sua posição central.
É importante esclarecer que neste Capítulo serão tratados apenas os procedimentos necessários para desempenhar a tarefa de enumeração, ou seja, gerar todos os subgrafos de tamanho
k e classificá-los quanto ao isomorfismo. As demais etapas necessárias para identificação de
Network Motifs foram implementados conforme a Seção 2.5.
3.1 Grafos não direcionados
Para iniciar a demostração do método utilizado pelo acc-Motif [14] para enumerar os subgrafos
de tamanho 3, vamos definir algumas notações.
35
3.1. Grafos não direcionados
36
Definição 3.1.1. Seja G(V, E) um grafo simples não direcionado onde n = |V | e m = |E|. A
adjacência do vértice v ∈ V será descrita como δ(v). Para facilitar os cálculos vamos definir
nv = |δ(v)| e mv o número de arestas (x, y) ∈ E | x, y ∈ δ(v).
A
B
Figura 3.1: Os dois padrões conexos existentes para k = 3 num grafo não direcionado.
Para um grafo não direcionado existem apenas 2 subgrafos conexos para k = 3, conforme
ilustra a Figura 3.1. Para compreendermos a origem do algoritmo vamos analisar um grafo
simples não direcionado descrito na Figura 3.2 como Estrela. Neste grafo podemos facilmente
contabilizar os padrões para k = 3 de forma intuitiva. Como este grafo não possui nenhum
ciclo, então só teremos como subgrafo o padrão A, descrito na Figura 3.1.
Partindo do vértice central podemos combinar toda a sua adjacência 2 a 2 de modo a formar
padrões do tipo A. Deste modo, com apenas uma operação, calculamos todos os subgrafos do
grafo Estrela. Qualquer outro vértice só possui um vizinho que é o vértice v e não permitirá
fazer a combinação de sua adjacência 2 a 2.
v
v
v 8
n
= 28
=
2
2
Estrela
Frequência
Figura 3.2: Representação do Grafo Estrela e o cálculo para a sua enumeração.
Para generalizar a solução temos que possibilitar a ocorrência do padrão B. Deste modo
podemos gerar todos os subgrafos conexos de tamanho 3 num grafo simples não direcionado.
O padrão B é semelhante ao padrão A, a única diferença é uma aresta (x, y) ∈ E | x, y ∈ δ(v).
Então se existir tal aresta, o subgrafo deixa de ser do tipo A e passa a ser do tipo B. Quanto
Capítulo 3. Algoritmo acc-Motif para k=3
37
a combinação, esta aresta só interfere na combinação dos vértices x, y, qualquer outra combinação não terá interferência desta aresta. Neste caso temos que diminuir em uma ocorrência o
padrão A e acrescentar uma ocorrência ao padrão B. Deste modo o número de ocorrências dos
padrões B pode ser descrito por mv . Já o padrão A deve ser contabilizado o decréscimo dos
padrões B.
Padrões
Frequência
v
n
− mv
2
mv
Figura 3.3: Cálculo da frequência para os padrões descritos na Figura 3.1.
Para finalizar a enumeração temos que contornar um pequeno problema. Como o procedimento de combinação será aplicado a todos os vértices do grafo, então para cada padrão B
teremos a sua ocorrência multiplicada por 3. Para corrigir o problema basta dividir o número
de ocorrências do padrão B por 3. A implementação do método que executa a enumeração de
todos os subgrafos, pode ser visualizada no Algoritmo 11.
1
2
3
4
5
6
7
8
Entrada: Um grafo G(V, E).
Saída: O Histograma Preenchido.
Inicializa o Histograma com valor 0.
Calcula nv e mv para ∀ v ∈ V .
para cada v ∈ V faça
v
n
− mv .
Adiciona ao padrão A o valor
2
Adiciona ao padrão B o valor mv .
fim
Divide o valor total computado para o padrão B por 3.
retorna Histograma
Algoritmo 11: Procedimento de Enumeração para k = 3 num grafo não direcionado.
Como o Algoritmo 11 possui apenas um laço alinhado, então sua complexidade, excluindo
o procedimento da linha 2, é O(n). Agora vamos analisar os cálculos para os valores de nv e
mv . No Algoritmo 12 temos a representação do procedimento para cálculo dos conjuntos de
vizinhos de todos os vértices do grafo. A complexidade deste Algoritmo é O(m).
38
1
2
3
4
Saída: Os conjuntos δ(v) para ∀v ∈ V
para cada aresta (x, y) ∈ E faça
Adiciona x à δ(y).
Adiciona y à δ(x).
fim
Algoritmo 12: Construção dos conjuntos de vizinhos.
O procedimento para cálculo do valor mv pode ser efetuado fazendo com que cada aresta
(x, y) ∈ E | x, y ∈ δ(v) incremente sua existência em mv . Conforme a Figura 3.4, temos que
incrementar o valor de mv para ∀ v ∈ δ(x) ∩ δ(y).
δ(x) ∩ δ(y)
v1 v2 v3
δ(x)\δ(y)
y
x
δ(y)\δ(x)
Figura 3.4: Demostração do cálculo de mv .
O Algoritmo 13 descreve o procedimento para cálculo da variável mv para ∀ v ∈ V . A
complexidade para calcular o conjunto δ(x) ∩ δ(y) é O(min{nx , ny }), assim a complexidade
P
do algoritmo é dada pelo seguinte somatório
min{nx , ny }. Chiba e Nishizek’s [4] com
(x,y)∈E
o objetivo de listar todos os triângulos de um grafo, mostraram que min{nx , ny } = O(a(G)),
onde a(G) é a arboricidade do grafo G. Por definição, a arboricidade de um grafo é o número
mínimo de árvores necessárias para cobrir todas as arestas de um grafo.
√
Eles também mostraram que a complexidade de a(G) é O( m). Deste modo, a complexi√
dade total para o Algoritmo 13 é O(m m).
1
2
3
4
Saída: O valor de mv para ∀ v ∈ V
mv inicializa em 0.
mv ++ para ∀ v ∈ δ(x) ∩ δ(y).
fim
Algoritmo 13: Procedimento para cálculo do valor de mv .
39
A Complexidade do Algoritmo 11, sem análise da linha 2, é O(n). O custo para calcular nv
é O(m), visto que conforme Algoritmo 12, nv = |δ(v)|. Para calcular mv temos a complexidade
√
√
de O(m m), deste modo, a complexidade total para o Algoritmo 11 é O(m m).
3.2 Grafos direcionados
Para fazer a Enumeração em um grafo direcionado, o procedimento é bastante semelhante ao
caso não direcionado. A principal diferença entre os dois é que no caso direcionado existem 3
tipos de vizinhos conforme mostra a Figura 3.5. O conjunto Av representa os vizinhos de v por
meio de uma aresta com dupla direção, já o conjunto B v representa os vizinhos por meio de
uma aresta de saída e o conjunto C v representa os vizinhos cujas arestas entram em v.
Av
v
Bv
Cv
Figura 3.5: Definição dos três tipos de vizinhos no caso direcionado.
Para facilitar a demostração dos cálculos vamos definir algumas notações.
Definição 3.2.1. Seja G(V, E) um grafo simples e direcionado.

v

 A ,
∀u∈V
Bv ,

 v
C ,
se (u, v) ∈ E e (v, u) ∈ E
se (v, u) ∈ E e (u, v) 6∈ E
se (u, v) ∈ E e (v, u) 6∈ E
Definimos v-Patterns como sendo o conjunto de todos os subgrafos de 3 vértices {v, x, y},
onde v é o vértice de referência e x, y ∈ δ(v) são 2 vizinhos do vértice v.
Para facilitar a indicação de arestas bidirecionais (x, y), (y, x) ∈ E, vamos indicá-las
como (x, y)∗ . Definimos também como nvA = |Av |, nvB = |B v | e nvC = |C v |.
Seja mvAB o número de arestas (x, y) ∈ E|x ∈ Av e y ∈ B v e m∗v
AB o número de arestas
bidirecionais (x, y)∗ ∈ E|x ∈ Av e y ∈ B v . O mesmo se segue para as outras combinações
possíveis para os conjuntos Av , B v e C v . Vamos continuar indicando δ(v) como a vizinhança
de v, só que no caso direcionado, δ(v) = Av ∪ B v ∪ C v . Seja V iz v = {Av , B v , C v } o conjunto
contendo todas as classes de conjuntos de vizinhos de v.
3.2. Grafos direcionados
40
Outra diferença entre o problema para grafos direcionados e não direcionados é que a quantidade de padrões sobe de 2 para 13 subgrafos possíveis. Assim os cálculos para a enumeração
ficam mais complexos, pois o número de variáveis do problema aumentam. Antes tínhamos
apenas um conjunto de vizinhos para combinar 2 a 2, como agora temos 3 tipos de vizinhos, é
necessário combinar com repetição todos os 3 conjuntos 2 a 2. Neste caso teremos 6 combinações possíveis: Av Av , Av B v , Av C v , B v B v , B v C v , C v C v . Estas combinações são necessárias
pois qualquer um dos dois vértices x e y, podem pertencer aos conjuntos Av , B v e C v .
A partir destas combinações formamos os 6 padrões de subgrafos acíclicos. Os 7 subgrafos
restantes são variações destes 6 primeiros com acréscimo de uma aresta, gerando assim os
padrões cíclicos. Para calcular a enumeração dos padrões acíclicos quando os dois vizinhos são
do mesmo tipo, é necessário fazer a combinação destes 2 a 2, caso os vizinhos sejam de tipos
diferentes, então fazemos o produto entre eles. Na Figura 3.6 temos a indicação dos padrões e
suas respectivas frequências.
Combinações Padrões
v
Av Av
Frequência
v
Combinações Padrões
v
nA
2
Bv Bv
nvA nvB
v
v
v
A B
v
nvB
2
v
B C
nvB nvC
v
v
Av C v
Frequência
v
nvA nvC
CvCv
nvC
2
Figura 3.6: Cálculo da frequência para os 6 padrões acíclicos.
A Frequência descrita na Figura 3.6 estaria correta se não existissem os padrões cíclicos.
Acontece que cada padrão desta tabela pode se tornar um padrão cíclico com a existência de
uma aresta (x, y) ∈ E|x, y ∈ δ(v). Neste caso, temos que considerar a existência desta aresta
e deduzir a sua ocorrência do padrão acíclico. Existem 3 possibilidades de arestas para fechar
o ciclo, ou seja, podemos ter uma aresta (x, y) ou (y, x) ou (x, y)∗ . Para completar o cálculo
de enumeração temos que analisar a existência dos 3 tipos de arestas e fazer a dedução dos
possíveis novos padrões formados. Este procedimento é idêntico ao que foi feito no caso não
direcionado, a diferença é que agora temos mais variáveis a analisar. Na Figura 3.7 temos a
análise do acréscimo dos 3 tipos de arestas. As arestas que estão sendo acrecidas ao padrão
41
acíclico estão em vermelho. Podemos perceber que nem sempre temos a formação de um
novo padrão, pois alguns subgrafos acabam ficando idênticos. Na primeira linha da Figura 3.7
podemos verificar que o padrão composto pela combinação Av Av , ao adicionarmos uma aresta
(x, y) temos um padrão isomórfico ao subgrafo formado com a adição de uma aresta (y, x).
Neste caso, só fazemos a subtração de mvAA uma única vez. Se ao adicionarmos uma aresta
(x, y) o padrão se tornar diferente dos já analisados então devemos subtrair a sua frequência do
padrão acíclico.
Padrão
Frequência
Padrões e suas Equivalências
v
v
y Av Av x
v
y Av Av x
v
−
v
v
v
y Bv Bv x
−
nvB
2
− mvBB − m∗v
BB
v
nvB nvC −mvBC −mvCB −m∗v
BC
y C v Bv x
v
y Cv Cv x
y Bv
−
y C v Bv x
⇐⇒
y Cv
v
v
v
nvA nvC −mvAC −mvCA −m∗v
AC
−
y Bv Bv x
Bv x
v
v
v
y Bv
y C v Av x
⇐⇒
Bv x
nvA nvB −mvAB −mvBA −m∗v
AB
−
y C v Av x
v
nA
− mvAA − m∗v
AA
2
v
y B v Av x
−
Av x
y Av
−
y B v Av x
Av x
Cv x
−
⇐⇒
Av x
v
y Cv
v
−
y Cv Cv x
y Cv
nvC
2
− mvCC − m∗v
CC
Figura 3.7: Representação de como é feito o cálculo da frequência para os padrões acíclicos.
Fazendo as deduções necessárias, conforme Figura 3.7 completamos as operações necessárias para a enumeração dos padrões acíclicos.
Conforme já apresentado, podemos perceber que quando x e y pertencem ao mesmo conjunto, sempre teremos o mesmo padrão formado com a adição da aresta (x, y) e (y, x). Deste
42
modo podemos padronizar a frequência para quando a combinação for composta por conjuntos
de vizinhos iguais ou quando estesforem diferentes. Para a combinação T T com T ∈ V iz v
nvT
− mvT T − m∗v
teremos a seguinte frequência
T T , quando tivermos a combinação T1 T2 com
2
T1 , T2 ∈ V iz v |T1 6= T2 teremos a frequência nvT1 nvT2 − mvT1 T2 − mvT2 T1 − m∗v
T1 T2 . Estas fórmulas padronizam o cálculo da frequência para as combinações onde não temos aresta entre os
vértices x e y.
Padrão
Frequência
Padrões e suas Equivalências
x Av
v
⇐⇒
y Av
Av x
v
⇐⇒
y Av
+
y Av
v
y Bv C v y
v
v
x Bv C v y
v
Cv x
v
v
mvBB + mvCB + mvCC
y Bv C v y
y Cv
y Cv
v
+
v
Bv x
mvCA + m∗v
BB
x C v Bv y
+
⇐⇒
v
Bv x
x Cv
y Bv
mvAC + mvBA + m∗v
BC
+
v
Bv x
Bv x
y Av
x Cv
v
+
v
Av y
mvAB + m∗v
CC
y Bv C v y
+
⇐⇒
v
Cv x
y Av
y Cv
∗v
mvAA + m∗v
AB + mAC
+
v
Av x
Av x
x Av
y Bv
Av x
v
+
v
⇐⇒
m∗v
AA
Av y
x Av
v
Av x
Av x
v
Bv x
⇐⇒
x Bv C v y
mvBC
v
Figura 3.8: Representação de como é feito o cálculo da frequência para os padrões cíclicos.
43
Agora precisamos calcular a frequência para os outros 7 padrões cíclicos. Do mesmo modo
aplicado ao caso não direcionado, os padrões cíclicos podem ser contabilizados por meio das
arestas (x, y) ∈ E|x, y ∈ δ(v). Quando analisamos o vértice v ocupando as 3 posições do ciclo
no caso não direcionado, obtínhamos as mesmas combinações de conjuntos de vizinhos, pois
este era um k3 , agora no caso direcionado podemos obter combinações diferentes. Para contornar esta possibilidade temos que analisar as 3 posições possíveis para o vértice v e verificar a
que grupo a aresta oposta pertence. Se para as 3 posições tivermos arestas de grupos distintos
então temos que acrescentar o valor de suas ocorrências na frequência do padrão. Na Figura
3.8 temos a representação dos cálculos das frequências para os padrões cíclicos. Nela, podemos
perceber que mesmo variando o vértice v nas 3 posições alguns padrões continuam idênticos,
neste caso, o padrão terá sua frequência representada por arestas de um único grupo. Nesta
figura a aresta na cor azul é aquela que indicará a frequência daquele padrão quando estivermos
analisando o vértice v. Com as tabelas da Figura 3.7 e 3.8, temos a frequência para todos os 13
padrões existentes em grafos direcionados para k = 3.
O Algoritmo 14 representa o método para enumeração dos 13 padrões existentes em grafos
direcionados. Excluindo a complexidade das linhas 2 e 3 podemos verificar que a complexidade
do algoritmo é a mesma do algoritmo não direcionado, ou seja, O(n). Este algoritmo pode
ser facilmente paralelizável, pois o cálculo da frequência para um vértice v só depende das
∗v
variáveis: {nvA , nvB , nvC }, {mvAA , . . . , mvCC } e {m∗v
AA , . . . , mCC }. Deste modo, cada vértice
pode ser processado separadamente. Por exemplo, na linha 4 de algoritmo, temos um laço que
varre todos os vértices do grafo. Este laço pode ser dividido por várias threads e cada núcleo
poderia processar um intervalo diferente de vértices. Ao final podemos fazer um merge dos
histogramas, somando os valores computados em cada padrão em um único histograma.
1
2
3
4
5
6
7
8
9
10
Calcula {nvA , nvB , nvC } para todo v ∈ V .
∗v
Calcula {mvAA , . . . , mvCC } e {m∗v
AA , . . . , mCC } para todo v ∈ V .
para cada v ∈ V faça
Calcula a frequência para os 13 padrões descritas nas Figuras 3.7 e 3.8.
Para cada padrão adiciona a sua frequência ao histograma.
fim
Divide o valor total computado para os padrões da Figura 3.8 por 3.
retorna Histograma
Algoritmo 14: Procedimento de Enumeração para k = 3 num grafo direcionado.
44
Agora vamos analisar o algoritmo para construção dos conjuntos de vizinhos e dos valores
∗v
de {mvAA , . . . , mvCC } e {m∗v
AA , . . . , mCC }.
1
2
3
4
5
6
7
8
9
10
Saída: Os conjuntos Av , B v e C v para ∀ v ∈ V
para cada aresta e ∈ E faça
se e = (x, y)∗ então
Adiciona x à Ay .
Adiciona y à Ax .
fim
se e = (x, y) então
Adiciona x à C y .
Adiciona y à B x .
fim
fim
Algoritmo 15: Cálculo dos conjuntos Av , B v e C v .
∗v
Saída: O valor de {mvAA , . . . , mvCC } e {m∗v
AA , . . . , mCC } para ∀ v ∈ V
v
v
1 Inicializa em 0 o valor de mT T para ∀ T1 , T2 ∈ V iz .
1 2
2 para cada aresta e ∈ E faça
Para
Se e = (x, y)∗
Se e = (x, y)
x
y
∀v ∈A ∩A
m∗v
++
mvAA ++
AA
∀ v ∈ Ax ∩ C y
m∗v
mvAB ++
AB ++
∀ v ∈ Ax ∩ B y
m∗v
mvAC ++
AC ++
x
y
∗v
∀v ∈C ∩A
mAB ++
mvBA ++
3
∀ v ∈ Cx ∩ Cy
m∗v
mvBB ++
BB ++
∀ v ∈ C x ∩ By
m∗v
mvBC ++
BC ++
x
y
∗v
∀v ∈B ∩A
mAC ++
mvCA ++
∀ v ∈ Bx ∩ C y
m∗v
mvCB ++
BC ++
x
y
∗v
∀v ∈B ∩B
mCC ++
mvCC ++
4 fim
∗v
Algoritmo 16: Procedimento para cálculo do valor de {mvAA , . . . , mvCC } e {m∗v
AA , . . . , mCC }.
O método para construção dos conjuntos Av , B v e C v , está implementado no Algoritmo 15.
Este método difere pouco do Algoritmo 12 para o caso não direcionado. A diferença está na
construção dos conjuntos de vizinhos, mas mantém a mesma complexidade, ou seja, O(m).
Já o Algoritmo 16 representa o procedimento para construção das variáveis {mvAA , . . . , mvCC }
∗v
e {m∗v
AA , . . . , mCC }. Neste algoritmo são calculados 9 interseções para cada aresta e ∈ E.
√
A complexidade para calcular cada interseção é O( m), conforme apresentado por Chiba e
45
√
Nishizek’s [4]. Deste modo a complexidade total do algoritmo é O(m m). Conforme já espe√
rávamos, a complexidade do Algoritmo 14 é a mesma do Algoritmo 11 , ou seja, O(m m).
mvAC ++
mvAB ++
mvAA ++
v2
v3
mvBA ++
v4
mvBB ++
v1
Cx
Bx
Ax
v5
y
x
v6
v
mBC ++
v7
v
mCA ++
v8
v
mCB ++
Cy
By
Ay
v9
v
mCC ++
Figura 3.9: Demostração do cálculo de {mvAA , . . . , mvCC }.
Na Figura 3.9 temos a representação esquemática das 9 combinações dos conjuntos de vizinhos Av , B v e C v . Nela está descrita uma aresta (x, y) ∈ E e as 9 situações possíveis para
v ∈ δ(x) ∩ δ(y). Para cada situação temos a indicação da variável a ser incrementada. Podemos
perceber que quando (x, y) é uma aresta direcional a ordem dos conjuntos de vizinhos entre x
e y interfere no resultado, por este motivo mvAC 6= mvCA .
∗v
Quando temos (x, y)∗ a ordem dos conjuntos não é relevante, ou seja, m∗v
AC = mCA . A
∗v
∗v
∗v
∗v
∗v
Figura 3.10 temos a descrição de como as 6 variáveis {m∗v
AA , mAB , mAC mBB , mBC , mCC } são
incrementadas.
3.3 Resultados
O acc-Motif foi implementado em JAVA. Seu desempenho se mostrou bastante promissor com
relação ao FANMOD [21] e o Kavosh [7]. Estes dois últimos algoritmos estão implementados
em C++ e são os mais rápidos desenvolvidos até o momento. O acc-Motif foi mais rápido em
todos os grafos testados. Em alguns casos chegou a ser 251 vezes mais rápido que o FANMOD
e 64 vezes mais rápido que o Kavosh. Todos os testes para k = 3 foram feitos rodando o
algoritmo 5 vezes e com 100 grafos aleatórios.
3.3. Resultados
46
m∗v
AB ++
m∗v
AA ++
v2
v1
Cx
Bx
Ax
m∗v
AC ++
v3
y
x
v4
∗v
mBB ++
v5
∗v
mBC ++
Cy
By
Ay
v6
∗v
mCC ++
∗v
Figura 3.10: Demonstração do cálculo de {m∗v
AA , . . . , mCC } .
Tabela 3.1: Tempo de Enumeração para k = 3 em milissegundos para alguns grafos.
Grafos
E.coli [2]
CSphd [3]
Levedura [2]
Roget [3]
Epa [3]
California [3]
Facebook [18]
ODLIS [3]
PairsFSG [3]
Airport [18]
Foldoc [3]
Words E. [2]
(n,m)
(418, 519)
(1882, 1740)
(688, 1079)
(1022, 5074)
(4271, 8965)
(6175, 16150)
(1899, 20296)
(2900, 18241)
(5018, 63608)
(1574, 28236)
(12905, 109092)
(7381, 46281)
FANMOD
8, 00 ± 0, 26
9, 70 ± 0, 12
22, 91 ± 0, 15
53, 54 ± 0, 78
392, 16 ± 0, 96
638, 26 ± 1, 31
1489, 78 ± 1, 14
3260, 12 ± 5, 05
3981, 49 ± 11, 77
6013, 60 ± 2, 40
7806, 14 ± 22, 94
24558, 38 ± 71, 99
Kavosh
4, 6 ± 0, 02
5, 66 ± 0, 05
11, 71 ± 0, 12
30, 29 ± 0, 28
211, 82 ± 0, 64
328, 23 ± 1, 21
604, 51 ± 3, 73
985, 67 ± 2, 52
1991, 94 ± 6, 44
1314, 18 ± 3, 04
2207, 32 ± 10, 94
6328, 85 ± 65, 02
acc-Motif
0, 14 ± 0, 01
0, 74 ± 0, 05
0, 30 ± 0, 04
2, 25 ± 0, 23
4, 39 ± 0, 08
12, 70 ± 0, 21
19, 30 ± 0, 14
20, 89 ± 0, 56
97, 72 ± 1, 69
32, 83 ± 1, 63
182, 74 ± 0, 89
81, 89 ± 1, 38
Na Tabela 3.1, temos o tempo gasto por grafo para fazer a enumeração de alguns grafos
disponíveis na rede. O tempo na Tabela 3.1 foi medido em milissegundos e está acompanhado
de seu desvio padrão. Os testes foram feitos utilizando apenas uma thread e a máquina onde
foi rodado os testes, possuía as seguintes configurações: Intel(R) Core(TM)2 Duo CPU T6600,
2.20 GHz, 3 GB RAM.
(a) Grafos pequenos.
47
(b) Grafos médios.
(c) Grafos grandes.
Figura 3.11: Gráfico contendo o tempo de Enumeração em milissegundos para k = 3 nos
grafos descritos na Tabela 3.1.
Na Figura 3.11 temos os gráficos dos tempos de enumeração para os grafos da Tabela 3.1.
Os grafos foram separados por ordem de grandeza, para que os tempos dos grafos menores não
fiquem achatados no gráfico em função dos grafos maiores. Nestes gráficos podemos perceber
que o acc-Motif possui um custo computacional bem inferior aos outros algoritmos.
Podemos fazer um comparativo do ganho computacional entre os 3 algoritmos. Seja Ta , Tk
e Tf o tempo de Enumeração respectivamente do acc-Motif, Kavosh, e FANMOD. O ganho
computacional será representado pelo número de vezes que um algoritmo foi mais rápido que
outro. Neste caso, teremos Tk /Ta indicando o número de vezes que o acc-Motif foi mais rápido
que o Kavosh, para Tf /Ta temos o número de vezes que o acc-Motif foi mais rápido que o
FANMOD e Tf /Tk indica o número de vezes que o Kavosh foi mais rápido que o FANMOD.
Na Figura 3.12 temos a indicação dos valores de Tk /Ta , Tf /Ta e Tf /Tk calculados para
os tempos indicados na Tabela 3.1. Neste gráfico o conjunto de teste foi ordenado de forma
crescente com relação aos valores de Tf /Ta . Calculando a média dos valores de Tk /Ta , temos
3.3. Resultados
48
que em média, o acc-Motif é 32 vezes mais rápido que o Kavosh. Para os valores de Tf /Ta ,
temos que em média, o acc-Motif foi 91 vezes mais rápido que o FANMOD e para Tf /Tk ,
temos que o Kavosh é 2,5 vezes mais rápido que o FANMOD.
Com este resultado temos a proporção do ganho computacional apresentado pelo acc-Motif.
Figura 3.12: Gráfico contendo os valores de Tk /Ta , Tf /Ta e Tf /Tk para o conjunto de teste
indicados na Tabela 3.1.
3.3.1
Avaliação em grafos aleatórios
Foram feitos testes também com grafos aleatórios conforme o Algoritmo 10. Os grafos foram
construídos com 5000 vértices e com o número de arestas variando de 5000 em 5000. O primeiro iniciou com 5000 arestas, gerando um grafo com grau médio igual a 1 e o último continha
100 mil arestas dando origem a um grafo com uma média de 20 arestas por vértice.
A Figura 3.13 representa os gráficos do tempo de enumeração para os grafos aleatórios descritos acima. Pela curva do gráfico podemos perceber que o custo computacional do algoritmo
cresce de maneira aproximadamente linear com relação ao número de arestas, confirmando as√
sim a complexidade O(m m). Os tempos registrados neste teste estão descritos na Tabela A.1.
Utilizando os resultados do teste anterior, podemos analisar o custo para fazer a enumeração
por subgrafo. Deste modo podemos saber se o custo para enumerar cada subgrafo aumenta ou
diminui conforme o grafo fica mais denso ou esparso.
Na Figura 3.14 temos um gráfico que mostra a desempenho dos 3 algoritmos com relação
ao número de subgrafos. Nela, podemos perceber que no FANMOD o custo para contabilizar
49
Figura 3.13: Gráfico contendo o tempo de Enumeração em milissegundos para k = 3 em grafos aleatórios.
um subgrafo aumenta conforme o grafo fica mais denso. Este comportamento acarreta um
crescimento exponencial do tempo de execução do algoritmo conforme o número de arestas no
grafo aumenta.
O acc-Motif e o Kavosh possuem uma curva semelhante, indicando que o custo para contabilizar um subgrafo diminui conforme o grafo fica mais denso. A diferença entre os dois é que o
acc-Motif possui uma constante menor, ou seja, o custo computacional para cada subgrafo é inferior. Também constatamos que no acc-Motif, o custo diminui mais aceleradamente conforme
o grafo fica mais denso em comparação ao Kavosh. Por exemplo, o custo inicial no acc-Motif
foi de 356 nanossegundos por subgrafo. Ao final chegamos ao custo de 68 nanossegundos por
subgrafo, representando uma diminuição de 81%. O Kavosh iniciou com 1094 nanossegundos
por subgrafo e terminou com 885 nanossegundos por subgrafo, incorrendo numa diminuição de
19%. Já o FANMOD apresentou um aumento de 62% com relação ao custo inicial.
50
3.3. Resultados
Figura 3.14: Gráfico contendo o tempo de Enumeração por subgrafo em nanossegundos para
k = 3 em grafos aleatórios.
C APÍTULO
4
Antes de apresentar o algoritmo para k = 4 utilizado pelo acc-Motif [14], faremos uma análise
da estrutura a ser utilizada. Para subgrafos de tamanho 4 é necessário que tenhamos uma estrutura maior do que a utilizada para k = 3, pois para calcularmos o padrão descrito na Figura
4.1, também conhecido como caminho de comprimento 4, partindo do vértice v, teríamos que
analisar 3 vértices adjacentes sendo que um destes teria que estar a distância 2 de v.
v
Figura 4.1: Caminho de comprimento 4.
Os cálculos seriam mais complexos se partíssemos da mesma base utilizada para k = 3.
No entanto, utilizando como estrutura básica uma aresta, ao invés de um vértice, precisaríamos
apenas calcular a combinação de 2 vértices adjacentes a esta estrutura. Além disto, estes 2
vértices estariam numa vizinhança imediata, facilitando assim, os cálculos de frequência para
cada padrão.
51
52
4.1 Grafos não direcionados
Para calcularmos as frequências de todos os subgrafos de 4 vértices que contenham a aresta e
em sua posição central temos que analisar todos os possíveis subgrafos formados a partir de
dois vizinhos desta aresta.
Definição 4.1.1. Seja e-Patterns o conjunto de todos os subgrafos de 4 vértices {u, v, x, y},
onde e = (u, v) é a aresta central e x, y ∈ δ(e) = δ(u) ∪ δ(v) \ {u, v} são os dois vértices
vizinhos a aresta e.
Vamos definir também X e = δ(u) \ (δ(v) ∪ u), Y e = δ(v) \ (δ(u) ∪ v) e Z e = δ(u) ∩ δ(v) \
{u, v}. Os conjuntos X e , Y e e Z e estão descritos na Figura 4.2.
Para facilitar os cálculos vamos estabelecer neX = |X e |, neY = |Y e | e neZ = |Z e |. Do
mesmo modo aplicado a k = 3, vamos representar o número de arestas (x, y) ∈ E ∗ |x ∈ X e e
y ∈ Z e como meXZ e assim sucessivamente para todas as combinações de X e , Y e e Z e . Como
temos 3 tipos de vizinhos, ao combinarmos estes 2 a 2 com repetição teremos 6 pares possíveis
formando as variáveis {meXX , meXY , meXZ , meY Y , meY Z , meZZ }.
Ze
Xe
u
e
v
Ye
Figura 4.2: Definição dos 3 tipos de vizinhos para a aresta e.
Como temos 3 tipos de vizinhos e precisamos analisar a aresta e com adição de 2 vizinhos,
é necessário fazer a combinação destes 3 conjuntos 2 a 2. Deste modo teremos as combinações
X e X e , X e Y e , X e Z e , Y e Y e , Y e Z e , Z e Z e . A combinação X e Z e representa que x ∈ X e e y ∈
Z e , e o mesmo se segue para as outras combinações.
Para que o cálculo da frequência dos padrões esteja completa precisamos analisar duas situações possíveis. A primeira delas é a frequência dos padrões formados pelos 6 pares de combinações dos conjuntos de vizinhos sem aresta entre os vértices x, y, ou seja, (x, y) 6∈ E|x, y ∈ δ(e).
A segunda análise seria levando em consideração esta aresta (x, y). Deste modo estaremos varrendo todos os pares de vizinhos possíveis com ou sem aresta entre eles, ou seja, estaremos
levando em consideração todos os padrões possíveis.
53
Apresentaremos, inicialmente, o primeiro caso em que (x, y) 6∈ E. Como não estamos
levando em consideração a aresta (x, y), então a frequência será dada pela combinação de seus
vizinhos, ou seja, quando os dois vizinhos forem do mesmo conjunto, a frequência para este
padrão será indicada pela combinação deste 2 a 2, caso contrário a frequência será o produto
entre eles. Este procedimento é idêntico ao aplicado para k = 3. Contudo, devemos deduzir a
frequência da aresta (x, y), pois neste caso os padrões analisados não terão esta aresta.
Tabela 4.1: Representação dos subgrafos formados pelas 6 combinações dos conjuntos de vizinhos sem a aresta (x, y).
Par
Padrões
Frequência
Par
Padrões
Frequência
y
e
X X
y
e
e
u
v
neX
2
−
meXX
e
Y Y
e
e
u
v
x
X Y
y
neX neY
e
v
−
meXY
Y eZ e
x
X Z
x
u
e
e
u
y
e
− meY Y
y
e
u
e
x
x
e
neY
2
v
neX neZ − meXZ
v
y
x
e
Z Z
e
u
e
v
neY neZ − meY Z
neZ
2
− meZZ
Conforme descrito na Tabela 4.1, temos os 6 subgrafos formados pelas combinações descritas acima e suas respectivas frequências. Nela, podemos verificar que os subgrafos formados pela combinação X e X e e Y e Y e são isomorfos. Desta forma é necessário somar as suas
frequências, pois representam um único padrão. O mesmo se aplica as combinações X e Z e e
Y e Z e . Contudo ainda temos que analisar a frequência dos padrões formados pelos 6 pares de
combinações dos conjuntos de vizinhos levando em consideração a existência da aresta (x, y).
A frequência dos padrões que possuem a aresta (x, y), será indicada pelo valor de me . Esta
abordagem é idêntica a apresentada no problema para k = 3.
Desta forma a Tabela 4.2 ilustra os 6 subgrafos formados pela combinação de dois vizinhos
incluindo a aresta (x, y) e suas respectivas frequências.
A partir das Tabelas 4.1 e 4.2 podemos identificar que ocorre isomorfismo em diversos
subgrafos. Para contornar o problema basta representar os subgrafos num único padrão e somar
as suas frequências, pois elas representam todas as situações em que o padrão poderá ocorrer.
Para identificar os padrões isomorfos temos os seguintes agrupamentos:
54
Tabela 4.2: Representação dos subgrafos formados pelas 6 combinações dos conjuntos de vizinhos com a aresta (x, y).
Par
Padrões
Frequência
Par
Padrões
Frequência
y
y
X eX e
e
u
v
meXX
Y eY e
e
u
meY Y
v
x
x
y
x
e
X Y
y
e
meXY
e
u
e
Y Z
e
v
x
y
X eZ e
x
u
e
e
u
meXZ
v
y
x
Z eZ e
v
u
meY Z
e
meZZ
v
1. {X e X e , Y e Y e } ⊂ Tabela 4.1.
2. { X e Z e , Y e Z e } ⊂ Tabela 4.1 ∪ {X e X e , Y e Y e } ⊂ Tabela 4.2.
3. {Z e Z e } ⊂ Tabela 4.1 ∪ {X e Z e , Y e Z e } ⊂ Tabela 4.2.
Fazendo as devidas junções, somando as frequências dos padrões isomórficos, podemos
verificar na Tabela 4.3, a frequência final para os 6 padrões de tamanho 4 existentes em grafos
não direcionados.
Contudo, a frequência ainda não representa na integra o número de subgrafos de e-Patterns,
pois do mesmo modo que ocorre ambiguidade para k = 3, aqui também temos que contornar
este inconveniente. No caso anterior, tínhamos que dividir por 3 os padrões cíclicos, pois este é
o número de vértices pelo qual podemos enumerar o padrão. Para k = 4, a enumeração é feita
por arestas, então temos que dividir a frequência do padrão pelo número de arestas que podem
enumerar aquele padrão.
A Tabela 4.4 temos um exemplo das arestas que enumeram o padrão e a combinação que
gerou a frequência para aquela aresta e. Assim podemos saber quais as arestas que podem
enumerar determinado padrão e identificar o valor do divisor.
Na Tabela 4.5 temos a indicação das possíveis posições para a aresta e mostrando o número
de ambiguidades na frequência do padrão. O divisor é o fator que ao fim da enumeração dividirá
o valor da frequência.
55
Tabela 4.3: Representação da frequência para os 6 padrões de tamanho 4 em grafos não direcionados.
Padrões
Frequência
neX
2
neZ
2
neY
+
2
Padrões
Frequência
neX neY − meXY
− meXX − meY Y
meXY
− meZZ + meXZ + meY Z
(neX + neY )neZ − meXZ − meY Z +
meXX + meY Y
meZZ
Tabela 4.4: Exemplo de padrão indicando as arestas que enumeram o padrão.
e
Posições para a
Aresta e
e
e
X e X e e Y e Y e da Tabela 4.2
Combinações
X e Z e e Y e Z e da Tabela 4.1
Tabela 4.5: Indicação do número de arestas que enumeram o padrão.
Padrões
e
e
Divisor
3
Padrões
e
e
e
e
e
e
Divisor
Padrões
Divisor
5
e
3
e
1
e
e
e
e
e
e
4
e
e
e
e
e
e
6
56
1
2
3
4
5
6
7
8
9
Calcula {neX , neY , neZ } para ∀ e ∈ E.
Calcula {meXX , meXY , meXZ , meY Y , meY Z , meZZ } para ∀ e ∈ E.
para cada e ∈ E faça
Calcula a frequência para os 6 padrões descrita Tabela 4.3.
Para cada padrão adiciona a sua frequência ao histograma.
fim
Divide o valor total computado para os padrões, conforme divisor da Tabela 4.5.
retorna Histograma
Algoritmo 17: Procedimento de Enumeração para k = 4 num grafo não direcionado.
O Algoritmo 17 implementa o método de enumeração para subgrafos de tamanho 4 em grafos não direcionados. Sua complexidade excluindo a linha 2 e 3 é O(m). Agora vamos analisar
a complexidade para gerar os conjuntos X e , Y e , Z e e as variáveis {meXX , meXY , meXZ , meY Y ,
meY Z , meZZ }.
1
2
3
4
5
Saída: Os conjuntos X e , Y e e Z e para ∀ e ∈ E
para cada aresta e = (u, v) ∈ E ∗ faça
Z e = δ(u) ∩ δ(v) \ {u, v}
X e = δ(u) \ (δ(v) ∪ u)
Y e = δ(v) \ (δ(u) ∪ v)
fim
Algoritmo 18: Cálculo dos conjuntos X e , Y e e Z e .
O Algoritmo 18 representa o método para construção dos conjuntos X e , Y e , Z e . Conside-
rando o custo computacional para calcular δ(u)∩δ(v) = O(min{nu , nv }), podemos representar
P
min{nu , nv }. Conforme apresentado por
a complexidade do algoritmo pelo somatório
∗
(u,v)∈E
√
Chiba e Nishizek’s [4], a complexidade deste agoritmo é O(m m).
O método para construção das variáveis {meXX , meXY , meXZ , meY Y , meY Z , meZZ } está imple-
mentado no Algoritmo 19. A complexidade do método, conforme as linhas 1 e 2, é O(m2 ).
Na Figura 4.3 as arestas indicadas condicionam os incrementos das variáveis meXX , meXY ,
meXZ , meY Y , meY Z e meZZ com relação a aresta e.
√
No Algoritmo 17, a complexidade da linha 2 é O(m m) e a complexidade da linha 3 é
O(m2 ). Deste modo a complexidade total do algoritmo é O(m2 ).
57
Entrada: Um grafo G∗ (V, E ∗ ).
Saída: O valor de {meXX , meXY , meXZ , meY Y , meY Z , meZZ } para ∀ e ∈ E ∗
e
1 m inicializa em 0.
∗
2 para cada aresta e = (u, v) ∈ E faça
3
para cada aresta (x, y) ∈ E ∗ faça
Se os vértices
Faça
e
e
x∈X ey∈X
meXX ++
x ∈ Xe e y ∈ Y e
meXY ++
e
e
4
x∈X ey∈Z
meXZ ++
x∈Ye ey ∈ Ye
meY Y ++
x ∈ Y e e y ∈ Ze
meY Z ++
e
e
x∈Z ey∈Z
meZZ ++
5
fim
6 fim
Algoritmo 19: Procedimento para cálculo do valor de {meXX , meXY , meXZ , meY Y , meY Z , meZZ }.
meXY ++
meZZ ++
meXX ++
e
u
meXZ ++
v
meY Y ++
meY Z ++
Figura 4.3: Definição dos 3 tipos de vizinhos para a aresta e.
4.2 Grafos direcionados
A solução para grafos direcionados é bastante semelhante à utilizada em grafos não direcionados. O que difere é o número de variáveis do problema e a quantidade de conjuntos de vizinhos.
Definição 4.2.1. São 15 tipos de vizinhos diferentes conforme mostra a Figura 4.4.
Os conjuntos Ae1 = Au \ (δ(v) ∪ {v}), B1e = B u \ (δ(v) ∪ {v}) e C1e = C u \ (δ(v) ∪ {v}),
representam os conjuntos vizinhos de u mas que não são vizinhos de v.
Os conjuntos Ae2 = Av \ (δ(u) ∪ {u}), B2e = B v \ (δ(u) ∪ {u}) e C2e = C v \ (δ(u) ∪ {u}),
são os conjuntos de vizinhos de v que não são vizinhos de u.
58
Temos também os conjuntos AAe = Au ∩ Av , AB e = Au ∩ B v , AC e = Au ∩ C v , BAe =
B u ∩Av , BB e = B u ∩B v , BC e = B u ∩C v , CAe = C u ∩Av , CB e = C u ∩B v , CC e = C u ∩C v ,
que indicam os conjuntos de vizinhos por meio de intersecção entre u e v.
Desse modo, V iz e = {Ae1 , B1e , C1e , Ae2 , B2e , C2e , AAe , AB e , AC e , BAe , BB e , BC e , CAe , CB e , CC e }.
Dado um conjunto T ∈ V iz e , definimos como neT = |T |. Definimos como meT1 T2 o número de
arestas (x, y) ∈ E|x ∈ T1 e y ∈ T2 , onde T1 , T2 ∈ V iz e . Definimos como m∗e
T1 T2 o número de
arestas (x, y)∗ ∈ E|x ∈ T1 e y ∈ T2 .
AC e
AB e
BAe
AAe
BB e
C1e
B1e
C2e
e
u
v
Ae1
B2e
Ae2
BC e
CC e
CAe
CB e
Figura 4.4: Representação dos 15 tipos de vizinhos da aresta e.
Para computar a frequência de todos os 199 padrões de tamanho 4 em grafos direcionados é
necessário analisar todas as combinações de vizinhos 2 a 2 para que todos os padrões existentes
sejam levados em consideração. Este procedimento é idêntico ao que foi utilizado no caso não
direcionado.
Para representar o padrão formado por determinada combinação T1 , T2 ∈ V iz e , utilizaremos a função Padrão(e, T1, T2 ) que retornará a identificação do padrão formando pela aresta e
mais dois vizinhos x, y tal que x ∈ T1 e y ∈ T2 . A aresta e pode ser direcional ou bidirecional,
por este motivo, ela deve constar na função Padrão, pois dependendo do tipo de aresta e teremos a formação de um padrão diferente. Com relação aos vértices x, y temos quatro situações
possíveis para cada combinação. Podemos ter uma aresta (x, y), ou uma aresta (y, x), ou uma
aresta (x, y)∗, ou não possuir aresta entre os vértices x, y.
59
Para ilustrar estas variações vamos exemplificar na Tabela 4.6 os padrões formados pela
aresta e = (u, v)∗ e x ∈ Ae1 e y ∈ CC e . Como podemos ver, temos 4 funções distintas:
Padrão(e, T1, T2 ) quando não temos arestas entre x e y, Padrão→(e, T1 , T2 ) quando tivermos a
aresta (x, y), Padrão← (e, T1 , T2 ) quando existir uma aresta (y, x) e Padrão↔(e, T1 , T2 ) para os
padrões que possuem uma aresta (x, y)∗ .
Na Figura 4.7 temos a representação de todos os padrões formados pela função Padrão(e, T1 , T2 )
com T1 , T2 ∈ V iz e . A aresta na cor azul representa a relação entre os vértices x e y, podendo
esta assumir 4 situações conforme mostra a Figura 4.6. A aresta e pode ser igual a (u, v) ou
(u, v)∗.
Tabela 4.6: Exemplo de retorno para as funções: Padrão(e, T1 , T2 ), Padrão→ (e, T1 , T2 ),
Padrão← (e, T1 , T2 ) e Padrão↔(e, T1 , T2 ).
Padrão Formado
e
e
e
Padrão→ (e, Ae1 , CC e )
Possui uma aresta (x, y).
Padrão← (e, Ae1 , CC e )
Possui uma aresta (y, x).
Padrão↔ (e, Ae1 , CC e )
Possui uma aresta (x, y)∗ .
v
v
v
y
x
u
Sem a aresta entre x e y.
y
x
u
Padrão(e, Ae1, CC e )
y
x
u
Característica
y
x
u
Função Correspondente
e
v
Devido à quantidade de padrões a frequência de cada padrão será feita termo a termo, ou
seja, para cada par de combinação dos conjuntos de vizinhos será feito o incremento no respectivo padrão formado por aquela combinação.
Para que possamos fazer o cálculo da frequência por partes é necessário que o número
de ocorrências para cada termo esteja padronizado. Para analisar todas as combinações de
vizinhos temos que tratar duas situações distintas. A primeira delas é quando a combinação
é composta por um único conjunto, ou seja, x, y ∈ T | T ∈ V iz e . Neste caso a frequência
60
Tabela 4.7: Representa todos os padrões formados pela função Padrão(e, T1, T2 ) para T1 , T2 ∈
V iz e .
Ae1
B1e
C1e
Ae2
B2e
C2e
AAe
AB e AC e
BAe BB e BC e CAe CB e CC e
Ae1
B1e
C1e
Ae2
B2e
C2e
AAe
AB e
AC e
BAe
BB e
BC e
CAe
CB e
CC e
neT
. Como este padrão não possui
para o Padrão(e, T, T ) desprezando as arestas entre x, y é
2
arestas entre os vértices x, y então é necessário deduzir a ocorrência destas arestas. No caso
direcionado temos 3 tipos de arestas possíveis: (x, y), (y, x) e (x, y)∗. Como x e y pertence ao
mesmo conjunto, o número de ocorrências de arestas (x, y)é o mesmo de ocorrências de arestas
neT
(y, x). Neste caso a frequência para o Padrão(e, T, T ) =
− meT T − m∗e
TT .
2
Para o Padrão→(e, T, T ) temos que a sua ocorrência será dada por meT T . Como este padrão é
idêntico ao Padrão←(e, T, T ) então só faremos o computo uma única vez. O Padrão↔(e, T, T )
será representado por m∗e
TT .
61
A segundo caso trata as combinações cujos vizinhos são diferentes, ou seja, quando x ∈ T1
e y ∈ T2 | T1 6= T2 e T1 , T2 ∈ V iz e . Neste caso a frequência para o Padrão(e, T1 , T2 ) = neT1 neT2 ,
fazendo as deduções em função de não possuir aresta entre x, y temos que a frequência para
→
o Padrão(e, T1 , T2 ) = neT1 neT2 − meT1 T2 − meT2 T1 − m∗e
T1 T2 . Já o Padrão (e, T1 , T2 ) terá sua
frequência indicada por meT1 T2 .
O Padrão← (e, T2 , T1 ) será representado por meT2 T1 e por último temos o Padrão↔(e, T1 , T2 )
que será indicado pelo valor de m∗e
T1 T2 .
A partir do cálculo da frequência estabelecido para cada combinação podemos computar o
número de ocorrência para todos os padrões de tamanho 4 em grafos direcionados.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Calcula neT para ∀ e ∈ E e para ∀ T ∈ V iz e .
e
Calcula meT1 T2 e m∗e
T1 T2 para ∀ e ∈ E e para ∀ T1 , T2 ∈ V iz .
para cada aresta e ∈ E faça
para cada T ∈ V iz e faça
e
nT
− meT T − m∗e
Frequência [Padrão(e, T, T )]+ =
TT .
2
Frequência [Padrão→ (e, T, T )]+ = meT T .
Frequência [Padrão↔ (e, T, T )]+ = m∗e
TT .
fim
para cada T1 , T2 ∈ V iz e faça
Frequência [Padrão(e, T1, T2 )]+ = neT1 neT2 − meT1 T2 − meT2 T1 − m∗e
T1 T2 .
Frequência [Padrão→ (e, T1 , T2 )]+ = meT1 T2 .
Frequência [Padrão← (e, T1 , T2 )]+ = meT2 T1 .
Frequência [Padrão↔ (e, T1 , T2 )]+ = m∗e
T1 T2 .
fim
fim
Divide o valor total computado para cada padrão pelo seu respectivo divisor, cuja a
estrutura é equivalente aos padrões da Tabela 4.5.
retorna Histograma
Algoritmo 20: Procedimento de Enumeração para k = 4 num grafo direcionado.
O Algoritmo 20 implementa o método de enumeração para k = 4. Sua complexidade
excluindo a linha 2 e 3 é O(m). Podemos perceber que para cada aresta do grafo calcularemos
a frequência para os 199 padrões, ou seja, mesmo que um padrão não exista, este será calculado
pelo algoritmo. A diferença é que neste caso o cálculo da frequência para este padrão em todas
as arestas será zero. Deste modo podemos concluir que quanto a classificação, o algoritmo é
centrado no Motif. Se quisermos encontrar um padrão específico podemos fazer um filtro no
laço da linha 5 e ao invés de calcularmos todos os 199 padrões, podemos especificar um único
4.3. Resultados
62
padrão. Mesmo calculando a frequência para um único padrão, a complexidade do algoritmo
será a mesma.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Saída: Os conjuntos T ∈ V iz e para ∀ e ∈ E
para cada aresta e = (u, v) ∈ E faça
Ae1 = Au \ (δ(v) ∪ {v})
B1e = B u \ (δ(v) ∪ {v})
C1e = C u \ (δ(v) ∪ {v})
Ae2 = Av \ (δ(u) ∪ {u})
B2e = B v \ (δ(u) ∪ {u})
C2e = C v \ (δ(u) ∪ {u})
AAe = Au ∩ Av
AB e = Au ∩ B v
AC e = Au ∩ C v
BAe = B u ∩ Av
BB e = B u ∩ B v
BC e = B u ∩ C v
CAe = C u ∩ Av
CB e = C u ∩ B v
CC e = C u ∩ C v
fim
Algoritmo 21: Cálculo do conjunto V iz e para ∀ e ∈ E.
O Algoritmo 21 implementa a construção do conjunto V iz e . Sua complexidade é idêntica
√
ao do Algoritmo 18, ou seja, O(m m), a diferença é que neste caso temos 15 conjuntos de
vizinhos.
e
O Algoritmo 22 implementa a construção das variáveis meT1 T2 e m∗e
T1 T2 | T1 , T2 ∈ V iz para
∀ e ∈ E. A complexidade do método, conforme linha 1 e 2, é O(m2 ), ou seja, é a mesma do
Algoritmo 19.
Podemos concluir que a a complexidade total do Algoritmo 20 é O(m2 ), conforme linha 3.
4.3 Resultados
Nesta seção serão apresentados os resultados quanto ao desempenho computacional para executar o processo de Enumeração para k = 4 em grafos direcionados. O acc-Motif foi comparado
em relação ao FANMOD [21] e o Kavosh [7] que são os algoritmos mais rápidos atualmente
para detectar Motifs.
O acc-Motif se mostrou mais rápido em todos os grafos testados, em alguns casos chegou a
ser 249 vezes mais rápido que o FANMOD e 85 vezes mais rápido que o Kavosh, como foi o
63
e
Saída: O valor de meT1 T2 e m∗e
T1 T2 | T1 , T2 ∈ V iz para ∀ e ∈ E
1 para cada aresta e ∈ E faça
2
3
se x ∈ T1 e y ∈ T2 | T1 , T2 ∈ V iz e então
4
se (x, y) é bidirecional & x < y então
5
m∗e
T1 T2 ++
6
fim
7
se (x, y) é direcional então
8
meT1 T2 ++
9
fim
10
fim
11
fim
12 fim
e
Algoritmo 22: Procedimento para cálculo do valor de meT1 T2 e m∗e
T1 T2 | T1 , T2 ∈ V iz para
∀ e ∈ E.
Tabela 4.8: Tempo de Enumeração para k = 4 em segundos para alguns grafos.
Grafos
E.coli [2]
CSphd [3]
Levedura [2]
Roget [3]
Epa [3]
California [3]
Facebook [18]
ODLIS [3]
PairsFSG [3]
Airport [18]
Foldoc [3]
(n,m)
(418, 519)
(1882, 1740)
(688, 1079)
(1022, 5074)
(4271, 8965)
(6175, 16150)
(1899, 20296)
(2900, 18241)
(5018, 63608)
(1574, 28236)
(12905, 109092)
FANMOD
0, 221 ± 0, 002
0, 105 ± 0, 001
0, 576 ± 0, 002
0, 949 ± 0, 001
26, 719 ± 0, 037
37, 365 ± 0, 053
151, 935 ± 0, 108
640, 538 ± 3, 611
324, 703 ± 0, 506
592, 960 ± 0, 057
1219, 255 ± 8, 125
Kavosh
0, 131 ± 0, 001
0, 062 ± 0, 001
0, 290 ± 0, 001
0, 546 ± 0, 002
14, 532 ± 0, 111
20, 064 ± 0, 050
61, 342 ± 0, 172
218, 071 ± 0, 473
193, 873 ± 0, 842
171, 115 ± 0, 361
276, 869 ± 1, 660
acc-Motif
0, 002 ± 0, 000
0, 006 ± 0, 000
0, 006 ± 0, 000
0, 055 ± 0, 005
0, 184 ± 0, 006
0, 698 ± 0, 021
2, 062 ± 0, 022
2, 563 ± 0, 051
7, 409 ± 0, 127
10, 095 ± 0, 084
8, 591 ± 0, 076
caso do grafo ODLIS [3]. Todos os testes para k = 4 foram feitos rodando o algoritmo 5 vezes
e com 10 grafos aleatórios. O tempo na Tabela 4.8 foi medido em segundos e está acompanhado
de seu desvio padrão. Os testes foram feitos nos mesmo moldes dos descritos na Seção 3.3.
Na Figura 4.5, temos o gráfico dos tempos descritos na Tabela 4.8. Os grafos foram agrupados por ordem de tamanho. Conforme descrito na Seção 3.3 podemos representar o ganho
computacional como sendo o número de vezes que um algoritmo foi mais rápido do que outro.
Seja Ta , Tk e Tf o tempo de Enumeração respectivamente do acc-Motif, Kavosh, e FANMOD.
4.3. Resultados
64
(a) Grafos pequenos.
(b) Grafos médios.
(c) Grafos grandes.
Figura 4.5: Gráfico contendo o tempo de Enumeração em segundos para k = 4 nos grafos
descritos na Tabela 4.8.
Na Figura 4.6 temos o gráfico do ganho computacional indicado pelos valores de Tk /Ta ,
Tf /Ta e Tf /Tk . Este gráfico é similar ao da Figura 3.12, só que neste temos k = 4.
Para os valores médios dos ganhos temos o seguinte resultado. Média(Tk /Ta ) = 38,
Média(Tf /Ta ) = 91 e Média(Tf /Tk ) = 2, 3. Este resultado mostra que o acc-Motif manteve seu desempenho com relação ao FANMOD tanto para k = 3 quanto para k = 4. Com
relação ao Kavosh, o acc-Motif aumentou esta proporção saindo de 32 para k = 3 e indo para
38 para k = 4. Assim podemos inferir que a extensão deste algoritmo para subgrafos maiores
pode trazer ótimos resultados.
Também foram feitos testes em grafos aleatórios conforme Algoritmo 10. Os grafos possuem 5000 vértices e as arestas variam de 10 mil a 100 mil aumentando o número de arestas
gradativamente de 10 mil. O acc-Motif foi mais rápido em todos os grafos testados conforme,
65
Figura 4.6: Gráfico contendo os valores de Tk /Ta , Tf /Ta e Tf /Tk para o conjunto de teste
indicados na Tabela 3.1.
demonstra a Figura 4.7. Este teste mostra o comportamento dos algoritmos com o aumento do
grau médio dos grafos. Os tempos registrados neste teste estão descritos na Tabela A.2.
Figura 4.7: Gráfico contendo o tempo de Enumeração em segundos para k = 4 em grafos
aleatórios.
A Figura 4.8 apresenta o percentual de tempo gasto no processo de enumeração. Os testes
foram feitos utilizando os mesmos grafos aleatórios do teste anterior, a diferença é que neste
caso o número de arestas dos grafos variam de mil até 100 mil. Este gráfico mostra o percentual
de tempo gasto no procedimento de construção dos conjuntos de vizinhos, referenciado no
gráfico por V iz e , que corresponde a execução da linha 2 do Algoritmo 20. Temos também o
66
4.3. Resultados
percentual de tempo gasto na execução da linha 3 do Algoritmo 20, representado no gráfico
por meT1 T2 . Por fim, temos a indicação da parcela de tempo gasto para computar o número
de ocorrências no Histograma. Esta etapa representa a execução da linha 5 até a linha 12 do
Algoritmo 20 e estão indicadas no gráfico por Set Histograma.
Conforme mostra o gráfico da Figura 4.8, podemos verificar que grande parte do tempo
gasto na Enumeração se deve ao Algoritmo 22. Confirmando assim a relevância de sua complexidade O(m2 ) no Algoritmo 20.
Figura 4.8: Gráfico contendo a porcentagem de tempo gasto na Enumeração para k = 4 em
grafos aleatórios.
C APÍTULO
5
Conclusão
O problema de Detecção de Network Motifs é de propósito geral e sua aplicação envolve diversas áreas do conhecimento. Sua solução envolve 4 etapas [7]:
1. Enumeração de todos os subgrafos de tamanho k.
2. Classificação do subgrafo quanto ao isomorfismo.
3. Geração de grafos aleatórios.
4. Análise estatística dos padrões para identificar os possíveis Motifs.
A primeira delas é a tarefa de maior custo computacional. Neste trabalho foram abordados
alguns métodos para fazer a enumeração. O método de Força Bruta vide Seção 2.3.1, por exemplo, apesar de resolver o problema para qualquer tamanho de subgrafo possui complexidade
Θ(nk ), que é muito elevada, tornando o método ineficiente para grafos grandes.
Também foi apresentado o Algoritmo Elementar vide Seção 2.3.2, que possui um desempenho bem interessante pelo fato de não verificar a conexidade do subgrafo gerado. Infelizmente
esta abordagem, da forma como foi concebida, não permite uma extensão automática para subgrafos maiores. Ela necessita de uma implementação para cada tamanho k. Como usualmente
o tamanho do Motif é limitado pelo custo computacional, o valor de k geralmente é inferior a 8
tornando possível o uso deste algoritmo.
67
5.1. Comparativo
68
Quanto a segunda etapa do problema que é a classificação quanto ao isomorfismo foram
apresentados algumas soluções como o Algoritmo de Força Bruta, descrito pelo Algoritmo 5,
que resolve o problema para grafos de qualquer tamanho com complexidade Θ(n2 n!). Sua
utilização se tornou um pouco obsoleta após a descoberta de propriedades nos grafos que permitem uma expressiva diminuição no espectro de busca conforme apresentado pelo Algoritmo
de Força Bruta com Refinamento Estrutural vide Seção 2.4.2.
No problema de Network Motifs o tamanho do subgrafo analisado é pequeno, tornando
viável a utilização de métodos que resolvem o problema de Isomorfismo em Grafos em tempo
polinomial. Neste trabalho foi apresentado o Algoritmo 9 que resolve o problema em tempo
polinomial para dígrafos com no máximo 5 vértices.
Quanto a geração de grafos aleatórios foram apresentados algumas abordagens que atualmente são utilizadas pelos algoritmos voltados para Detecção de Network Motifs.
Por último foi apresentado o acc-Motifs [14] que é um algoritmo que executa as tarefas de
√
enumeração e classificação quanto ao isomorfismo com complexidade O(m m) para k = 3 e
O(m2 ) para k = 4. Este algoritmo acelera o processo de enumeração por meio de otimização
combinatória e em comparação com outros algoritmos o acc-Motif se mostrou bastante rápido.
5.1 Comparativo
Para entender o motivo pelo qual o acc-Motif é mais rápido que os outros algoritmos, podemos
fazer um comparativo sobre a tarefa de maior custo computacional, que é o processo de enumeração dos subgrafos e classificação quanto ao isomorfismo. Analisando o custo computacional
para estas tarefas, podemos comparar as estratégias de cada etapa conforme Figura 5.1.
acc-Motif
FANMOD e Kavosh
• Geração de todos os subgrafos de tamanho k − 2.
• Geração de todos os subgrafos de tamanho k.
• Estrutura de dados grande para cada subgrafo.
• Estrutura de dados pequena para cada
subgrafo.
• Classificação quanto ao isomorfismo
com complexidade O(1).
• Classificação quanto √ao isomorfismo
com complexidade 2O( k log k) .
Figura 5.1: Comparação no processo de Enumeração entre o acc-Motif e o FANMOD e Kavosh.
Capítulo 5. Conclusão
69
O procedimento para gerar todos os subgrafos de determinado tamanho varia conforme o
algoritmo. Esta etapa do processo é a principal diferença entre os algoritmos. A classificação quanto ao isomorfismo é um problema à parte, cada algoritmo pode utilizar uma estratégia
diferente. O melhor método para classificação quanto ao isomorfismo possui complexidade
√
2O( k log k) [24]. Deste modo, os algoritmos que identificam os Network Motifs, não se preocupam muito com o problema de isomorfismo e sim com a geração dos subgrafos.
A grande vantagem do acc-Motif está na classificação quanto ao isomorfismo com complexidade O(1). Outra diferença está relacionada ao número de subgrafos gerados. O acc-Motif
só gera os subgrafos de tamanho k − 2, o restante da enumeração para subgrafos de tamanho k
é feita por meio de Otimização Combinatória. Para atingir este objetivo é necessário um custo
computacional na ordem de O(m) para cada subgrafo gerado.
O acc-Motif também necessita de uma grande estrutura de dados. Por exemplo, a vizinhança
de um subgrafo k − 2 é composta por 4k−2 − 1 conjuntos de vizinhos. Apesar do custo desta
estrutura, a metodologia de enumeração utilizada pelo acc-Motif é bastante promissora.
5.2 Contribuições
Este trabalho deixa como contribuição para a área de Teoria dos Grafos a análise e descrição
de algoritmos para Enumeração de subgrafos, soluções para o problema de isomorfismo, abordagens para a construção de grafos aleatórios e análise estatística para o reconhecimento de
padrões. Quanto a área de Otimização Combinatória, este trabalho deixa como contribuição
a descrição do algoritmo acc-Motif que é uma ferramenta para Detecção de Network Motifs
implementada para Motifs de tamanho 3 e 4.
5.3 Trabalhos Futuros
Os trabalhos futuros impulsionados a partir deste trabalho de graduação consistem na extensão
do Algoritmo Elementar 2.3.2 para tamanhos maiores que 4.
A função de hash descrita no Algoritmo 9 pode ser utilizada em conjunto com métodos
que façam uso de outras características dos grafos como é o caso da Teoria Espectral, podendo
assim restringir ainda mais o espaço de busca. Este método também pode ser aprimorado para
que a função de hash seja perfeita para grafos maiores do que 5 vértices.
Os trabalhos futuros com relação ao acc-Motif estariam voltados para aumentar o tamanho
dos subgrafos para k ≥ 5. A grande dificuldade no progresso deste algoritmo está relacionada
à elevada complexidade de implementação, contudo o ganho de desempenho é encorajador.
[1] Edward G. Allan, Jr., William H. Turkett, Jr., and Errin W. Fulp. Using network motifs
to identify application protocols. In Proceedings of the 28th IEEE conference on Global
telecommunications, GLOBECOM’09, pages 4266–4272. IEEE Press, 2009.
[2] Uri Alon. Molecular cell biology lab: Dataset.
http://www.weizmann.ac.il/mcb/UriAlon/groupNetworksData.html,
2012.
[3] Vladimir
Batagelj
and
Andrej
Mrvar.
Pajek
http://vlado.fmf.uni-lj.si/pub/networks/data/, 2006.
datasets.
[4] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM
J. Comput., 14(1):210–223, February 1985.
[5] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to algorithms. MIT Press and McGraw-Hill, 1990.
[6] Joshua A. Grochow and Manolis Kellis. Network motif discovery using subgraph enumeration and symmetry-breaking. In Proceedings of the 11th annual international conference on Research in computational molecular biology, RECOMB’07, pages 92–106,
Berlin, Heidelberg, 2007. Springer-Verlag.
[7] Z. Kashani, H. Ahrabian, E. Elahi, A. Nowzari-Dalini, E. Ansari, S. Asadi, S. Mohammadi, F. Schreiber, and A. Masoudi-Nejad. Kavosh: a new algorithm for finding network
motifs. BMC bioinformatics, 10(1):318, 2009.
[8] Luciana Lee. Reformulação do problema de isomorfismo de grafos como um problema
quadrático de alocação. Departamento de Informática do Centro Tecnológico da Universidade Federal do Espírito Santo, Setembro 2007.
[9] Celine Lefebvre, Wei Keat Lim, Katia Basso, Riccardo Dalla Favera, and Andrea Califano.
A context-specific network of protein-dna and protein-protein interactions reveals new
regulatory motifs in human b cells. In Proceedings of the joint 2006 satellite conference
on Systems biology and computational proteomics, RECOMB’06, pages 42–56, Berlin,
Heidelberg, 2007. Springer-Verlag.
71
72
[10] Tien-ho Lin, Robert F. Murphy, and Ziv Bar-Joseph. Discriminative motif finding for predicting protein subcellular localization. IEEE/ACM Trans. Comput. Biol. Bioinformatics,
8:441–451, March 2011.
[11] Zhang Lin, Qian Guanqun, and Zhang Li. Clustering analysis of motif significance profile in software networks. In Proceedings of the 10th WSEAS International Conference
on Mathematical Methods and Computational Techniques in Electrical Engineering, pages 145–147, Stevens Point, Wisconsin, USA, 2008. World Scientific and Engineering
Academy and Society (WSEAS).
[12] Michael Lones and Andy Tyrrell. Regulatory motif discovery using a population clustering evolutionary algorithm. IEEE/ACM Transactions on Computational Biology and
Bioinformatics, 4:403–414, 2007.
[13] Dror Marcus and Yuval Shavitt. Efficient counting of network motifs. In Proceedings of the 2010 IEEE 30th International Conference on Distributed Computing Systems
Workshops, ICDCSW ’10, pages 92–98, Washington, DC, USA, 2010. IEEE Computer
Society.
[14] Luis A.A. Meira, Vinícius R. Máximo, Álvaro L. Fazenda, and Arlindo F. da Conceição. Accelerated motif detection using combinatorial techniques. Workshop on Complex
Networks and their Applications, 2012, Sorrento. 8th International Conference on SIGNAL IMAGE TECHNOLOGY INTERNET BASED SYSTEMS - SITIS, page 744, 2012.
[15] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network
motifs: Simple building blocks of complex networks. Science, 298:824–887, 2002.
[16] R. Milo N.Kashtan, S.Itzkovitz and U.Alon. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. BIOINFORMATICS,
20:1746–1758, 2004.
[17] S. Omidi, F. Schreiber, and A. Masoudi-Nejad. Moda: An efficient algorithm for network
motif discovery in biological networks. Genes Genet. Syst, 84:385–395, 2009.
[18] Tore Opsahl. Datasets tore opsahl.
http://toreopsahl.com/datasets/#usairports, 2012.
[19] Nadia Pisanti, Maxime Crochemore, Roberto Grossi, and Marie-France Sagot. Bases of
motifs for generating repeated patterns with wild cards. IEEE/ACM Trans. Comput. Biol.
Bioinformatics, 2:40–50, January 2005.
[20] F. Schreiber and H. Schwöbbermeyer. Mavisto: a tool for the exploration of network
motifs. Bioinformatics, 21(17):3572–3574, 2005.
[21] S.Wernicke and F.Rasche. Fanmod: a tool for fast network motif detection. Bioinformatics, 22:1152–1153, 2006.
73
[22] Tie Wang, Jeffrey W. Touchman, Weiyi Zhang, Edward B. Suh, and Guoliang Xue. A
parallel algorithm for extracting transcription regulatory network motifs. In Proceedings
of the Fifth IEEE Symposium on Bioinformatics and Bioengineering, BIBE ’05, pages
193–200, Washington, DC, USA, 2005. IEEE Computer Society.
[23] wolfram. Weakly connected digraph.
http://mathworld.wolfram.com/WeaklyConnectedDigraph.html.
http://oeis.org/A003085.
[24] Elisabeth Wong, Brittany Baur, Saad Quader, and Chun-Hsi Huang. Biological network
motif detection: principles and practice. Briefings in Bioinformatics, 13(2):202–215,
2012.
[25] Kai-Hsiang Yang, Kun-Yan Chiou, Hahn-Ming Lee, and Jan-Ming Ho. Web appearance
disambiguation of personal names based on network motif. In Proceedings of the 2006
IEEE/WIC/ACM International Conference on Web Intelligence, WI ’06, pages 386–389,
Washington, DC, USA, 2006. IEEE Computer Society.
A PÊNDICE
A
Tabela de Resultados
Na Tabela A.1 temos o tempo de enumeração, em milissegundos, dos grafos aleatórios que
foram utilizados para comparar o desempenho do acc-Motif para k = 3.
Os grafos aleatórios utilizados nestes testes foram construídos conforme Algoritmo 10.
Na Tabela A.2 temos o tempo de enumeração, em segundos, dos grafos aleatórios que foram
utilizados para testar o desempenho do acc-Motif para k = 4.
75
76
Tabela A.1: Tempo de Enumeração para k = 3 em milissegundos para grafos aleatórios.
(n,m)
(5000, 5000)
(5000, 10000)
(5000, 15000)
(5000, 20000)
(5000, 25000)
(5000, 30000)
(5000, 35000)
(5000, 40000)
(5000, 45000)
(5000, 50000)
(5000, 55000)
(5000, 60000)
(5000, 65000)
(5000, 70000)
(5000, 75000)
(5000, 80000)
(5000, 85000)
(5000, 90000)
(5000, 95000)
(5000, 100000)
No subgrafos
9.940
40.107
90.103
158.903
249.247
359.327
488.035
637.250
806.300
995.801
1.202.269
1.434.311
1.680.077
1.947.312
2.233.657
2.541.885
2.862.776
3.207.754
3.575.859
3.960.874
FANMOD
16, 30 ± 0, 23
62, 22 ± 0, 22
139, 29 ± 0, 28
248, 77 ± 0, 60
396, 36 ± 0, 55
589, 25 ± 6, 61
815, 07 ± 2, 12
1089, 54 ± 3, 71
1421, 07 ± 2, 80
1796, 40 ± 6, 24
2236, 91 ± 9, 02
2777, 80 ± 8, 53
3388, 10 ± 18, 82
4083, 98 ± 25, 54
4896, 12 ± 31, 71
5772, 18 ± 71, 79
6631, 58 ± 52, 86
7730, 73 ± 36, 08
8979, 13 ± 47, 96
10513, 84 ± 191, 28
Kavosh
10, 88 ± 0, 16
40, 44 ± 0, 22
86, 45 ± 0, 41
149, 08 ± 2, 25
230, 12 ± 2, 27
328, 81 ± 3, 24
445, 40 ± 2, 68
578, 97 ± 2, 89
736, 20 ± 9, 83
904, 16 ± 5, 01
1084, 76 ± 8, 04
1294, 24 ± 4, 57
1513, 36 ± 8, 10
1755, 14 ± 13, 57
1998, 33 ± 11, 53
2270, 47 ± 5, 53
2557, 38 ± 10, 29
2856, 95 ± 5, 95
3174, 27 ± 16, 43
3504, 24 ± 9, 03
acc-Motif
3, 54 ± 0, 03
10, 15 ± 0, 97
16, 76 ± 0, 41
24, 25 ± 0, 06
32, 51 ± 0, 03
41, 78 ± 0, 05
51, 58 ± 0, 15
63, 17 ± 0, 70
75, 97 ± 0, 46
91, 86 ± 3, 71
105, 37 ± 2, 63
117, 50 ± 0, 64
133, 30 ± 0, 14
150, 41 ± 0, 08
168, 27 ± 1, 28
185, 47 ± 0, 12
197, 28 ± 0, 11
225, 43 ± 5, 27
248, 01 ± 0, 14
269, 33 ± 0, 57
Tabela A.2: Tempo de Enumeração para k = 4 em segundos para grafos aleatórios.
(n,m)
(5000, 10000)
(5000, 20000)
(5000, 30000)
(5000, 40000)
(5000, 50000)
(5000, 60000)
(5000, 70000)
(5000, 80000)
(5000, 90000)
(5000, 100000)
No subgrafos
213.740
1.679.228
5.729.246
13.511.302
26.381.480
45.610.787
72.022.684
107.374.549
151.887.217
208.345.757
FANMOD
0, 42 ± 0, 002
3, 31 ± 0, 004
11, 87 ± 0, 003
29, 64 ± 0, 100
61, 40 ± 0, 071
114, 10 ± 0, 152
191, 85 ± 0, 368
310, 50 ± 5, 771
465, 36 ± 2, 749
659, 55 ± 1, 039
Kavosh
0, 32 ± 0, 001
2, 33 ± 0, 004
7, 80 ± 0, 028
18, 30 ± 0, 025
36, 12 ± 0, 367
62, 61 ± 0, 554
96, 83 ± 0, 141
144, 46 ± 0, 695
205, 46 ± 0, 640
280, 01 ± 0, 682
acc-Motif
0, 11 ± 0, 004
0, 37 ± 0, 003
0, 91 ± 0, 009
1, 85 ± 0, 020
3, 32 ± 0, 005
5, 59 ± 0, 024
8, 86 ± 0, 028
13, 25 ± 0, 019
18, 30 ± 0, 336
25, 87 ± 0, 895

Detecção de Network Motifs

Transcrição

Documentos relacionados

Apresentação: Problema do isomorfismo em grafos

Introduç˜ao `a Teoria dos grafos

UNIVERSIDADE FEDERAL DE MINAS GERAIS DEPARTAMENTO

Geometria Professor Jefferson lista de exercícios

Maior substring em comum

22 Algoritmo de Prim

seminario - IME-USP

Análise de Redes Sociais

Em uma pizzaria, cada tulipa de chopp custa R$ 0,80 e uma pizza

Exercicios 3 - Departamento de Matemática - PUC-Rio