Detecção de Network Motifs
Transcrição
Detecção de Network Motifs
Detecção de Network Motifs Vinícius Rosa Máximo Detecção de Network Motifs 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 Detecção de Network Motifs 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 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. Capítulo 1. Introdução 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, Capítulo 1. Introdução 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). Capítulo 2. Network Motifs 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 Adiciona o subgrafo ao Histograma. 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. Capítulo 2. Network Motifs 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 Adiciona o subgrafo ao Histograma. 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 Adiciona o subgrafo ao Histograma. 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 Adiciona o subgrafo ao Histograma. 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 Adiciona o subgrafo ao Histograma. 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 Adiciona o subgrafo ao Histograma. 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. 2.4. Classificação quanto ao isomorfismo 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. Capítulo 2. Network Motifs 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. 2.4. Classificação quanto ao isomorfismo 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. Capítulo 2. Network Motifs 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 ). 2.4. Classificação quanto ao isomorfismo 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. Capítulo 2. Network Motifs 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. 2.4. Classificação quanto ao isomorfismo 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. Capítulo 2. Network Motifs 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 2.4. Classificação quanto ao isomorfismo 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 Capítulo 2. Network Motifs 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 Entrada: Uma matriz[k][k] booleana. 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 2.4. Classificação quanto ao isomorfismo 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 Capítulo 2. Network Motifs 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 2.4. Classificação quanto ao isomorfismo 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 Entrada: Uma matriz[k][k] booleana. 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. Capítulo 2. Network Motifs 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. Capítulo 2. Network Motifs 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. Capítulo 2. Network Motifs Figura 2.10: Número de padrões no grafo original com relação à média. 33 C APÍTULO 3 Algoritmo acc-Motif para k=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). 3.1. Grafos não direcionados 38 1 2 3 4 Entrada: Um grafo G(V, E). 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 Entrada: Um grafo G(V, E). Saída: O valor de mv para ∀ v ∈ V mv inicializa em 0. para cada aresta (x, y) ∈ E faça mv ++ para ∀ v ∈ δ(x) ∩ δ(y). fim Algoritmo 13: Procedimento para cálculo do valor de mv . Capítulo 3. Algoritmo acc-Motif para k=3 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 Capítulo 3. Algoritmo acc-Motif para k=3 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 3.2. Grafos direcionados 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. Capítulo 3. Algoritmo acc-Motif para k=3 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 Entrada: Um grafo G(V, E). Saída: O Histograma Preenchido. Inicializa o Histograma com valor 0. Calcula {nvA , nvB , nvC } para todo v ∈ V . ∗v Calcula {mvAA , . . . , mvCC } e {m∗v AA , . . . , mCC } para todo v ∈ V . Inicializa o Histograma com valor 0. 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 3.2. Grafos direcionados 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 Entrada: Um grafo G(V, E). 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 . Entrada: Um grafo G(V, E). ∗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 Capítulo 3. Algoritmo acc-Motif para k=3 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. Capítulo 3. Algoritmo acc-Motif para k=3 (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 Capítulo 3. Algoritmo acc-Motif para k=3 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 Algoritmo acc-Motif para k=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 4.1. Grafos não direcionados 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. Capítulo 4. Algoritmo acc-Motif para k=4 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: 4.1. Grafos não direcionados 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. Capítulo 4. Algoritmo acc-Motif para k=4 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 4.1. Grafos não direcionados 56 1 2 3 4 5 6 7 8 9 Entrada: Um grafo G(V, E). Saída: O Histograma Preenchido. Inicializa o Histograma com valor 0. 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 Entrada: Um grafo G(V, E). 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 ). Capítulo 4. Algoritmo acc-Motif para k=4 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. 4.2. Grafos direcionados 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. Capítulo 4. Algoritmo acc-Motif para k=4 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 4.2. Grafos direcionados 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 . Capítulo 4. Algoritmo acc-Motif para k=4 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 Entrada: Um grafo G(V, E). Saída: O Histograma Preenchido. Inicializa o Histograma com valor 0. 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 Entrada: Um grafo G(V, E). 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 Capítulo 4. Algoritmo acc-Motif para k=4 63 Entrada: Um grafo G(V, E). 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 para cada aresta (x, y) ∈ E faça 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, Capítulo 4. Algoritmo acc-Motif para k=4 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. Referências Bibliográficas [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 Referências Bibliográficas [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. Referências Bibliográficas 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