Original title: Fair Top-k Katz Centrality via Graph Design
Ivan Qin, Prudence Wong, Lutz Oettershagen · September 2026
Computer algorithms often rank people or accounts in a network to pick the top few results, a list called the top-k rankingThe list of the k highest-ranked nodes according to a centrality score.. Katz centralityA measure of node importance based on paths and connections in a network. is one popular score used for this. However, these top lists can be unfair to certain groups. Instead of changing how scores are calculated, the researchers changed the network itself. They added directed connections between nodes to help underrepresented nodes reach the top list. They proved that finding the absolute smallest number of changes is theoretically hard. Then, they showed that helpful edits must push qualified outside nodes past inside rivals right at the boundary. Using this insight, they built an algorithm called BLADE. On synthetic and real-world networks, BLADE hits the target group balance with far fewer changes than natural baseline methods.
Imagine you're picking the top ten players for a school basketball team based on skills, but the list has mostly players from one club. To make it fair, you want to include others, but you don't have time to scout everyone. You realize that only a few players are close to making the cut, and by adding a couple of them or adjusting the selection slightly, you can achieve balance. In this paper, the network is like the group of players, and the goal is to add a few edges to promote borderline nodes to meet fairness goals without extensive changes.
Networks rank people and things, like influencers on social media or papers in citations. If top lists are biased, decisions and perceptions can be unfair. This work allows fixing fairness with minimal changes to the network.
The abstract does not address other centrality measures besides Katz or different fairness criteria. It also states that the minimum-edit problem is strongly inapproximable, so optimal solutions may not be computationally feasible.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Fair Top-k Katz Centrality via Graph Design — Ivan Qin, Prudence Wong, Lutz Oettershagen
Abstract licence: CC0
Explanation generated by Synthesis from the abstract — it is not the original paper. This is a preprint, so it hasn't necessarily been peer reviewed.