Registro fonte: Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais

Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais

This study presents experimental results on the scalability of the coalition’s structures formation for real graphs that go from 5 thousand vertices. A simple heuristic algorithm called Propagation Algorithm for Coalition Structure Formation (APFEC in Portuguese) with experimental guarantees is pres...

ver descrição completa

Autor principal:	Silveira, Fabio Sebastian
Formato:	Dissertação
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2017
Assuntos:	Teoria dos grafos Agentes inteligentes (Software) Inteligência artificial Métodos de simulação Engenharia de sistemas Computação Graph theory Intelligent agents (Computer software) Artificial intelligence Simulation methods Systems engineering Computer science CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/2711
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-2711
recordtype	dspace
spelling	riut-1-27112017-12-08T19:38:16Z Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais Scalability of the problem of generation of coalition structures: application of an algorithm based on the detection of communities to real graphs Silveira, Fabio Sebastian Giménez Lugo, Gustavo Alberto http://lattes.cnpq.br/2787038908575326 Giménez Lugo, Gustavo Alberto Vignatti, Andre Luís Tacla, Cesar Augusto Lopes, Heitor Silvério Teoria dos grafos Agentes inteligentes (Software) Inteligência artificial Métodos de simulação Engenharia de sistemas Computação Graph theory Intelligent agents (Computer software) Artificial intelligence Simulation methods Systems engineering Computer science CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação This study presents experimental results on the scalability of the coalition’s structures formation for real graphs that go from 5 thousand vertices. A simple heuristic algorithm called Propagation Algorithm for Coalition Structure Formation (APFEC in Portuguese) with experimental guarantees is presented and probed, based on a balanced label propagation version for detection of communities in very large graphs. The limits of the proposal are evaluated, comparing it with the state-of-the-art in relation to the exact algorithms (ODP-IP - The IP algorithm, based on representation of integer partitions, and ODP, optimal dynamic programming) and heuristic (CFSS - Coalition Formation for Sparse Synergies). The experiments are performed with a set of 14 real-world graphs, and the results show that this approach can calculate coalition structures quickly, even in the presence of the limitations discussed. Finally, the preliminary results are analyzed considering the influence of the ability and the interrelation between the agents in the evaluation of the coalitions. Este estudo apresenta resultados experimentais sobre a escalabilidade da formação de estruturas de coalizão para grafos reais que passam de 5 mil vértices. Um algoritmo heurístico simples denominado Algoritmo de Propagação para Formação de Estrutura de Coalizão (APFEC) com garantias experimentais é apresentado e sondado, com base em uma versão de propagação balanceada de rótulos para detecção de comunidades em grafos muito grandes. Os limites da proposta são avaliados, comparando-o com o estado-da-arte em relação aos algoritmos exatos (ODP-IP - A junção do algoritmo IP, baseado em representação de partições de inteiros, e ODP, programação dinâmica ótima) e heurístico (CFSS - Formação de coligação para grafos esparsos). Os experimentos são executados com um conjunto de 14 grafos do mundo real, e os resultados mostram que esta abordagem consegue calcular estruturas de coalizão de maneira rápida, mesmo na presença das limitações discutidas. Finalmente, os resultados preliminares são analisados considerando a influência da habilidade e a inter-relação entre os agentes na avaliação das coalizões. 2017-12-08T19:38:16Z 2017-12-08T19:38:16Z 2017-08-15 masterThesis SILVEIRA, Fabio Sebastian. Escalabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais. 2017. 68 f. Dissertação (Mestrado em Computação Aplicada) - Universidade Tecnológica Federal do Paraná, Curitiba, 2017. http://repositorio.utfpr.edu.br/jspui/handle/1/2711 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Curitiba Brasil Programa de Pós-Graduação em Computação Aplicada UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Teoria dos grafos Agentes inteligentes (Software) Inteligência artificial Métodos de simulação Engenharia de sistemas Computação Graph theory Intelligent agents (Computer software) Artificial intelligence Simulation methods Systems engineering Computer science CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação
spellingShingle	Teoria dos grafos Agentes inteligentes (Software) Inteligência artificial Métodos de simulação Engenharia de sistemas Computação Graph theory Intelligent agents (Computer software) Artificial intelligence Simulation methods Systems engineering Computer science CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação Silveira, Fabio Sebastian Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais
description	This study presents experimental results on the scalability of the coalition’s structures formation for real graphs that go from 5 thousand vertices. A simple heuristic algorithm called Propagation Algorithm for Coalition Structure Formation (APFEC in Portuguese) with experimental guarantees is presented and probed, based on a balanced label propagation version for detection of communities in very large graphs. The limits of the proposal are evaluated, comparing it with the state-of-the-art in relation to the exact algorithms (ODP-IP - The IP algorithm, based on representation of integer partitions, and ODP, optimal dynamic programming) and heuristic (CFSS - Coalition Formation for Sparse Synergies). The experiments are performed with a set of 14 real-world graphs, and the results show that this approach can calculate coalition structures quickly, even in the presence of the limitations discussed. Finally, the preliminary results are analyzed considering the influence of the ability and the interrelation between the agents in the evaluation of the coalitions.
format	Dissertação
author	Silveira, Fabio Sebastian
author_sort	Silveira, Fabio Sebastian
title	Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais
title_short	Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais
title_full	Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais
title_fullStr	Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais
title_full_unstemmed	Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais
title_sort	escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2017
citation	SILVEIRA, Fabio Sebastian. Escalabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais. 2017. 68 f. Dissertação (Mestrado em Computação Aplicada) - Universidade Tecnológica Federal do Paraná, Curitiba, 2017.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/2711
_version_	1805452782746992640
score	10,814766

Escabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais

Registros relacionados