docApresentação - RECOD — Reasoning for Complex Data
download 
Denúncia Transcrição
Apresentação - RECOD — Reasoning for Complex Data
Classificação Semi-Supervisionada em Grafos Candidato: Felipe Andrade Holanda Orientador: Jacques Wainer Instituto de Computação - Unicamp 21/09/2011 Agenda 1 Detecção de Comunidades Definição Exemplos Estado da Arte 2 Classificação Definição Exemplos Estado da Arte 3 Comparação 4 Objetivo 5 Cronograma 6 Agradecimentos 7 Referências Detecção de Comunidades Definição Definição Definição intuitiva Determinar os grupos de vértices que tem mais conexões entre si do que com o resto do grafo. 3 Detecção de Comunidades Definição Detecção de Comunidades Figura: Grafo simples com três comunidades 4 Detecção de Comunidades Exemplos Rede de interações de proteı́nas Numa rede de interações de proteı́nas, acredita-se que as comunidades representam grupos funcionais (grupo de proteı́nas envolvidas num mesmo processo. Entrada: um grafo de interações de proteı́nas Saı́da: os agrupamentos de proteı́nas, que geralmente correspondem aos grupos funcionais. 5 Detecção de Comunidades Exemplos Rede de interações de proteı́nas Figura: Grafo das interações entre as proteı́nas do fungo S. cerevisiae (Palla et al., 2005) 6 Detecção de Comunidades Exemplos Rede de colaboração cientı́fica Numa rede de colaboração cientı́fica, construı́da a partir de citações, artigos tendem a citar outros semelhantes Entrada: um grafo colaboração Saı́da: Os agrupamentos dos artigos, que geralmente correspondem a áreas ou subáreas. 8 Detecção de Comunidades Exemplos Rede de colaboração cientı́fica Figura: Mapa da ciência baseado em citações. Contruı́do a partir da análise de 6.128 revistas cientı́ficos conectados por 6.434.916 de citações (Rosvall and Bergstrom, 2008) 9 Detecção de Comunidades Estado da Arte Estado da Arte OSLOM (Lancichinetti et al., 2011) Baseado na significância estatı́stica das comunidades em relação a um grafo aleatório Caracterı́sticas Grafos orientados Arestas com pesos Comunidades sobrepostas Comunidades hierárquicas 11 Detecção de Comunidades Estado da Arte Estado da Arte Figura: OSLOM 12 Classificação Definição Classificação semi-supervisionada Definição É possı́vel inferir os atributos de um vértice em uma rede baseado nos atributos dos outros vértices da rede? Entrada: um grafo com alguns vértices previamente classificados Saı́da: a classe dos outros vértices Objetivo: inferir atributos Permite classificar a mesma rede usando diferentes critérios 13 Classificação Exemplos Redes sociais Figura: Grafo das interações sociais entre os alunos da Zachary’s karate club 14 Classificação Exemplos Redes sociais Figura: Vértices previamente classificados 15 Classificação Exemplos Redes sociais Figura: Classificação dos demais vértices 16 Classificação Exemplos Redes sociais Figura: Grafo de amigos do Facebook mostrando a classe Unicamp 17 Classificação Exemplos Redes sociais Figura: Grafo de amigos do Facebook classificados por cidade 18 Classificação Estado da Arte Estado da Arte Mislove et al. Analisou 3 redes: Estudantes da graduação da Universidade de Rice Estudantes de pós-graduação da Universidade de Rice Moradores de New Orleans Cada rede foi agrupada segundo diferentes critérios. Escola anteriormente frequentada Ano de ingresso na Universidade Curso da graduação 19 Classificação Estado da Arte Afinidade Representa o grau de homofilia da rede em relação a um certo atributo a Aa = fração das arestas ligando vértices com o mesmo atributo a fração esperada se os atributos fossem aleatórios Users Rice undergrads Attribute college major year (1) Affinity 4.49 2.33 1.97 Tabela: Dados retirados de Mislove et al. (2010) 20 Classificação Estado da Arte Figura: Informação Mútua Normalizada versus fração de usuários previamente classificados da rede social dos alunos de graduação da Universidade de Rice agrupados segundo 3 critérios. 21 Comparação Deteção de comunidades Problema de agrupamento Apenas dados não catalogados Existem algoritmos bastante elaborados e eficientes como o OSLOM Detecta as comunidades mais fortes Classificação semi-supervisionada Problema de classificação Dados não catalogados Alguns dados catalogados Mislove et al. utilizou um algoritmo guloso simples 22 Objetivo Objetivo Adaptar diferentes algoritmos de detecção de comunidades para solucionar o problema da classificação Desenvolver novos algoritmos de classificação que usem as informações das comunidades 23 Cronograma Cronograma 1 2 3 4 5 6 7 8 9 Leitura de Artigos Cursar Disciplinas Preparação para o EQM EQM Coleta de dados de redes sociais Desenvolvimento dos Algoritmos Validação dos Resultados Escrita da Dissertação Defesa 24 Agradecimentos Agradecimentos Agradeço ao RECOD, ao IC, à Unicamp e ao CNPq 25 Perguntas? 26 Referências Referências Lancichinetti, A., Radicchi, F., Ramasco, J. J., and Fortunato, S. (2011). Finding statistically significant communities in networks. PLoS ONE, 6(4):e18961. Mislove, A., Viswanath, B., Gummadi, K. P., and Druschel, P. (2010). You are who you know: inferring user profiles in online social networks. In Proceedings of the third ACM international conference on Web search and data mining, WSDM ’10, pages 251–260, New York, NY, USA. ACM. Palla, G., Derényi, I., Farkas, I., and Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814–818. Rosvall, M. and Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4):1118–1123. 27
