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 vertexcolored 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 CLUS- TER 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.

Authors

• Vincent Froese
• Leon Kellerhals TU Berlin
• Rolf Niedermeier Technische Universität Berlin

Keywords

No keywords are indexed for this paper.