LOG FILE Nome: Steven Koiti Tsukamoto N.USP: 6431089 MAC0499 - Trabalho de Formatura Supervisionado Ano 2014 Titulo: "Detecção de Comunidades em Redes Complexas com informações associadas às arestas" Supervisores: Professor Marcelo Finger e Ana Paula Appel (PhD, IBM Research) Colaborador: Professor Estevam R. Hruschka Jr. (UFSCar) ----------------------------------------------------------------------------------------------------------------------------- Fevereiro Mandado emails para os professores Roberto Marcondes e Renata Wassermann para marcar uma conversa sobre possíveis orientações e temas para o trabalho de formatura supervisionado. Acontecimentos: 26/02: Reunião de apresentação da disciplina ----------------------------------------------------------------------------------------------------------------------------- Março Conversando com a pesquisadora Ana Paula Appel (IBM Research), ganhei interesse pelo sistema NELL (Never-Ending Learning Language). Estevam Hruschka (professor da UFSCar, orientador de pós-doutorado da Ana Paula Appel e um dos desenvolvedores do NELL) sugeriu alguns interessantes temas relacionados ao projeto Read the Web. Um dos pontos importantes do funcionamento do NELL é saber como dividir o grafo de modo que se possa realizar uma iteração aprendendo apenas sobre um determinado subconjunto do grafo. Isso irá permitir que as iterações não se tornem muito lentas e, além disso, possibilita que subconjuntos do grafo possam ser tratados de maneira específica pelos algoritmos do NELL. Conversando com a professora Nina Hirata (responsável pela disciplina), perguntei se era possível uma supervisão com alguém de fora do instituto. Foi recomendado ter também um supervisor de dentro do instituto. Conversando com o professor Marcelo Finger, foram estabelecidos os supervisores e tema. Definido o tema: "Detecção de Comunidades em Redes Complexas com informações associadas às arestas" E supervisores: Prof. Marcelo Finger e Ana Paula Appel (PhD, IBM Research), com a colaboração do professor Estevam R. Hruschka Jr. (UFSCar). Acontecimentos: 17/03: Conversa presencial com a professora Renata Wassermann. Mostrou indisponibilidade devido a uma grande quantidade de tarefas e alunos a orientar. Recomendou conversar com o Prof. Flávio Corrêa da Silva. 17/03: Professor Flávio também mostrou indisponibilidade pelas mesmas razões que a professora Renata. 17/03: Enviado um email para a responsável da disciplina perguntando sobre a possibilidade de um orientador externo do instituto. 21/03: Conversa presencial com o Prof. Marcelo Finger. 26/03: Enviado o email para a responsável da disciplina confirmando tema e supervisores. ----------------------------------------------------------------------------------------------------------------------------- Abril Atividades realizadas: - Execução de alguns exemplos usando a biblioteca GraphChi. - Leitura de alguns artigos relacionados ao NELL: "Toward an Architecture for Never-Ending Language Learning", Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka Jr., e Tom M. Mitchell "Autonomously Reviewing and Validating the Knowledge Base of a Never-Ending Learning System", Saulo D. S. Pedro, Ana Paula Appel, e Estevam R. Hruschka Jr. "Centaurs - a Component Based Framework to Mine Large Graphs", Ana Paula Appel, e Estevam Rafael Hruschka Junior "Prophet - a link-predictor to learn new rules on NELL", Ana Paula Appel, e Estevam Rafael Hruschka Junior - Download dos dados do NELL e entendimento de seu conteúdo (entidade, relação, ação, valor). Extração e construção do grafo. - Criação da homepage em: linux.ime.usp.br/~steven/mac0499 - Preparação e entrega da proposta de trabalho. Acontecimentos: 02/04 - Download da biblioteca GraphChi (capaz de processar grandes grafos usando memória em disco). 10/04 - Troca de emails com Lucas Navarro. Perguntas em relação às ambiguidades do sistema NELL como 'apple' (empresa ou fruta). 20/04 - Entrega do relatório sobre um estudo preliminar do tema 28/04 - Recebido de Lucas Navarro o programa que corrige alguns 'concepts' dos dados do NELL. 30/04 - criação da homepage do trabalho e entrega da proposta de trabalho. Enviado email para a responsável da disciplina e supervisores avisando sobre a disponibilidade do trabalho na homepage. Reuniões: 09/04 - Ana Paula 16/04 - Ana Paula 23/04 - Ana Paula e Estevam Primeira reunião com o Prof. Estevam 30/04 - Ana Paula ----------------------------------------------------------------------------------------------------------------------------- Maio Resumo do mês: Foco maior nos algoritmos de detecção de comunidades. Existe bastante material relacionado ao assunto. Usando a biblioteca SNAP, foram feitos alguns experimentos com o grafo do NELL. Alguns dos resultados são mostrados abaixo. -------------------------------- Biblioteca SNAP (Stanford Network Analysis Project) ** Versão em Python - dois algoritmo já implementados ** - Girvan-Newman Baseado na centralidade de betweenness. Essa medida é igual ao número de menores caminhos de todos os vértices para quaisquer outros vértices que passam por aquele nó. Problema: elevado tempo de processamento - CNM (Clauset-Newman-Moore) Para cada etapa, o algoritmo junta as 2 comunidades que possuem o maior valor positivo de contribuição para a modularidade global. Problema: memória insuficiente ** Versão em C++ - três algoritmos já implementados ** - Girvan-Newman Tempo de processamento: superior a 64 horas Problema: não finalizado o processamento devido à elevada duração - CNM (Clauset-Newman-Moore) Tempo de processamento: aproximadamente 1 hora Resultados: número de nós -> 680.553 número de arestas -> 422.200 modularidade -> 0.965323 número de comunidades -> 312.916 tamanho da maior comunidade -> 30.954 porcentagem -> 99,25% das comunidades tem tamanho 2 - Infomap Tempo de processamento: 58h51min Resultados: número de nós -> 680.553 número de arestas -> 422.200 número de comunidades -> 680.553 Problema: O algoritmo criou apenas comunidades de tamanho 1 -------------------------------- NCP (Network Community Profile) Condutância -> noção mais simples de qualidade de clusterização. Quociente entre o número de arestas dentro do cluster pelo número de arestas de saída do cluster. Conjuntos que se aproximam de ser uma comunidade possuem pequenos valores de condutância. NCP caracteriza a qualidade de uma rede de comunidades como função pelo tamanho. Para todo tamanho de comunidade k, a função f(k) mede a pontuação para o conjunto de comunidades do tamnaho determinado. De acordo com o gráfico gerado pela ferramenta NCPPLOT do SNAP, as comunidades "ideais" do NELL possuem tamanho por volta de 100 (concordando com a citação do pesquisador Yuri). -------------------------------- Biblioteca Igraph Foi estudada a possibilidade de usar outra biblioteca de grafos, implementada em Python. Possui os seguintes algoritmos para detecção de comunidades: - Edge Betweenness - Fast Greedy - Infomap - Label propagation - Leading Eigenvector - Multilevel - Optimal modularity - Spinglass - Walktrap -------------------------------- Acontecimentos: 02/05 - Recebido alguns comentários do Prof. Marcelo Finger sobre a proposta de trabalho. 08/05 - Recebido uma survey do Prof. Marcelo Finger sobre detecção de comunidades. 23/05 - Recebido dados já subdivididos do NELL (categoria esportes e mais populadas), enviados por Paulo Henrique Barchi. 26/05 - Recebido material do pesquisador Luis Gregorio Moyano (IBM Research) sobre detecção de comunidades. Artigos de Leicht e Newman, algoritmo de Louvain (grafos grandes) e trabalho de Jure Leskovec. 30/05 - Entrega do arquivo log file 1 Reuniões: 07/05 - Ana Paula e Estevam Problemas: tempo de processamento no grafo do NELL Novas ideias: testar com apenas uma parte do grafo ou usar o ncpplot do SNAP 23/05 - Ana Paula e Estevam Apresentação dos resultados para o algoritmo Girvan-Newman (C++) e gráfico do ncpplot. Dois próximos passos: - verificar sobre as comunidades geradas pelo algoritmo, principalmente a de maior tamanho - verificar como o algoritmo de detecção de comunidade se comporta com determinadas categorias do grafo do NELL (relacionados a esporte ou as mais populadas) 29/05 - Ana Paula Número de componentes conexas é aproximadamente o mesmo número de comunidades geradas. Outra abordagem: fazer uma transformação no grafo, tornando a aresta de relacionamento também um nó. Dessa forma, teremos um grafo mais conexo. Fazer uma comparação com o resultado para a maior componente conexa do grafo do NELL. ----------------------------------------------------------------------------------------------------------------------------- Junho Resumo: O algoritmo de Louvain apresentou um resultado bom e rápido na detecção de comunidades. Porém, assim como os resultados obtidos nos algoritmos do SNAP, a grande maioria das comunidades são de tamanho 2. Foi abordada uma ideia de transformação do grafo do NELL. Porém, os resultados foram bem parecidos. Novamente, a maioria das comunidades detectadas eram de tamanho 2. Fazendo alguns testes em diferentes bases de dados, foi averiguado que o algoritmo de Louvain não é tendencioso a criar apenas comunidades de tamanho 2. Usamos uma outra forma para o particionamento do grafo: a ferramenta Metis (www.cs.umn.edu/~metis). O algoritmo subdivide o grafo em subconjuntos de mesmo tamanho. Ou seja, as categorias são proporcionalmente divididas entre as partições. Porém, estamos interessados em detectar comunidades com características específicas. Aplicando o algoritmo do Metis no grafo do NELL transformado, obtemos resultados semelhantes. Ou seja, as categorias foram divididas proporcionalmente entre as partições. Subdividindo o grafo do NELL por assuntos (como música ou esporte), percebemos que foi criado um grande grupo formada pelas instâncias relacionadas à 'url'. (imagens foram guardadas) Aplicando o algoritmo do Metis nesses subgrafos, vemos que esse mesmo grande grupo é formado por diversas partições. Porém, ao aplicar o algoritmo de modularidade, pode-se ver claramente pelas imagens (geradas pelo Gephi) os diferentes grupos formados, ou seja, o grande grupo se tornou uma partição. Ao remover as instâncias de "url", o grafo sofreu uma redução bastante significativa. Pontos positivos: o grafo ficou mais "limpo", podendo ser detectadas diferentes comunidades. Pontos negativos: perda de informações. E o número de comunidades encontradas é praticamente o mesmo de componentes conexas. -------------------------------- Versão dos dados do NELL -> NELL.08m.840.esv -------------------------------- Grafo (sem aplicar transformação) Número de nós: 674.690 Número de arestas: 424.275 Número de componentes conexas: 311.477 Tamanho da maior componente: 46.065 ** Aplicando o algoritmo de Louvain na maior componente conexa ** Número de comunidades: 125 comunidades Resultados: Tamanho da comunidade: 4 -> quantidade: 16 Tamanho da comunidade: 5 -> quantidade: 5 Tamanho da comunidade: 6 -> quantidade: 8 Tamanho da comunidade: 7 -> quantidade: 4 Tamanho da comunidade: 8 -> quantidade: 2 Tamanho da comunidade: 9 -> quantidade: 2 Tamanho da comunidade: 10 -> quantidade: 2 Tamanho da comunidade: 11 -> quantidade: 5 Tamanho da comunidade: 12 -> quantidade: 5 Tamanho da comunidade: 13 -> quantidade: 4 Tamanho da comunidade: 14 -> quantidade: 1 Tamanho da comunidade: 15 -> quantidade: 2 Tamanho da comunidade: 16 -> quantidade: 1 Tamanho da comunidade: 17 -> quantidade: 2 Tamanho da comunidade: 19 -> quantidade: 1 Tamanho da comunidade: 20 -> quantidade: 1 Tamanho da comunidade: 21 -> quantidade: 3 Tamanho da comunidade: 22 -> quantidade: 1 Tamanho da comunidade: 23 -> quantidade: 1 Tamanho da comunidade: 24 -> quantidade: 1 Tamanho da comunidade: 25 -> quantidade: 1 Tamanho da comunidade: 27 -> quantidade: 1 Tamanho da comunidade: 28 -> quantidade: 2 Tamanho da comunidade: 29 -> quantidade: 1 Tamanho da comunidade: 33 -> quantidade: 4 Tamanho da comunidade: 35 -> quantidade: 1 Tamanho da comunidade: 36 -> quantidade: 1 Tamanho da comunidade: 39 -> quantidade: 2 Tamanho da comunidade: 42 -> quantidade: 2 Tamanho da comunidade: 51 -> quantidade: 1 Tamanho da comunidade: 56 -> quantidade: 1 Tamanho da comunidade: 60 -> quantidade: 2 Tamanho da comunidade: 63 -> quantidade: 1 Tamanho da comunidade: 72 -> quantidade: 1 Tamanho da comunidade: 83 -> quantidade: 1 Tamanho da comunidade: 99 -> quantidade: 1 Tamanho da comunidade: 103 -> quantidade: 1 Tamanho da comunidade: 138 -> quantidade: 1 Tamanho da comunidade: 143 -> quantidade: 1 Tamanho da comunidade: 156 -> quantidade: 1 Tamanho da comunidade: 216 -> quantidade: 1 Tamanho da comunidade: 242 -> quantidade: 1 Tamanho da comunidade: 287 -> quantidade: 1 Tamanho da comunidade: 309 -> quantidade: 1 Tamanho da comunidade: 402 -> quantidade: 1 Tamanho da comunidade: 419 -> quantidade: 1 Tamanho da comunidade: 452 -> quantidade: 1 Tamanho da comunidade: 475 -> quantidade: 1 Tamanho da comunidade: 476 -> quantidade: 1 Tamanho da comunidade: 517 -> quantidade: 1 Tamanho da comunidade: 518 -> quantidade: 1 Tamanho da comunidade: 648 -> quantidade: 1 Tamanho da comunidade: 696 -> quantidade: 1 Tamanho da comunidade: 742 -> quantidade: 1 Tamanho da comunidade: 819 -> quantidade: 1 Tamanho da comunidade: 883 -> quantidade: 1 Tamanho da comunidade: 1163 -> quantidade: 1 Tamanho da comunidade: 1227 -> quantidade: 1 Tamanho da comunidade: 1461 -> quantidade: 1 Tamanho da comunidade: 1518 -> quantidade: 1 Tamanho da comunidade: 1534 -> quantidade: 1 Tamanho da comunidade: 1722 -> quantidade: 1 Tamanho da comunidade: 1940 -> quantidade: 1 Tamanho da comunidade: 2173 -> quantidade: 1 Tamanho da comunidade: 2433 -> quantidade: 1 Tamanho da comunidade: 2684 -> quantidade: 1 Tamanho da comunidade: 2697 -> quantidade: 1 Tamanho da comunidade: 2824 -> quantidade: 1 Tamanho da comunidade: 3731 -> quantidade: 1 Tamanho da comunidade: 3870 -> quantidade: 1 Tamanho da comunidade: 4750 -> quantidade: 1 Conclusão: Aplicando o algoritmo de Louvain na maior componente conexa, obtivemos um conjunto de comunidades bastante diversificado. Porém o algoritmo foi aplicado em uma pequena componente com apenas 46.065 nós, representando apenas 6,82% do total do grafo. Notamos também que prevalece apenas uma categoria para os resultados (no caso: "url"). -------------------------------- Grafo depois da transformação A transformação consiste em transformar as arestas (que representam a relação) em nós do grafo também. Por exemplo, dadas as duas seguintes relações: (1) Messi <--playsin--> Barcelona (2) Cristiano_Ronaldo <--playsin--> Real_Madrid Teremos: Messi-------Barcelona \ / playsin / \ Cristiano_Ronaldo------Real_Madrid Resultado: Número de nós: 674.984 Número de arestas: 1.272.825 Número de componentes conexas: 3 Tamanho da maior componente: 674.725 Tempo: 101 minutos ********************************** ** Aplicando o algoritmo de Louvain ** Número de comunidades: 176.159 comunidades Modularidade: 0.412692 Tempo de processamento: 5 minutos Resultados: Tamanho da comunidade: 2 (52,19%) -> quantidade: 176.140 (99,98%) Tamanho da comunidade: 12 -> quantidade: 1 Tamanho da comunidade: 13 -> quantidade: 1 Tamanho da comunidade: 20 -> quantidade: 1 Tamanho da comunidade: 22 -> quantidade: 1 Tamanho da comunidade: 28 -> quantidade: 1 Tamanho da comunidade: 30 -> quantidade: 1 Tamanho da comunidade: 50 -> quantidade: 1 Tamanho da comunidade: 114 -> quantidade: 1 Tamanho da comunidade: 247 -> quantidade: 1 Tamanho da comunidade: 316 -> quantidade: 1 Tamanho da comunidade: 809 -> quantidade: 1 Tamanho da comunidade: 1549 -> quantidade: 1 Tamanho da comunidade: 5179 -> quantidade: 1 Tamanho da comunidade: 6030 -> quantidade: 1 Tamanho da comunidade: 6788 -> quantidade: 1 Tamanho da comunidade: 8595 -> quantidade: 1 Tamanho da comunidade: 9155 -> quantidade: 1 Tamanho da comunidade: 28750 (4,25%) -> quantidade: 1 Tamanho da comunidade: 254.997 (37,77%) -> quantidade: 1 Conclusão: Algoritmo extremamente rápido se comparado às outras alternativas. Porém, teve como resultado um elevado número de comunidades de tamanho 2, o que não é muito interessante. Apresentou também uma concentrada comunidade com 37,77% do total de nós. ********************************** Aplicando o algoritmo de Louvain na maior comunidade encontrada Número de nós: 254.997 Número de arestas: 382.494 Modularidade: 0.249997 Número de comunidades: 95.624 comunidades Resultados: Tamanho da comunidade: 2 -> quantidade: 95.623 Tamanho da comunidade: 63.751 -> quantidade: 1 Conclusão: Aplicando o algoritmo de Louvain na maior comunidade encontrada, também não resultou em uma melhoria na detecção de comunidades. Neste caso foram criadas apenas comunidades de tamanho 2 e uma outra única grande comunidade. ********************************** ** Aplicando o algoritmo CNM (Clauset-Newman-Moore) ** Número de comunidades: 176.163 Modularidade: 0.406342 Tempo de processamento: 4 horas Resultados: Tamanho da comunidade: 2 (52,19%) -> quantidade: 176.143 (99,98%) Tamanho da comunidade: 12 -> quantidade: 3 Tamanho da comunidade: 20 -> quantidade: 1 Tamanho da comunidade: 22 -> quantidade: 1 Tamanho da comunidade: 25 -> quantidade: 1 Tamanho da comunidade: 28 -> quantidade: 1 Tamanho da comunidade: 32 -> quantidade: 1 Tamanho da comunidade: 50 -> quantidade: 1 Tamanho da comunidade: 72 -> quantidade: 1 Tamanho da comunidade: 247 -> quantidade: 1 Tamanho da comunidade: 313 -> quantidade: 1 Tamanho da comunidade: 400 -> quantidade: 1 Tamanho da comunidade: 410 -> quantidade: 1 Tamanho da comunidade: 606 -> quantidade: 1 Tamanho da comunidade: 1515 -> quantidade: 1 Tamanho da comunidade: 8736 -> quantidade: 1 Tamanho da comunidade: 9110 -> quantidade: 1 Tamanho da comunidade: 46085 (6,82%) -> quantidade: 1 Tamanho da comunidade: 254.991 (37,77%) -> quantidade: 1 Conclusão: Apresentou resultados extramamente parecidos ao Louvain, ou seja, praticamente o mesmo número de comunidades de tamanho 2 e com uma grande comunidade concentrando 37,77% dos nós. Porém, o CNM tem um tempo de processamento muito mais elevado. -------------------------------- Para confirmar que o algoritmo de Louvain não esteja tendendo a criar apenas comunidades de tamanho 2, foram feitos alguns testes com outras bases de dados. Os dados foram obtidos pelo site do SNAP (http://snap.stanford.edu/). ** DBLP ** (http://snap.stanford.edu/data/com-DBLP.html) Número de nós: 317.080 Número de arestas: 1.049.866 Modularidade: 0.820289 Tempo de processamento: 9 segundos ** Amazon ** (http://snap.stanford.edu/data/com-Amazon.html) Número de nós: 334.863 Número de arestas: 925.872 Modularidade: 0.926206 Tempo de processamento: 10 segundos ** Youtube ** (http://snap.stanford.edu/data/com-Youtube.html) Número de nós: 1.134.890 Número de arestas: 2.987.624 Modularidade: 0.71029 Tempo de processamento: 56 segundos Conclusão: Em todas as bases de dados de nosso teste, foram obtidos comunidades de tamanho bem variado. Em nenhuma delas foram encontradas comunidades de tamanho 2. Ou seja, percebemos que o algoritmo de Louvain não é tendencioso a criar apenas comunidades de tamanho 2. Reforça-se o fato da detecção de comunidades de tamanho 2 no grafo do NELL seja uma característica própria. -------------------------------- Metis Metis é um pacote de programas usado para o particionamento de grafos e possui implementado algoritmos multi-níveis. Basicamente temos 3 fases: - Aglutina o grafo até apresentar um pequeno número de vértices. - Processa a bissecção do grafo. - Projeta o grafo de volta ao tamanho original e com as partições refinadas. -------------------------------- Ao remover as instâncias de "url" (e as que apenas se relacionavam com elas) obtemos o seguinte grafo do NELL: Número de nós: 63.734 Número de arestas: 116.956 Número de componentes conexas: 7839 Tamanho da maior componente: 43.899 Percebemos: Uma redução significativa de 90% do número de nós (o grafo original com 674.690 nós diminuiu para 63.734) Redução de 72% do número de arestas (de 424.275 para 116.956). O número de componentes conexas diminuiu de 311.477 para 7839. E o tamanho da maior componente continuou parecida (de 46.065 para 43.899) ** Aplicando o algoritmo de Louvain ** Número de comunidades: 7935 comunidades Modularidade: 0.830035 Tempo de processamento: 0.684 segundos Resultados: Tamanho da comunidade: 1 -> quantidade: 1 Tamanho da comunidade: 2 -> quantidade: 6354 Tamanho da comunidade: 3 -> quantidade: 869 Tamanho da comunidade: 4 -> quantidade: 234 Tamanho da comunidade: 5 -> quantidade: 112 Tamanho da comunidade: 6 -> quantidade: 84 Tamanho da comunidade: 7 -> quantidade: 40 Tamanho da comunidade: 8 -> quantidade: 35 Tamanho da comunidade: 9 -> quantidade: 24 Tamanho da comunidade: 10 -> quantidade: 25 Tamanho da comunidade: 11 -> quantidade: 23 Tamanho da comunidade: 12 -> quantidade: 22 Tamanho da comunidade: 13 -> quantidade: 9 Tamanho da comunidade: 14 -> quantidade: 8 Tamanho da comunidade: 15 -> quantidade: 4 Tamanho da comunidade: 16 -> quantidade: 3 Tamanho da comunidade: 17 -> quantidade: 4 Tamanho da comunidade: 18 -> quantidade: 1 Tamanho da comunidade: 19 -> quantidade: 7 Tamanho da comunidade: 20 -> quantidade: 5 Tamanho da comunidade: 21 -> quantidade: 1 Tamanho da comunidade: 22 -> quantidade: 2 Tamanho da comunidade: 23 -> quantidade: 3 Tamanho da comunidade: 24 -> quantidade: 2 Tamanho da comunidade: 25 -> quantidade: 3 Tamanho da comunidade: 26 -> quantidade: 1 Tamanho da comunidade: 27 -> quantidade: 2 Tamanho da comunidade: 28 -> quantidade: 1 Tamanho da comunidade: 29 -> quantidade: 1 Tamanho da comunidade: 30 -> quantidade: 2 Tamanho da comunidade: 32 -> quantidade: 1 Tamanho da comunidade: 35 -> quantidade: 2 Tamanho da comunidade: 40 -> quantidade: 2 Tamanho da comunidade: 41 -> quantidade: 4 Tamanho da comunidade: 42 -> quantidade: 1 Tamanho da comunidade: 48 -> quantidade: 1 Tamanho da comunidade: 50 -> quantidade: 1 Tamanho da comunidade: 56 -> quantidade: 1 Tamanho da comunidade: 57 -> quantidade: 1 Tamanho da comunidade: 62 -> quantidade: 2 Tamanho da comunidade: 63 -> quantidade: 1 Tamanho da comunidade: 70 -> quantidade: 1 Tamanho da comunidade: 94 -> quantidade: 1 Tamanho da comunidade: 129 -> quantidade: 2 Tamanho da comunidade: 144 -> quantidade: 1 Tamanho da comunidade: 150 -> quantidade: 1 Tamanho da comunidade: 206 -> quantidade: 1 Tamanho da comunidade: 239 -> quantidade: 1 Tamanho da comunidade: 240 -> quantidade: 1 Tamanho da comunidade: 280 -> quantidade: 1 Tamanho da comunidade: 295 -> quantidade: 1 Tamanho da comunidade: 308 -> quantidade: 1 Tamanho da comunidade: 409 -> quantidade: 1 Tamanho da comunidade: 438 -> quantidade: 1 Tamanho da comunidade: 451 -> quantidade: 1 Tamanho da comunidade: 461 -> quantidade: 1 Tamanho da comunidade: 482 -> quantidade: 1 Tamanho da comunidade: 532 -> quantidade: 1 Tamanho da comunidade: 631 -> quantidade: 1 Tamanho da comunidade: 693 -> quantidade: 1 Tamanho da comunidade: 759 -> quantidade: 1 Tamanho da comunidade: 818 -> quantidade: 1 Tamanho da comunidade: 986 -> quantidade: 1 Tamanho da comunidade: 1158 -> quantidade: 1 Tamanho da comunidade: 1287 -> quantidade: 1 Tamanho da comunidade: 1349 -> quantidade: 1 Tamanho da comunidade: 1364 -> quantidade: 1 Tamanho da comunidade: 1531 -> quantidade: 1 Tamanho da comunidade: 1882 -> quantidade: 1 Tamanho da comunidade: 2055 -> quantidade: 1 Tamanho da comunidade: 2487 -> quantidade: 1 Tamanho da comunidade: 2733 -> quantidade: 1 Tamanho da comunidade: 2845 -> quantidade: 1 Tamanho da comunidade: 3957 -> quantidade: 1 Tamanho da comunidade: 5204 -> quantidade: 1 Tamanho da comunidade: 6183 -> quantidade: 1 Conclusão: Foram detectadas comunidades de tamanho variado. O número de comunidades detectadas pelo algoritmo (total de 7935) é bastante próximo ao número de componentes conexas (7839). Houve uma grande redução no tamanho do grafo original, perdendo grande parte das informações. Mas ao diminuir o grafo, conseguimos obter melhores resultados e a possibilidade de gerar a visualização dos grafos. -------------------------------- Ao remover as instâncias de "url" do grafo transformado do NELL, obtemos o seguinte: Número de nós: 64.027 Número de arestas: 350.868 Número de componentes conexas: 7 Tamanho da maior componente: 63.660 Percebemos: O grafo obtido é bastante conexo, possui 99,42% dos nós conectados. ** Aplicando o algoritmo de Louvain ** Número de comunidades: 32 comunidades Modularidade: 0.785076 Tempo de processamento: 0.607 segundos Resultados: Tamanho da comunidade: 12 -> quantidade: 1 Tamanho da comunidade: 13 -> quantidade: 2 Tamanho da comunidade: 17 -> quantidade: 1 Tamanho da comunidade: 21 -> quantidade: 1 Tamanho da comunidade: 27 -> quantidade: 1 Tamanho da comunidade: 43 -> quantidade: 1 Tamanho da comunidade: 73 -> quantidade: 1 Tamanho da comunidade: 91 -> quantidade: 1 Tamanho da comunidade: 115 -> quantidade: 1 Tamanho da comunidade: 247 -> quantidade: 1 Tamanho da comunidade: 287 -> quantidade: 1 Tamanho da comunidade: 630 -> quantidade: 1 Tamanho da comunidade: 852 -> quantidade: 1 Tamanho da comunidade: 919 -> quantidade: 1 Tamanho da comunidade: 1188 -> quantidade: 1 Tamanho da comunidade: 1205 -> quantidade: 1 Tamanho da comunidade: 1485 -> quantidade: 1 Tamanho da comunidade: 1529 -> quantidade: 1 Tamanho da comunidade: 1582 -> quantidade: 1 Tamanho da comunidade: 1833 -> quantidade: 1 Tamanho da comunidade: 2210 -> quantidade: 1 Tamanho da comunidade: 2392 -> quantidade: 1 Tamanho da comunidade: 2430 -> quantidade: 1 Tamanho da comunidade: 2474 -> quantidade: 1 Tamanho da comunidade: 3011 -> quantidade: 1 Tamanho da comunidade: 3841 -> quantidade: 1 Tamanho da comunidade: 4543 -> quantidade: 1 Tamanho da comunidade: 4877 -> quantidade: 1 Tamanho da comunidade: 7604 -> quantidade: 1 Tamanho da comunidade: 9102 -> quantidade: 1 Tamanho da comunidade: 9361 -> quantidade: 1 Conclusão: Também foram detectadas comunidades de tamanho variado. Apresentou uma quantidade menor de comunidades detectadas (de 7935 para 32 comunidades), ou seja, conseguiu agrupar partições maiores de forma balanceada. Os resultados obtidos foram melhores em relação ao grafo original. -------------------------------- Reuniões: 06/06 - Ana Paula e Estevam Apresentado os resultados obtidos para a transformação do grafo. Mas ainda a grande maioria das comunidades detectadas são de tamanho 2. Próximos passos: - Confirmar que essa detecção de comunidades de tamanho 2 seja uma característica do grafo do NELL. - Aplicar outras alternativas para o particionamento do grafo: METIS. 11/06 - Ana Paula Apresentados os resultados obtidos do Metis, em que são criadas partições igualmente distribuídas do grafo. Ou seja, as categorias são subdivididas igualmentre entre as partições. Porém, estamos interessados em comunidades com características específicas. Próximos passos: - Separar 2 ou mais subgrafos do NELL para certas categorias (como esporte, filmes, ...) e plotar na ferramenta Gephi. - Pensar em alternativas para a modificação do algoritmo do Metis (a escolha de como ele junta os nós, condição de parada e o particionamento). 16/06 - Ana Paula e Estevam Discussão de como abordar o problema usando a ferramenta Metis. Estevam passou dois arquivos "categories.xls" e "relations.xls", em que possuem as generalizações dos 'concepts'. Próximos passos: - Aplicar o algoritmo do Metis para o grafo do NELL transformado. - Usando as generalizações, selecionar relações e categorias vinculadas a determinados assuntos (como esporte e filme). A partir desses específicos grupos plotar (no Gephi) e visualizar seu comportamento no Metis. 24/06 - Ana Paula e Estevam Apresentada as imagens obtidas (utilizando a ferramenta Gephi) ao separar o grafo do NELL pelos assuntos de "sport" e "music". Foi verificado que existe uma grande partição ligada pela relação "haswikipediaurl". Também foi apresentada as imagens do grafo depois que aplicado o algoritmo do Metis (para 4-partições). Próximos passos: - Remover os nós relacionados à 'url' e verificar os novos resultados. - Fazer um estudo aprofundado do Metis, visando modificar o código e 'relaxar' a propriedade de formar k-partições de tamanhos iguais. Como provavelmente as partições não terão o mesmo tamanho, utilizar alguma outra medida (por exemplo: o grau do nó). Talvez pensar em uma implementação utilizando diferentes bibliotecas como do SNAP ou outras em Python. ----------------------------------------------------------------------------------------------------------------------------- Julho Resumo: Foram analisados os outros 90% do grafo referentes às instâncias deixadas de lado (relacionadas à 'url'). Concluímos que esse grafo restante é muito difícil de se trabalhar pois é desconexo (ou possui arestas sem significado). Foram estabelicidos dois principais objetivos: detectar comunidade de um mesmo tipo ou de um mesmo assunto. Além de usar os algoritmos já existentes e estudados, propomos também a implementação de um novo algoritmo baseado no Metis, mas com um relaxamento na restrição de tamanhos proporcionais. Foram obtidos alguns resultados para o Objetivo 1 e foram discutidas as possibilidades de avaliação do Objetivo 2. -------------------------------- Detecção de Comunidades -> Modularidade Algoritmos: - Maximização de Modularidade Simples - Maximização de Modularidade Espectral - Arrefecimento simulado - Algoritmo Genético - Algoritmo Guloso -> Centralidade de Intermediação (Betweenness centrality) -> Clusterização Hierárquica -------------------------------- Os outros 90% Nos últimos experimentos, deixamos de lado aproximadamente 90% do grafo do NELL que eram referentes às 'urls'. Percebendo que não podemos ignorar essa grande quantidade de dados (que podem ser essenciais e importantes para o estudo), resolvemos analisar e tirar conclusões sobre os dois tipos de grafos trabalhados (com e sem relações como nós). Obtivemos os seguintes resultados: - Versão normal Quantidade de nós: 614.636 Quantidade de arestas: 307.318 Quantidade de componentes conexas: 307.318 Tamanho da maior componente conexa: 2 Quantidade de nós com o concept url: 307.318 Conclusão: Podemos ver que o número de componentes conexas é o mesmo que o número de arestas do grafo, ou seja, temos um grafo totalmente desconexo em que os nós são ligados 2 a 2. Trabalhar com este tipo de grafo é realmente bem difícil pois as instâncias não estão ligadas umas com as outras. Observando o 'concept' dessas instâncias percebemos que metade delas são do tipo 'url'. Examinando melhor os resultados, temos o seguinte formato se repetindo para todas as ligações: instância -> url_da_instância(wikipedia) Exemplos: concept:country:cameroun -> concept:url:http://en.wikipedia.org/wiki/Cameroun concept:product:macbook -> concept:url:http://en.wikipedia.org/wiki/MacBook - Versão com as relações sendo nós do grafo Quantidade de nós: 614.637 Quantidade de arestas: 921.957 Quantidade de componentes conexas: 1 Tamanho da maior componente conexa: 614.637 Quantidade de nós com o concept url: 307.318 Conclusão: Diferente do modelo anterior, temos um grafo totalmente conexo com apenas uma grande componente concentrando todos os nós. O grande número de arestas ocorre principalmente porque todas as instâncias estão ligadas à relação 'haswikipediaurl'. Ou seja, temos 307.318 arestas ligando instâncias 'url' com as instâncias de outros tipos. E temos mais 614.636 arestas ligando cada uma dessas instâncias com a relação 'haswikipediaurl'. Portanto, assim como a versão normal, este tipo de grafo também é bem difícil de se trabalhar pois as ligações não possuem muito significado. -------------------------------- Objetivos Existem dois tipos de objetivos que podemos abordar: (1) Estamos interessado que o algoritmo de detecção de comunidades encontre comunidades de um mesmo tipo, ou seja, que os grupos sejam compostos por instâncias de mesmo 'concept'. Dessa forma, poderemos identificar instâncias mal categorizadas. Por exemplo: Podemos descobrir uma comunidade com quase todas as suas instâncias como categoria 'país' e apenas uma instância como 'cidade'. Isso faz com que o sistema repense sobre a categorização dessa instância (será mesmo uma 'cidade'?). (2) Estamos interessado que o algoritmo encontre comunidades em que suas instâncias estejam relacionadas a um mesmo assunto. Diferente do objetivo anterior, não necessariamente precisam ser de um mesmo tipo, mas precisam de alguma forma estarem relacionadas a algo em comum. Com isso, poderemos descobrir subgrupos de um gênero e assim criar subcategorias que podem enriquecer ainda mais o sistema. Por exemplo: Podemos ter uma comunidade relacionada à New York, em que teremos instâncias como músicas de origem da cidade, empresas de New York, pessoas famosas, esportes praticados, ... Ou seja, a cidade de New York foi identificada como uma categoria tão complexa, que podemos criar uma subcategoria especialmente para ela. -------------------------------- Objetivo 1 Informações dos grafos Grafo normal Número de nós: 63.734 Número de arestas: 116.956 Número de comunidades: 32 Grafo com relações como nós Número de nós: 64.027 Número de arestas: 350.868 Número de comunidades: 7935 *Algoritmo de Louvain* Grafo normal: Na média, as comunidades têm 53.56% do predomínio de um tipo. Tivemos 19% das comunidades com porcentagem maior que 80%. (Ps: usamos apenas as comunidades com mais de 10 instâncias. Totalizando: 157 comunidades) Grafo com relações como nós: Na média, as comunidades têm 50.87% do predomínio de um tipo. Tivemos 21,87% das comunidades com porcentagem maior que 80%. Conclusão primária: Usando o algoritmo de Louvain, provavelmente em seu resultado teremos uma comunidade de predominância de aproximadamente 50% de um tipo e as outras instâncias com categoria de outros 'concepts'. Ou seja, não conseguimos um resultado satisfatório no sentido de dividir o grafo de acordo com o tipo. * Algoritmo Metis* Grafo normal: Na média, as comunidades têm 35.62% do predomínio de um tipo. Grafo com relações como nós: Na média, as comunidades têm 28.21% do predomínio de um tipo. Conclusão primária: Usando o algoritmo Metis, obtemos um resultado ainda menos satisfatório em relação a particionar o grafo de acordo pelo tipo. -------------------------------- Reuniões: 18/07 - Estevam Foram apresentadas as imagens do grafo sem as 'urls'. Algumas dúvidas quanto aos objetivos do trabalho foram esclarecidas e devem ser pensadas e exploradas nesta fase do projeto. Próximos passos: - Analisar os outros 90% das instâncias deixadas de lado (referentes às 'urls') - Consolidar os objetivos: - Conseguir encontrar comunidades com o mesmo 'concept'. Ou seja, ter um algoritmo que consiga juntar as instâncias do mesmo tipo. Por exemplo: reunir em um grupo todas as cidades, uma outra comunidade somente com atletas, outra só com músicas, ... A ideia seria ajudar o sistema a categorizar as instâncias ainda não catalogadas ou que foram mal categorizadas. - Encontrar comunidades relacionadas a algum assunto específico. Diferente do objetivo anterior, não estamos tão preocupados que as instâncias de uma mesma comunidade possuam 'concept' iguais, estamos interessados que elas estejam relacionadas a algum assunto em comum. Por exemplo, podemos encontrar uma comunidade com a cidade de Chicago, esportes relacionados à cidade, comidas típicas do lugar, músicas e artistas com origem em Chicago, ... A ideia é então descobrir subgrupos de algum genêro e dessa forma enriquecer e melhorar o sistema. - Rodar novamente outros algoritmos, como o Metis, e verificar os novos resultados. Pensar também em uma versão que relaxe a restrição de tamanho igual de comunidades. ----------------------------------------------------------------------------------------------------------------------------- Agosto Resumo: Com o intuito de criar uma solução semelhante ao Metis, mas flexível no tamanho das partições, foi encontrado o trabalho de mestrado do Leonardo Almeida ("Detecção de comunidades em redes complexas utilizando estratégia multinível"). Entrando em contato com o Prof. Alneu (USP - São Carlos), foram passados os emails do Leonardo Almeida e Alan (também supervisionado pelo professor Alneu e atualmente trabalhando com a mesma estratégia). Ambos concordaram em ajudar e compartilhar parte das implementações. Porém, como não foi obtido mais nenhuma resposta durante o mês de Agosto, comecei uma implementação própria do algoritmo. A ideia é finalizar o algoritmo em Setembro, para que em Outubro possa finalizar os testes e descrever os resultados. -------------------------------- Comparação entre duas iterações distintas do NELL Versão dos dados do NELL -> NELL.08m.860.esv -------------------------------- Grafo (sem url) do NELL Número de nós: 69.837 Número de arestas: 134.700 Número de componentes conexas: 8.156 Tamanho da maior componente: 48.937 ** Aplicando o algoritmo de Louvain ** Número de comunidades: 8267 comunidades Tamanho da comunidade: 2 -> quantidade: 6471 Tamanho da comunidade: 3 -> quantidade: 1005 Tamanho da comunidade: 4 -> quantidade: 286 Tamanho da comunidade: 5 -> quantidade: 123 Tamanho da comunidade: 6 -> quantidade: 94 Tamanho da comunidade: 7 -> quantidade: 44 Tamanho da comunidade: 8 -> quantidade: 37 Tamanho da comunidade: 9 -> quantidade: 18 Tamanho da comunidade: 10 -> quantidade: 31 Tamanho da comunidade: 11 -> quantidade: 24 Tamanho da comunidade: 12 -> quantidade: 10 Tamanho da comunidade: 13 -> quantidade: 9 Tamanho da comunidade: 14 -> quantidade: 17 Tamanho da comunidade: 15 -> quantidade: 14 Tamanho da comunidade: 16 -> quantidade: 3 Tamanho da comunidade: 17 -> quantidade: 6 Tamanho da comunidade: 18 -> quantidade: 2 Tamanho da comunidade: 19 -> quantidade: 3 Tamanho da comunidade: 20 -> quantidade: 3 Tamanho da comunidade: 21 -> quantidade: 5 Tamanho da comunidade: 24 -> quantidade: 2 Tamanho da comunidade: 25 -> quantidade: 4 Tamanho da comunidade: 26 -> quantidade: 1 Tamanho da comunidade: 27 -> quantidade: 4 Tamanho da comunidade: 28 -> quantidade: 1 Tamanho da comunidade: 29 -> quantidade: 2 Tamanho da comunidade: 31 -> quantidade: 1 Tamanho da comunidade: 33 -> quantidade: 1 Tamanho da comunidade: 35 -> quantidade: 1 Tamanho da comunidade: 36 -> quantidade: 1 Tamanho da comunidade: 42 -> quantidade: 2 Tamanho da comunidade: 46 -> quantidade: 1 Tamanho da comunidade: 52 -> quantidade: 1 Tamanho da comunidade: 53 -> quantidade: 1 Tamanho da comunidade: 62 -> quantidade: 1 Tamanho da comunidade: 66 -> quantidade: 1 Tamanho da comunidade: 67 -> quantidade: 2 Tamanho da comunidade: 69 -> quantidade: 1 Tamanho da comunidade: 70 -> quantidade: 1 Tamanho da comunidade: 83 -> quantidade: 1 Tamanho da comunidade: 99 -> quantidade: 1 Tamanho da comunidade: 115 -> quantidade: 1 Tamanho da comunidade: 121 -> quantidade: 1 Tamanho da comunidade: 153 -> quantidade: 1 Tamanho da comunidade: 244 -> quantidade: 1 Tamanho da comunidade: 281 -> quantidade: 1 Tamanho da comunidade: 377 -> quantidade: 1 Tamanho da comunidade: 432 -> quantidade: 1 Tamanho da comunidade: 534 -> quantidade: 1 Tamanho da comunidade: 539 -> quantidade: 1 Tamanho da comunidade: 617 -> quantidade: 1 Tamanho da comunidade: 643 -> quantidade: 1 Tamanho da comunidade: 737 -> quantidade: 1 Tamanho da comunidade: 781 -> quantidade: 1 Tamanho da comunidade: 872 -> quantidade: 2 Tamanho da comunidade: 964 -> quantidade: 1 Tamanho da comunidade: 1167 -> quantidade: 1 Tamanho da comunidade: 1183 -> quantidade: 1 Tamanho da comunidade: 1452 -> quantidade: 1 Tamanho da comunidade: 1523 -> quantidade: 1 Tamanho da comunidade: 1554 -> quantidade: 1 Tamanho da comunidade: 1762 -> quantidade: 1 Tamanho da comunidade: 1903 -> quantidade: 1 Tamanho da comunidade: 2109 -> quantidade: 1 Tamanho da comunidade: 2147 -> quantidade: 1 Tamanho da comunidade: 2976 -> quantidade: 1 Tamanho da comunidade: 3182 -> quantidade: 1 Tamanho da comunidade: 3653 -> quantidade: 1 Tamanho da comunidade: 4753 -> quantidade: 1 Tamanho da comunidade: 4844 -> quantidade: 1 Tamanho da comunidade: 5313 -> quantidade: 1 Percebemos: - Um aumento de 6103 nós (de 63.734 para 69.837) em relação à iteração NELL.08m.840 - Um aumento de 17.740 arestas (de 116.956 para 134.700) - Um aumento de 7.839 para 8.156 de componentes conexas - O tamanho da maior componente passou de 43.899 para 48.937 - O número de comunidades detectadas passou de 7935 para 8267 comunidades Conclusão: Notamos que ao trocar os dados de entrada para uma versão mais recente do NELL, não notamos grandes diferenças nos resultados obtidos pelo método de Louvain. Podemos dizer que mesmo o NELL sendo um sistema dinâmico, os resultados permanecem iguais e continuamos não tendo problemas sem os 90% do grafo referentes às 'urls'. -------------------------------- Grafo (sem url) Transformado do NELL Número de nós: 70.132 Número de arestas: 404.100 Número de componentes conexas: 6 Tamanho da maior componente: 69.765 ** Aplicando o algoritmo de Louvain ** Número de comunidades: 29 comunidades Tamanho da comunidade: 12 -> quantidade: 1 Tamanho da comunidade: 13 -> quantidade: 1 Tamanho da comunidade: 17 -> quantidade: 1 Tamanho da comunidade: 22 -> quantidade: 1 Tamanho da comunidade: 27 -> quantidade: 1 Tamanho da comunidade: 86 -> quantidade: 1 Tamanho da comunidade: 106 -> quantidade: 1 Tamanho da comunidade: 124 -> quantidade: 1 Tamanho da comunidade: 289 -> quantidade: 2 Tamanho da comunidade: 611 -> quantidade: 1 Tamanho da comunidade: 635 -> quantidade: 1 Tamanho da comunidade: 882 -> quantidade: 1 Tamanho da comunidade: 1206 -> quantidade: 1 Tamanho da comunidade: 1214 -> quantidade: 1 Tamanho da comunidade: 1504 -> quantidade: 1 Tamanho da comunidade: 1544 -> quantidade: 1 Tamanho da comunidade: 1756 -> quantidade: 1 Tamanho da comunidade: 2222 -> quantidade: 1 Tamanho da comunidade: 2618 -> quantidade: 1 Tamanho da comunidade: 2740 -> quantidade: 1 Tamanho da comunidade: 4195 -> quantidade: 1 Tamanho da comunidade: 4981 -> quantidade: 1 Tamanho da comunidade: 5039 -> quantidade: 1 Tamanho da comunidade: 5133 -> quantidade: 1 Tamanho da comunidade: 5448 -> quantidade: 1 Tamanho da comunidade: 8123 -> quantidade: 1 Tamanho da comunidade: 9350 -> quantidade: 1 Tamanho da comunidade: 9946 -> quantidade: 1 Percebemos: - Um aumento de 6105 nós (de 64.027 para 70.132) em relação à iteração NELL.08m.840 - Um aumento de 53.232 arestas (de 350.868 para 404.100) - Um decréscimo de 7 para 6 de componentes conexas - O tamanho da maior componente passou de 63.660 para 69.765 - O número de comunidades detectadas passou de 32 para 29 comunidades Conclusão: Notamos que ao trocar os dados de entrada para uma versão mais recente do NELL, não notamos grandes diferenças nos resultados obtidos pelo método de Louvain. Podemos dizer que mesmo o NELL sendo um sistema dinâmico, os resultados permanecem iguais no grafo transformado e continuamos não tendo problemas sem os 90% do grafo referentes às 'urls'. -------------------------------- Algoritmo Multinível de Otimização de Modularidade Pseudocódigo Entrada: G(0) - Grafo original a ser particionado Saída: P(0) - vetor P representando o particionamento de G(0) 1 : i <- 0 2 : repita 3 : G(i+1) <- Coarse(G(i)) 4 : i <- i + 1 5 : até critério de encerramento coarsening 6 : P(i) <- AlgoritmoModularidade (G(i)) 7 : repita 8 : (G(i-1), P(i-1)) <- Uncoarse (G(i), P(i)) 9 : Refine (P(i-1)) 10 : i <- i - 1 11 : até G(i) = G(0) 12 : retorne P(0) -------------------------------- Procedimento da Fase de Coarsening Pseudocódigo Entrada: G(i) - Grafo a ser reduzido Saída: G(i+1) - Grafo reduzido 1 : M(i) <- Matching G(i) 2 : para cada aresta (u,v) ∈ M(i) 3 : SuperVértice <- Contrair (u,v) 4 : para todos vértices x adjacentes a u e v, faça: 5 : pesoAresta (SuperVértice, x) <- pesoAresta (u,x) + pesoAresta (v,x) 6 : fim para 7 : fim para 8 : retorne G(i+1) -------------------------------- Particionamento Uma das vantagens da estratégia multinível é permitir que algoritmos mais custosos possam ser utilizados nessa fase, sem que seja gerado impacto significativo no desempenho geral. -------------------------------- Procedimento da Fase de Uncoarsening Processo reverso ao efetuado na fase de coarsening. Os grafos reduzidos são agora expandidos até que se obtenha novamente o grafo original. Pseudocódigo (Algoritmo de Refinamento por Otimização de Modularidade) Entrada: P(i) - Particionamento de Entrada Saída: P(i) - Particionamento Refinado 1 : ganhos <- ComputeGanhos(G,P(i)) 2 : repita 3 : (v,p) <- maiorGanho (ganhos) 4 : move (v,p,P(i)) 5 : atualizeGanhos (ganhos, v) 6 : até Critério de Parada Refinemnto 7 : retorne -------------------------------- Acontecimentos: 07/08 - Enviado um email ao Prof. Alneu perguntando sobre algum repositório das implementações do trabalho do Leonardo. O professor passou os contatos do Leonardo e Alan (atualmente trabalhando com a mesma estratégia). Reuniões: 06/08 - Estevam Comentou-se sobre o trabalho de mestrado do aluno Leonardo Jesus Almeida (orientador: Prof. Dr. Alneu de Andrade Lopes). Segue a ideia de detecção de comunidades utilizando estratégia multinível, que é parecida com nossa abordagem de relaxar a restrição do Metis de dividir em subgrupos de mesmo tamanho. Discutiu-se a possibilidade de usar isoladamente as iterações disponibilizadas no site do NELL. Dessa forma não teríamos o problema de trabalhar com um grafo grande em que a grande maioria dos nós são 'urls'. Uma ideia interessante discutida em relação ao objetivo 1, seria particionar os grupos e mostrar quais das instâncias tem maior probabilidade de estarem erradas. Possivelmente aquelas que se localizam nas periferias. Próximos passos: - Enviar um email ao Leonardo, verificando a possibilidade do compartilhamento do executável. - Escrita de uma documentação mais formal. (pensar na estrutura da monografia) Montar um cronograma com o que ainda precisa ser feito, visando as datas de entregas. - Pegar uma nova versão dos dados do NELL e verificar se os mesmos resultados se repetem. (outro snapshot) Dessa forma poderemos averiguar se mesmo o NELL sendo um sistema dinâmico, se haverá problemas continuar trabalhando sem os 90% do grafo referentes às 'urls'. - Pensar mais sobre o Objetivo2. Uma ideia seria rodar novamente um outro algoritmo dentro da comunidade que detectamos ao querer encontrar grupos da mesma categoria. Dessa forma poderíamos encontrar subcategorias. E também teríamos os dois Objetivos associados um com o outro. ----------------------------------------------------------------------------------------------------------------------------- Setembro Redação Montada a estrutura da monografia usando Latex. Começada a escrita da monografia, com a redação do "Resumo" e a seção de "Introdução". -------------------------------- Implementação Implementação do algoritmo multinível de otimização de modularidade simplificado. Linguagem: Python Framework: Igraph Tivemos alguns problemas de implementação em uma das fases do algoritmo, pois ao usar as funções da biblioteca, ficamos restritos à certas funcionalidades. A atribuição dos "ID's" dos vértices e arestas são feitas de forma automática e contínua, ou seja, caso um dos nós seja removido, existe a chance de que os outros sejam renumerados. Essa estratégia é interessante para grafos estáticos, porém em certos pontos do algoritmo temos que juntar vértices para formar um novo "Super Vértice", o que torna o grafo bastante dinâmico. Com essas restrições da biblioteca Igraph, começamos a implementação em outra alternativa. No caso, foi escolhido o framework SNAP. -------------------------------- Reuniões: 05/09 - Estevam Reunião rápida. O Prof. Estevam falou que voltou de viagem. Tarefa: Mandar um email falando sobre as próximas atividades e datas de entrega. 11/09 - Ana Paula e Estevam Explicado o cronograma e os planos para o projeto do TCC. No momento focar na escrita da monografia e terminar a implementação do algoritmo multinível. Será feito uma simplicação do algoritmo em que a terceira fase (uncoarsening) não será mais necessária. Tarefas: - Começar a redação da monografia visando a data de entrega do dia 01/10 - Terminar a implementação do algoritmo multinível. 25/09 - Ana Paula e Estevam Foco na redação da monografia. Portanto, foi decido em adiar a reunião. ----------------------------------------------------------------------------------------------------------------------------- Outubro Finalizada a implementação do Algoritmo Multinível de Otimização de Modularidade Simplificado (AMOMS). Foram desenvolvidos 4 heurísticas para a fase de "coarsening": (1) Random Matching (RM) Todos os vértices são rotulados como não-marcados. O algoritmo visita aleatoriamente os nós até que todos tenham sido marcados ou que o critério de redução tenha sido satisfeito. Ao visitar um nó ele verifica se existe algum vizinho não-marcado para fazer o matching. Caso encontre, o par é definido como marcado e entra na lista de matching. Caso contrário, apenas o nó visitado é marcado. (2) Heavy-Edge Matching (HEM) Parecido com a estratégia RM. Porém, procura pela aresta de maior valor (peso) dentre as que ainda não foram marcadas. (3) Modified Heavy-Edge Matching (MHEM) Visa gerar um grafo reduzido ainda menor. Escolhe o vizinho mais similar e que possua mais vértices adjacentes em comum. (4) Light-Edge Matching (LEM) Critério oposto ao HEM. Procura a aresta que possua o menor peso. Terminada essa fase da implementação foram gerados alguns grafos reduzidos. Variamos em 6 diferentes tamanhos: 20%, 30%, 40%, 50%, 60% e 70%. Ou seja, no total tivemos 6 (tamanhos) x 4 (número de heurísticas) = 24 grafos reduzidos. -------------------------------- Acontecimentos: 01/10 - Entrega da versão "as it is" da monografia. 03/10 - Ana Paula enviou algumas sugestões e correções da monografia. (Introdução) 20/10 - Entrega da versão parcial da monografia. Reuniões: 02/10 - Ana Paula Discussão sobre o algoritmo multinível em desenvolvimento. Enviado a monografia parcial com a Introdução. Tarefas: Finalizar a implementação e continuar a redação da monografia. -----------------------------------------------------------------------------------------------------------------------------