UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO
DEFESA DE TESE DE DOUTORADO
Aluno: Ricardo Matsumura de Araújo
Orientador: Prof. Dr. Luis da Cunha Lamb
Título: Memetic Networks: Problem-Solving with Social Network Models
Área de Pesquisa: Inteligência Artificial
Data: 12/11/2009
Hora: 10:30
Local: Auditório José Mauro Volkmer de Castilho
Banca Examinadora:
Prof. Dr. Virgílio Augusto Fernandes Almeida (UFMG)
Prof. Dr. André Carlos Ponce de Leon Ferreira de Carvalho (ICMC-USP)
Prof. Dr. Rafael Heitor Bordini (UFRGS)
Presidente da Banca: Prof. Dr. Dr. Luis da Cunha Lamb
RESUMO
Sistemas sociais têm se tornado cada vez mais relevantes para a Ciência da Computação em geral e para a Inteligência Artificial em particular.
Tal interesse iniciou-se pela necessidade de analisar-se sistemas baseados em agentes onde a interação social destes agentes pode ter um impacto no resultado esperado. Uma tendência mais recente vem da área de Processamento Social de Informações, Computação Social e outros métodos emph{crowdsourced}, que são caracterizados por sistemas de computação compostos de pessoas reais, com um forte componente social na interação entre estas. O conjunto de todas interações sociais e os atores envolvidos compõem uma rede social, que pode ter uma forte influência em o quão eficaz ou eficiente o sistema pode ser. Nesta tese, exploramos o papel de estruturas de redes em sistemas sociais que visam a solução de problemas. Enquadramos a solução de problemas como uma busca por soluções válidas em um espaço de estados e propomos um modelo – a Rede Memética – que é capaz de realizar busca utilizando troca de informações (memes) entre atores interagindo em uma rede social. Tal modelo é aplicado a uma variedade de cenários e mostramos como a presença da rede social pode melhorar a capacidade do sistema em encontrar soluções.
Adicionalmente, relacionamos propriedades específicas de diversas redes bem conhecidas ao comportamento observado para os algoritmos propostos, resultando em um conjunto de regras gerais que podem melhorar o desempenho de tais sistemas sociais. Por fim, mostramos que os algoritmos propostos são competitivos com técnicas tradicionais de busca heurística em diversos cenários.
Palavras-chave: computação social, redes meméticas, inteligência artificial, busca, otimização