Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
A COP Model For Graph-Constrained Coalition Formation
Authors: Filippo Bistaffa, Alessandro Farinelli
JAIR 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Results show that our approach outperforms state of the art algorithms (i.e., Dy CE and IDPG) by at least one order of magnitude on realistic graphs, i.e., a crawl of the Twitter social graph, both in terms of runtime and memory. We evaluate COP-GCCF both on realistic and synthetic graphs. |
| Researcher Affiliation | Academia | Filippo Bistaffa EMAIL IIIA-CSIC, Campus UAB, 08913, Cerdanyola, Catalonia, Spain Alessandro Farinelli EMAIL Computer Science Department, University of Verona, Strada le Grazie 15, 37134, Verona, Italy |
| Pseudocode | Yes | Algorithm 1 Compute Req(S, ai, PT(G)) ... Algorithm 2 Rec Req(S, aj, PT(G)) |
| Open Source Code | No | To the best of our knowledge, the only COP solution approach that internally represents constraints as incomplete tables is CUBE, i.e., the GPU version of BE by Bistaffa et al. (2016). ... For Dy CE and IDPG, we used the implementations provided by the respective authors. |
| Open Datasets | Yes | We generate random GCCF instances considering three different network topologies, i.e., scale-free networks obtained with the Albert and Barab asi (2002) model with the m parameter equal to 1 and 2, and subgraphs of a large crawl of the Twitter social graph (Kwak et al., 2010). |
| Dataset Splits | No | We vary n within [20, 30],7 generating 20 random instances for each of the above network topologies and solving each of them with the three considered algorithms. |
| Hardware Specification | Yes | All our experiments are run on a machine with a 3.40GHz CPU, 16GB of memory and a Ge Force GTX 680 GPU. |
| Software Dependencies | No | The building phase of COP-GCCF is sequential and has been implemented in C++, while CUBE has been implemented in CUDA. |
| Experiment Setup | Yes | We generate random GCCF instances considering three different network topologies, i.e., scale-free networks obtained with the Albert and Barab asi (2002) model with the m parameter equal to 1 and 2, and subgraphs of a large crawl of the Twitter social graph (Kwak et al., 2010). G is obtained by means of a breadth-first traversal starting from a random node of the whole graph, adding each node and the corresponding arcs to G, until the desired number of nodes is reached (Russell, 2013). The number of edges is m n m (m+1) 2 and 1.6 n for scale-free networks and Twitter subgraphs respectively. Each feasible coalition has an uniformly distributed random value within [ 10, 10], while, for IDPG, unfeasible coalitions have a value of . We vary n within [20, 30],7 generating 20 random instances for each of the above network topologies and solving each of them with the three considered algorithms. |