Modification-Fair Cluster Editing
  The classic Cluster Editing problem (also known as Correlation Clustering)
asks to transform a given graph into a disjoint union of cliques (clusters) by
a small number of edge modifications. When applied to vertex-colored graphs
(the colors representing subgroups), standard algorithms for the NP-hard
Cluster Editing problem may yield solutions that are biased towards subgroups
of data (e.g., demographic groups), measured in the number of modifications
incident to the members of the subgroups. We propose a modification fairness
constraint which ensures that the number of edits incident to each subgroup is
proportional to its size. To start with, we study Modification-Fair Cluster
Editing for graphs with two vertex colors. We show that the problem is NP-hard
even if one may only insert edges within a subgroup; note that in the classic
"non-fair" setting, this case is trivially polynomial-time solvable. However,
in the more general editing form, the modification-fair variant remains
fixed-parameter tractable with respect to the number of edge edits. 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, that is, the cost of optimal
modification-fair differs from the cost of optimal "non-fair" solutions only by
a small percentage.
