Anytime Coalition Structure Generation on Scale-Free and Community Networks

We consider the coalition structure generation (CSG) problem on synergy graphs, which arises in many practical applications where communication constraints, social or trust relationships must be taken into account when forming coalitions. We propose a novel representation of this problem based on the concept of edge contraction, and an innovative branch and bound approach (CFSS), which is particularly efficient when applied to a general class of characteristic functions. We evaluate CFSS on two particular synergy graph topologies, i.e., scale-free networks and community networks, which provide an efficient description of many interesting real-world scenarios, e.g., social networks, authorships, collective energy purchasing and carpooling. Our results show that, when the graphs are very sparse, CFSS is 4 orders of magnitude faster than DyCE, the best algorithm to date for CSG on synergy graphs.