{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T23:21:07Z","timestamp":1767828067897,"version":"3.49.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T00:00:00Z","timestamp":1716595200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T00:00:00Z","timestamp":1716595200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The classic <jats:sc>Cluster Editing<\/jats:sc> problem (also known as <jats:sc>Correlation Clustering<\/jats:sc>) 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 <jats:sc>Cluster Editing<\/jats:sc> 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 <jats:sc>Modification-Fair Cluster Editing<\/jats:sc> for graphs with two vertex colors. We show that the problem is NP-hard even if one may only <jats:italic>insert<\/jats:italic> edges <jats:italic>within<\/jats:italic> a subgroup; note that in the classic \u201cnon-fair\u201d setting, this case is trivially polynomial-time solvable. However, in the more general <jats:italic>editing<\/jats:italic> 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 solutions differs from the cost of optimal \u201cnon-fair\u201d solutions only by a small percentage.<\/jats:p>","DOI":"10.1007\/s13278-024-01259-0","type":"journal-article","created":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T06:02:04Z","timestamp":1716616924000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Modification-fair cluster editing"],"prefix":"10.1007","volume":"14","author":[{"given":"Vincent","family":"Froese","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leon","family":"Kellerhals","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,25]]},"reference":[{"key":"1259_CR1","doi-asserted-by":"publisher","unstructured":"Abbasi M, Bhaskara A, Venkatasubramanian S ( 2021) Fair clustering via equitable group representations. In: proceedings of the ACM conference on fairness, accountability, and transparency (FAccT\u00a0\u201921), pp. 504\u2013 514. ACM, Virtual Event . https:\/\/doi.org\/10.1145\/3442188.3445913","DOI":"10.1145\/3442188.3445913"},{"key":"1259_CR2","unstructured":"Ahmadian S, Epasto A, Knittel M, Kumar R, Mahdian M, Moseley B, Pham P, Vassilvitskii S, Wang Y ( 2020) Fair hierarchical clustering. In: proceedings of the 33rd annual coference on advances in neural information processing systems (NeurIPS\u00a0\u201920), Virtual Event, pp. 21050\u2013 21060 . https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/f10f2da9a238b746d2bac55759915f0d-Abstract.html"},{"key":"1259_CR3","unstructured":"Ahmadian S, Epasto A, Kumar R, Mahdian M ( 2020) Fair correlation clustering. In: Proceedings of the 23rd international conference on artificial intelligence and statistics (AISTATS\u00a0\u201920), pp. 4195\u2013 4205. PMLR, Virtual Event . http:\/\/proceedings.mlr.press\/v108\/ahmadian20a.html"},{"key":"1259_CR4","doi-asserted-by":"publisher","unstructured":"Ahmadi S, Galhotra S, Saha B, Schwartz R (2020) Fair correlation clustering. arXiv . https:\/\/doi.org\/10.48550\/ARXIV.2002.03508 . https:\/\/arxiv.org\/abs\/2002.03508","DOI":"10.48550\/ARXIV.2002.03508"},{"key":"1259_CR5","unstructured":"Ahmadian S, Negahbani M (2023) Improved approximation for fair correlation clustering. In: Proceedings of the 26th international conference on artificial intelligence and statistics (AISTATS\u00a0\u201923), pp. 9499\u2013 9516. PMLR, Valencia, Spain . https:\/\/proceedings.mlr.press\/v206\/ahmadian23a.html"},{"key":"1259_CR6","doi-asserted-by":"publisher","unstructured":"B\u00f6cker S, Baumbach J ( 2013) Cluster editing. In: Proceedings of the 9th international conference on computability in Europe (CiE\u00a0\u201913), pp. 33\u2013 44. Springer, Milan, Italy . https:\/\/doi.org\/10.1007\/978-3-642-39053-1_5","DOI":"10.1007\/978-3-642-39053-1_5"},{"issue":"1\u20132","key":"1259_CR7","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10107-009-0307-4","volume":"128","author":"A Berger","year":"2011","unstructured":"Berger A, Bonifaci V, Grandoni F, Sch\u00e4fer G (2011) Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Math Progr 128(1\u20132):355\u2013372. https:\/\/doi.org\/10.1007\/s10107-009-0307-4","journal-title":"Math Progr"},{"issue":"2","key":"1259_CR8","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/s00453-009-9339-7","volume":"60","author":"S B\u00f6cker","year":"2011","unstructured":"B\u00f6cker S, Briesemeister S, Klau GW (2011) Exact algorithms for cluster editing: evaluation and experiments. Algorithmica 60(2):316\u2013334. https:\/\/doi.org\/10.1007\/s00453-009-9339-7","journal-title":"Algorithmica"},{"key":"1259_CR9","doi-asserted-by":"publisher","unstructured":"Bandyapadhyay S, Fomin FV, Golovach PA, Purohit N, Simonov K ( 2022) FPT approximation for fair minimum-load clustering. In: proceedings of the 17th international symposium on parameterized and exact computation (IPEC\u00a0\u201922), pp. 4\u2013 1414. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Potsdam, Germany . https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.4","DOI":"10.4230\/LIPIcs.IPEC.2022.4"},{"key":"1259_CR10","doi-asserted-by":"publisher","unstructured":"Bandyapadhyay S, Fomin FV, Simonov K ( 2021) On coresets for fair clustering in metric and euclidean spaces and their applications. In: proceedings of the 48th international colloquium on automata, languages, and programming (ICALP\u00a0\u201921), pp. 23\u2013 12315. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Virtual Event . https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.23","DOI":"10.4230\/LIPIcs.ICALP.2021.23"},{"issue":"4","key":"1259_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai L (1996) Fixed-parameter tractability of graph modification problems for hereditary properties. Inform Proc Lett 58(4):171\u2013176. https:\/\/doi.org\/10.1016\/0020-0190(96)00050-6","journal-title":"Inform Proc Lett"},{"issue":"8","key":"1259_CR12","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen J, Huang X, Kanj IA, Xia G (2006) Strong computational lower bounds via parameterized complexity. J Comput Syst Sci 72(8):1346\u20131367. https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J Comput Syst Sci"},{"key":"1259_CR13","unstructured":"Chierichetti F, Kumar R, Lattanzi S, Vassilvitskii S ( 2017) Fair clustering through fairlets. In: proceedings of the 30th annual coference on advances in neural information processing systems (NIPS\u00a0\u201917), pp. 5029\u2013 5037. Curran Associates, Inc., Long Beach, CA, USA . https:\/\/papers.nips.cc\/paper\/by-source-2017-2591"},{"key":"1259_CR14","doi-asserted-by":"publisher","unstructured":"Chen J, Molter H, Sorge M, Such\u00fd O ( 2018) Cluster editing in multi-layer and temporal graphs. In: proceedings of the 29th international symposium on algorithms and computation (ISAAC\u00a0\u201918), pp. 24\u2013 12413. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Jaoxi, Yilan, Taiwan . https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.24 . https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.24","DOI":"10.4230\/LIPIcs.ISAAC.2018.24"},{"key":"1259_CR15","unstructured":"Chakrabarty D, Negahbani M ( 2021) Better algorithms for individually fair $$k$$-clustering. In: proceedings of the 34th annual coference on advances in neural information processing systems (NeurIPS\u00a0\u201921), Virtual Event, pp. 13340\u2013 13351 . https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/6f221fcb5c504fe96789df252123770b-Abstract.html"},{"key":"1259_CR16","doi-asserted-by":"publisher","unstructured":"Friggstad Z, Mousavi R ( 2021) Fair correlation clustering with global and local guarantees. In: proceedings of the 17th international symposium on algorithms and data structures (WADS\u00a0\u201921), pp. 414\u2013 427. Springer, Virtual Event . https:\/\/doi.org\/10.1007\/978-3-030-83508-8_30","DOI":"10.1007\/978-3-030-83508-8_30"},{"key":"1259_CR17","doi-asserted-by":"publisher","unstructured":"Guo J, Hartung S, Komusiewicz C, Niedermeier R, Uhlmann J ( 2010) Exact algorithms and experiments for hierarchical tree clustering. In: proceedings of the 24th conference on artificial intelligence (AAAI\u00a0\u201910), pp. 457\u2013 462. AAAI Press, Atlanta, GA, USA . https:\/\/doi.org\/10.1609\/aaai.v24i1.7684","DOI":"10.1609\/aaai.v24i1.7684"},{"key":"1259_CR18","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey MR, Johnson DS (1975) Complexity results for multiprocessor scheduling under resource constraints. SIAM J Comput 4:397\u2013411. https:\/\/doi.org\/10.1137\/0204035","journal-title":"SIAM J Comput"},{"issue":"4","key":"1259_CR19","doi-asserted-by":"publisher","first-page":"1662","DOI":"10.1137\/090767285","volume":"24","author":"J Guo","year":"2010","unstructured":"Guo J, Komusiewicz C, Niedermeier R, Uhlmann J (2010) A more relaxed model for graph-based data clustering: $$s$$-plex cluster editing. SIAM J Discr Math 24(4):1662\u20131683. https:\/\/doi.org\/10.1137\/090767285","journal-title":"SIAM J Discr Math"},{"key":"1259_CR20","doi-asserted-by":"publisher","unstructured":"Ghadiri M, Samadi S, Vempala SS ( 2021) Socially fair $$k$$-means clustering. In: proceedings of the ACM conference on fairness, accountability, and transparency (FAccT\u00a0\u201921), pp. 438\u2013 448. ACM, Virtual Event . https:\/\/doi.org\/10.1145\/3442188.3445906","DOI":"10.1145\/3442188.3445906"},{"issue":"1\u20133","key":"1259_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01589097","volume":"45","author":"M Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel M, Wakabayashi Y (1989) A cutting plane algorithm for a clustering problem. Math Progr 45(1\u20133):59\u201396. https:\/\/doi.org\/10.1007\/BF01589097","journal-title":"Math Progr"},{"issue":"15","key":"1259_CR22","doi-asserted-by":"publisher","first-page":"2259","DOI":"10.1016\/j.dam.2012.05.019","volume":"160","author":"C Komusiewicz","year":"2012","unstructured":"Komusiewicz C, Uhlmann J (2012) Cluster editing with locally bounded modifications. Discr Appl Math 160(15):2259\u20132270. https:\/\/doi.org\/10.1016\/j.dam.2012.05.019","journal-title":"Discr Appl Math"},{"issue":"1","key":"1259_CR23","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1232722.1232727","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web 1(1):5. https:\/\/doi.org\/10.1145\/1232722.1232727","journal-title":"ACM Trans Web"},{"key":"1259_CR24","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: stanford large network dataset collection . http:\/\/snap.stanford.edu\/data"},{"issue":"1","key":"1259_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-020-00746-y","volume":"83","author":"J Luo","year":"2021","unstructured":"Luo J, Molter H, Nichterlein A, Niedermeier R (2021) Parameterized dynamic cluster editing. Algorithmica 83(1):1\u201344. https:\/\/doi.org\/10.1007\/s00453-020-00746-y","journal-title":"Algorithmica"},{"issue":"6","key":"1259_CR26","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/3457607","volume":"54","author":"N Mehrabi","year":"2022","unstructured":"Mehrabi N, Morstatter F, Saxena N, Lerman K, Galstyan A (2022) A survey on bias and fairness in machine learning. ACM Comput Surv 54(6):115\u2013111535. https:\/\/doi.org\/10.1145\/3457607","journal-title":"ACM Comput Surv"},{"key":"1259_CR27","unstructured":"Mahabadi S, Vakilian A (2020) Individual fairness for $$k$$-clustering. In: proceedings of the 37th international conference on machine learning (ICML\u00a0\u201920), vol. 119, pp. 6586\u2013 6596. PMLR, Virtual Event . http:\/\/proceedings.mlr.press\/v119\/mahabadi20a.html"},{"issue":"1","key":"1259_CR28","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley K, Vazirani UV, Vazirani VV (1987) Matching is as easy as matrix inversion. Combinatorica 7(1):105\u2013113. https:\/\/doi.org\/10.1007\/BF02579206","journal-title":"Combinatorica"},{"issue":"3","key":"1259_CR29","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/3494672","volume":"55","author":"D Pessach","year":"2023","unstructured":"Pessach D, Shmueli E (2023) A review on fairness in machine learning. ACM Or any chance Darwin\/Emily wil be at Inet tomorrow? :slightly_smiling_face:Comput Surv 55(3):51\u201315144. https:\/\/doi.org\/10.1145\/3494672","journal-title":"ACM Comput Surv"},{"key":"1259_CR30","doi-asserted-by":"publisher","unstructured":"Schwartz R, Zats R( 2022) Fair correlation clustering in general graphs. In: proceedings of the conference on approximation, randomization, and combinatorial optimization (APPROX\/RANDOM\u00a0\u201922), pp. 37\u2013 13719. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Virtual Event . https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2022.37","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.37"},{"key":"1259_CR31","doi-asserted-by":"publisher","unstructured":"Vakilian A, Yal\u00e7\u0131ner M (2021) Improved approximation algorithms for individually fair clustering. arXiv . https:\/\/doi.org\/10.48550\/ARXIV.2106.14043","DOI":"10.48550\/ARXIV.2106.14043"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-024-01259-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13278-024-01259-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-024-01259-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T14:30:30Z","timestamp":1740493830000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13278-024-01259-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,25]]},"references-count":31,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["1259"],"URL":"https:\/\/doi.org\/10.1007\/s13278-024-01259-0","relation":{},"ISSN":["1869-5469"],"issn-type":[{"value":"1869-5469","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,25]]},"assertion":[{"value":"30 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"109"}}