Equalizing Closeness Centralities via Edge Additions
Alex Crane, Sorelle A. Friedler, Mihir Patel, Freda Shi, Blair D. Sullivan, Madelyn J. Warr · 2025
Read Equalizing Closeness Centralities via Edge Additions by Alex Crane, Sorelle A. Friedler, Mihir Patel, Freda Shi, Blair D. Sullivan, Madelyn J. Warr (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06222.txt.
Introduction
Alex Crane and five co-authors study how to add edges to a network so two nodes end up equally central. Their twenty twenty-five paper uses closeness centrality, a score for how near a node is to all others. The aim is fairness: in social terms, an even share of network advantage.
Two versions are set out. One asks to push the ratio of the two scores as high as it can go, and the team gives a fast approximation method for it, with a matching hardness bound. The other asks to shrink the gap, and there they prove no good multiplicative approximation exists unless P equals NP. A third, all-pairs version is also shown hard.
Catalog record
| CREATOR | Alex Crane, Sorelle A. Friedler, Mihir Patel, Freda Shi, Blair D. Sullivan, Madelyn J. Warr |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06222
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Equalizing Closeness Centralities via Edge Additions Alex Crane, Sorelle A. Friedler, Mihir Patel, Freda Shi, Blair D. Sullivan, Madelyn J. Warr Abstract Graph modification problems with the goal of optimizing some measure of a given node’s network position have a rich history in the algorithms literature. Less commonly explored are modification problems with the goal of equalizing positions, though this class of problems is well-motivated from the perspective of equalizing social capital, i.e., algorithmic fairness. In this work, we study how to add edges to make the closeness centralities of a given pair of nodes more equal. We formalize several versions of this problem: Closeness Ratio Improvement , which aims to maximize the ratio of closeness centralities between two specified nodes, and Closeness Gap Minimization , which aims to minimize the absolute difference of centralities. For the former, we present a quasilinear-time 6 11 \frac{6}{11} -approximation, complemented by a bicriteria inapproximability bound. In contrast to this positive result, we show that Closeness Gap Minimization admits no multiplicative approximation, unless P = NP \textnormal{{P}}=\textnormal{{NP}} . We also establish NP -hardness for All-Pairs Closeness Ratio Improvement , which aims to maximize the minimum ratio of closeness centralities across all node pairs. 1 Introduction An important class of problems in the algorithmic fairness literature presents as input a network (a graph, possibly with some algorithmically relevant metadata) and asks for an efficiently computed set of network interventions meant either to alter the social dynamics of the network, or to reveal already present hidden structure. Generally, the motivating assumption is that real-world resources accrue to people in prominent positions within social networks, and that the distribution of this so-called social capital hinges on network structure itself [ 33 ] . For a broad survey, see [ 47 ] . Work in this direction has generally proceeded along several (occasionally overlapping) lines of inquiry. The first has focused on studying classic combinatorial optimization problems with fairness constraints , and exploring the algorithmic cost of these constraints by either proving impossibility results or lifting algorithmic techniques used for the classic unconstrained version of the problem. Fair clustering has received special emphasis, e.g., [ 3 , 4 , 5 , 1 , 31 , 52 , 23 ] , especially since the seminal work of Chierichetti et al. [ 17 ] . Often, relatively tractable combinatorial problems are significantly harder when the solution space is constrained to enforce fairness, e.g., [ 16 ] , though there have been some algorithmic success stories involving bicriteria approximations, e.g. [ 9 , 1 , 19 ] , or dual parameterizations, e.g., [ 38 ] . Somewhat more successful has been the trend of encoding fairness via a modified objective function, rather than by imposing additional constraints on a classic objective, e.g., [ 30 , 1 ] . With this perspective, a series of works on minimax or \ell_{p} -norm correlation clustering (beginning with [ 45 ] , most recently [ 23 ] ) as well as modification with “degree constraints,” e.g., [ 38 , 2 ] , can be seen through a fairness lens, even if fairness was not the original motivation. This line of work has been primarily theoretical, although an important practical insight, seen in e.g., [ 9 , 23 , 19 ] , is that the cost of fairness is often low in the sense that fair solutions are also often high-quality when evaluated by traditional criteria. Another line of work is distinguished by an empirical focus on information access, combined with some theoretical analysis, often in the context of some non-trivial diffusion model such as Independent Cascade [ 37 ] . This has given rise to fair variants of, e.g., the classic influence maximization problem [ 27 , 50 ] . Interventions in this setting could include selecting vertices at which to seed information (in which case the intervention is a modification of the metadata, rather than the underlying graph) or modifying the graph directly through e.g., edge addition, including formal or empirical analysis of the information spreading properties of proposed heuristics [ 7 , 51 , 27 , 50 , 40 , 36 ] . While the majority of works in this literature have introduced and experimentally evaluated heuristics, recently a greater interest in the analysis of algorithms has emerged, e.g., [ 12 , 46 ] . This network/graph focused work builds upon a broader literature studying fairness in machine learning. This literature has considered fairness both through added constraints (e.g., [ 34 ] ) and via modified objective functions (e.g., [ 29 ] ) where some emphasis has been given to understanding which classes of objective functions are most socially desirable from a fairness perspective, e.g., [ 53 ] . Both lines of work can also be divided into approaches which emphasize individual fairness by optimizing a maximin or minimax objective over all nodes, e.g., [ 27 , 45 ] , or by imposing a per-node fairness constraint, e.g., [ 38 ] , and approaches which emphasize group fairness by optimizing various measures based on demographic node attributes, e.g., [ 25 , 50 ] . In this work, we take a group fairness approach and directly optimize a fairness objective, but we do so in a purely graph-theoretic context, and our approach is closely aligned with a classic discrete algorithms perspective. Instead of considering a complex model of information flow, we will use centrality to measure a node’s social capital, e.g., in the spirit of [ 15 ] . Though many notions of centrality exist, we focus on closeness centrality , which is simple to understand, exhibits many qualities desirable in a centrality measure 1 1 1 In our context (undirected connected graphs), the “main problem” with closeness centrality identified by [ 14 ] (non-reachability) does not occur. [ 14 ] , and is very popular in the recent algorithms literature, e.g., [ 10 , 35 , 11 , 49 ] . Thus, closeness is a natural starting point for our goal of algorithmically equalizing node centralities. Formally, we consider a simple, unweighted, undirected graph G with two specified vertices a,b and an integer k . Our task is to add at most k edges to G while maximizing the ratio of the centralities of a and b , i.e., the best possible objective value is 1 . Here, the closeness centrality \textnormal{cc}_{{G}}({v}) of a vertex v is the sum of v ’s shortest-path distances to all vertices. 2 2 2 Closeness is also commonly defined as the reciprocal of this quantity. In the context of our objective (a ratio of closeness centralities), there is no meaningful distinction between these definitions. The impossibility result we establish for a gap-variant ( Corollary 1 ) also holds for both definitions. We note that the restriction to just two specified vertices of interest is a severe one, but also not dissimilar to many algorithmic works which impose such restrictions to make steps toward a more general goal, e.g., group fairness works restricted to two groups [ 30 , 3 ] , or partitioning problems restricted to two clusters [ 32 ] . We formalize two extensions of our two-vertex setting in Section 2 . The first directly