Repositório Digital

A- A A+

Memetic networks : problem-solving with social network models

.

Memetic networks : problem-solving with social network models

Mostrar registro completo

Estatísticas

Título Memetic networks : problem-solving with social network models
Outro título Redes Meméticas: solução de problemas utilizando modelos de redes sociais
Autor Araújo, Ricardo Matsumura de
Orientador Lamb, Luis da Cunha
Data 2010
Nível Doutorado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Inteligência artificial
Redes sociais
[en] Artificial intelligence
[en] Memetic network
[en] Optimization
[en] Search
[en] Social computing
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 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.
Abstract Social systems are increasingly relevant to computer science in general and artificial intelligence in particular. Such interest was first sparkled by agent-based systems where the social interaction of such agents can be relevant to the outcome produced. A more recent trend comes from the general area of Social Information Processing, Social Computing and other crowdsourced systems, which are characterized by computing systems composed of people and strong social interactions between them. The set of all social interactions and actors compose a social network, which may have strong influence on how effective the system can be. In this thesis, we explore the role of network structure in social systems aiming at solving problems, focusing on numerical and combinatorial optimization. We frame problem solving as a search for valid solutions in a state space and propose a model - the Memetic Network - that is able to perform search by using the exchange of information, named memes, between actors interacting in a social network. Such model is applied to a variety of scenarios and we show that the presence of a social network greatly improves the system capacity to find good solutions. In addition, we relate specific properties of many well-known networks to the behavior displayed by the proposed algorithms, resulting in a set of general rules that may improve the performance of such social systems. Finally, we show that the proposed algorithms can be competitive with traditional heuristic search algorithms in a number of scenarios.
Tipo Tese
URI http://hdl.handle.net/10183/25515
Arquivos Descrição Formato
000753513.pdf (2.400Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.