Repositório Institucional da Universidade Tecnológica Federal do Paraná (RIUT): 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
Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/2711
Título: 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
Título(s) alternativo(s): Scalability of the problem of generation of coalition structures: application of an algorithm based on the detection of communities to real graphs
Autor(es): Silveira, Fabio Sebastian
Orientador(es): Giménez Lugo, Gustavo Alberto
Citação: 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.
Resumo: 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.
Abstract: 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.