Coalition Generation Scalability through Community Detection: Results on Real Graphs

Citations Over Time

Abstract

This article presents experimental results on the scalability of coalition formation for real graphs approaching up to 5000 vertices. A simple heuristic algorithm named Propagation Algorithm for Coalition Structure Formation with no warranties is presented and probed, based on a version of label propagation for community detection in very large graphs [1]. The limits of the proposal are gauged, comparing it with the state-ofthe-art regarding exact (ODP-IP [2]) and heuristic (CFSS [3]) algorithms. Experiments were run over a set of 14 real world, power law graphs, and the results show a more than satisfactory performance, even in the presence of limitations that are discussed. Finally, preliminary results are explored considering the influence of the skill and the inter-relationship between agents in the evaluation of the coalitions.

Related Papers

• → Peer-to-Peer Models for Resource Discovery in Large-Scale Grids: A Scalable Architecture(2007)23 cited
• → Scalable Multi-purpose Network Representation for Large Scale Distributed System Simulation(2012)21 cited
• → Coalition Generation Scalability through Community Detection: Results on Real Graphs(2017)1 cited
• → A Discussion on the Scalability of Heuristic Approximators (Extended Abstract)(2022)