Modification-Fair Cluster Editing
Authors: Vincent Froese, Leon Kellerhals, Rolf Niedermeier6631-6638
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform both a theoretical (algorithms and complexity) as well as an empirical study. ... We complement these and further theoretical results with an empirical analysis of our model on real-world social networks where we find that the price of modification-fairness is surprisingly low... Experiments In the spirit of B ocker, Briesemeister, and Klau (2011) who studied classic CLUSTER EDITING, we refrain from using our FPT algorithm (Theorem 5 is rather a classification result) but instead rely on mathematical programming to investigate our model of modification fairness. We evaluate our model on the SNAP Facebook data set (Leskovec and Krevl 2014) which lists for each person (vertex) their gender (color). |
| Researcher Affiliation | Academia | Vincent Froese, Leon Kellerhals, Rolf Niedermeier Technische Universit at Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany. |
| Pseudocode | No | The paper describes algorithms conceptually (e.g., 'P3-branching algorithm') and outlines steps for proofs, but it does not include any formalized pseudocode or algorithm blocks. |
| Open Source Code | Yes | All material to reproduce the results is publicly available.1 (footnote 1: https://git.tu-berlin.de/akt-public/mod-fair-ce) |
| Open Datasets | Yes | We evaluate our model on the SNAP Facebook data set (Leskovec and Krevl 2014) which lists for each person (vertex) their gender (color). |
| Dataset Splits | No | The paper mentions 'sampled four subgraphs of different sizes' and grouping them into 'sets', but it does not specify explicit training, validation, or test dataset splits, percentages, or sample counts. |
| Hardware Specification | Yes | The experiments were run on machines with an Intel Xeon W-2125 4-core 8-thread CPU clocked at 4.0 GHz and 256GB of RAM, running Ubuntu 18.04. |
| Software Dependencies | Yes | We computed optimal solutions for MODIFICATION-FAIR CLUSTER EDITING using an integer linear programming (ILP) formulation of our problem fed into the commercial solver Gurobi 8.1.1. |
| Experiment Setup | Yes | We computed optimal solutions for MODIFICATION-FAIR CLUSTER EDITING using an integer linear programming (ILP) formulation of our problem fed into the commercial solver Gurobi 8.1.1. ... We made runs for δnorm {0, 0.01, 0.02, . . . , 0.05}. We set a time limit of 100 times the time required for running standard CLUSTER EDITING on the same instance and return the best feasible solution found up to this point. |