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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorGiménez Lugo, Gustavo Alberto-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2787038908575326-
Autor(es): dc.contributorGiménez Lugo, Gustavo Alberto-
Autor(es): dc.contributorVignatti, Andre Luís-
Autor(es): dc.contributorTacla, Cesar Augusto-
Autor(es): dc.contributorLopes, Heitor Silvério-
Autor(es): dc.creatorSilveira, Fabio Sebastian-
Data de aceite: dc.date.accessioned2022-02-21T22:26:14Z-
Data de disponibilização: dc.date.available2022-02-21T22:26:14Z-
Data de envio: dc.date.issued2017-12-08-
Data de envio: dc.date.issued2017-12-08-
Data de envio: dc.date.issued2017-08-15-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/2711-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/675084-
Descrição: dc.descriptionThis 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.-
Descrição: dc.descriptionEste 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherCuritiba-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação Aplicada-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectAgentes inteligentes (Software)-
Palavras-chave: dc.subjectInteligência artificial-
Palavras-chave: dc.subjectMétodos de simulação-
Palavras-chave: dc.subjectEngenharia de sistemas-
Palavras-chave: dc.subjectComputação-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectIntelligent agents (Computer software)-
Palavras-chave: dc.subjectArtificial intelligence-
Palavras-chave: dc.subjectSimulation methods-
Palavras-chave: dc.subjectSystems engineering-
Palavras-chave: dc.subjectComputer science-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Palavras-chave: dc.subjectCiência da Computação-
Título: dc.titleEscabilidade do problema de geração de estruturas de coalizão: aplicação de um algoritmo baseado em detecção de comunidades a grafos reais-
Título: dc.titleScalability of the problem of generation of coalition structures: application of an algorithm based on the detection of communities to real graphs-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.