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.

Anytime Coalition Structure Generation on Scale-Free and Community Networks

Bistaffa, Filippo;FARINELLI, Alessandro;
2014-01-01

Abstract

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.
2014
Coalition formation; Community networks; Scale-free networks; Collective energy purchasing
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/724362
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact