Pith. sign in

REVIEW 4 major objections 4 minor 47 references

Equalizing Closeness Centralities via Edge Additions

T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A near-linear-time algorithm equalizes two nodes' closeness centralities to at least 6/11 of the best possible ratio, while the gap variant is unapproximable.

desk verdict A solid, original contribution to network-fairness algorithms with sound hardness results and a 6/11-approximation that holds up; the one flagged concern in Lemma 4 dissolves on inspection. read the letter →

arxiv 2505.06222 v1 pith:6Z7XXHNQ submitted 2025-05-09 cs.DS cs.SI

Alex Crane , Sorelle A. Friedler , Mihir Patel , Blair D. Sullivan This is my paper · ORCID
classification cs.DScs.SI MSC 68Q1768W2568R10
keywords closenesscentralityedgeadditionsgraphmodificationfairnessinnetworksapproximationalgorithmNP-hardnesssocialcapital
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Closeness centrality measures a node's network position by its total distance to everyone else. This paper studies the algorithmic-fairness question of adding at most $k$ edges to make two specified nodes $a,b$ equally central, and finds a sharp difference between two natural objectives. The ratio version, Closeness Ratio Improvement, is $\mathsf{NP}$-hard for every target ratio in $(\frac12,1]$, yet admits a quasilinear-time $\frac{6}{11}$-approximation: a simple strategy---add the edge $ab$, then edges from $a$ to $b$'s neighbors---is guaranteed to achieve at least $\frac{6}{11}$ of the best possible ratio. The gap version, Closeness Gap Minimization, is $\mathsf{NP}$-hard and cannot have any multiplicative approximation unless $\mathsf{P}=\mathsf{NP}$. The paper thereby shows that equalizing social capital through link additions is tractable in a principled sense for the ratio objective, and hopeless for the difference objective.

What carries the argument

The engine of the result is Algorithm 1, which adds the edge $ab$ (if absent) and then repeatedly adds an edge from $a$ to a vertex in $b$'s private neighbourhood $\mathcal N_{G+S}(b)\setminus \mathcal N_{G+S}[a]$ until the budget is spent or $a$'s closeness falls below $b$'s. The correctness rests on three structural lemmas: the No Switching Lemma, which says that if adding $ab$ reverses the centrality order then one of the current graphs already achieves $\frac{6}{11}$; the Termination Lemma, which guarantees early stopping is safe; and a sufficient-condition lemma showing that $k+|\mathcal N_G(a)|\ge n/6$ forces a $\frac{6}{11}$ outcome. Lemma 4 supplies the converse: when neither $G$ nor $G+ab$ is $\frac{6}{11}$-approximate, the optimal solution must have $d_{G^*}(a,b)\in\{1,2\}$ and the large-neighbourhood condition must hold. The proof repeatedly uses a ratio-monotonicity observation: for nonnegative $w\le p\le q$, the fraction $(p+w)/(q+w)$ is at least $p/q$, which lets the paper strip away error terms.

What would settle it

Run Algorithm 1 on every graph with, say, at most 9 vertices and compare its output against exhaustive search over all $\binom{\binom{n}{2}}{k}$ edge sets; a single instance in which the algorithm's ratio is below $\frac{6}{11}$ of the optimal ratio would refute Theorem 4. Since the algorithm and the optimum are both finitely computable, this is a direct computational check.

Watch

Extended reading notes

Core claim

The paper's central discovery is a structural description of the hard instances of Closeness Ratio Improvement. It proves that if neither the original graph nor the graph obtained by adding the single edge $ab$ already achieves a $\frac{6}{11}$ ratio, then the optimal solution $G^*$ must place $a$ and $b$ at distance $1$ or $2$, and $b$ must have a very large private neighborhood; in that situation $k+|\mathcal N_G(a)|\ge n/6$, which lets a simple greedy edge-addition algorithm reach the $\frac{6}{11}$ guarantee. Equivalently, the only graphs where the trivial edge $ab$ is inadequate are graphs in which $b$ has so many private neighbors that adding edges from $a$ to those neighbors is provably effective. The same construction that gives $\mathsf{NP}$-hardness for target ratio $1$ is extended to every $\tau\in(1/2,1)$, and the same reduction shows the gap-minimization variant has no multiplicative approximation.

Load-bearing premise

The chain of inequalities in Lemma 4 is load-bearing and silently presumes that in an optimal solution $G^*$, the node $b$ is at least as central as $a$ (i.e. $\operatorname{cc}_{G^*}(a)\ge\operatorname{cc}_{G^*}(b)$); without that orientation, the bound $\operatorname{cc}_{G^*}(a)\le \frac{12}{11}\operatorname{cc}_{G^*}(b)$ does not follow from the written text.

Editorial extensions

If this is right

  • For every input $(G,a,b,k)$, Algorithm 1 runs in $O((n+m)\log k)$ time and returns an edge set with closeness ratio at least $\frac{6}{11}$ of the optimum.
  • Exact optimization is out of reach in general: Closeness Ratio Improvement is $\mathsf{NP}$-hard and $\mathsf{W}[2]$-hard in $k$ for every target ratio in $(\frac{1}{2},1]$.
  • The trivial bound of $\frac{1}{2}$ from adding the single edge $ab$ is tight, so $\frac{6}{11}$ is a real improvement over the naive intervention.
  • Closeness Gap Minimization is not only hard but inapproximable: no multiplicative factor is possible unless $\mathsf{P}=\mathsf{NP}$.
  • Any algorithm allowed $ck$ edges, for constant $c\ge1$, cannot guarantee a ratio better than $\frac{5ec}{5ec+1}-\epsilon$ for any $\epsilon>0$, unless $\mathsf{P}=\mathsf{NP}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The omitted orientation case in Lemma 4 looks repairable from the paper's own bounds: if $d_{G^*}(a,b)\ge3$, the structural claims force $a$ to be the less central node, and the opposite orientation gives stronger estimates on $k$; a filled-in proof should keep the $6/11$ theorem intact.
  • Because Algorithm 1 is deterministic and near-linear, an empirical study could test whether the $6/11$ guarantee is loose on real social graphs; the lemmas suggest hard instances are sparse graphs where $b$ has an enormous private neighbourhood.
  • The same private-neighbourhood decomposition is a plausible starting point for the two proposed generalizations, Group Closeness Ratio Improvement and All-Pairs Closeness Ratio Improvement, though the $1/2$ trivial baseline from adding $ab$ does not carry over.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies two graph-modification problems in which a budget of k edge additions is used to equalize the closeness centralities of two designated vertices a and b: Closeness Ratio Improvement, which maximizes the ratio min(cc(a),cc(b))/max(cc(a),cc(b)), and Closeness Gap Minimization, which minimizes the absolute difference |cc(a)-cc(b)|, where closeness is the sum of shortest-path distances. The authors prove that both problems are NP-hard, give a quasilinear-time 6/11-approximation for the ratio version, and prove a bicriteria inapproximability bound for the ratio version as well as the non-approximability of the gap version. The main algorithmic contribution is a simple strategy: add the edge ab, then repeatedly add edges from a to vertices in b's neighborhood, with early-termination rules.

Significance. If the results are correct, this is a solid contribution to the emerging literature on algorithmic fairness through network modification. The paper introduces a well-motivated pair of problems, establishes hardness thresholds, and provides a nontrivial constant-factor approximation with a quasilinear runtime, which is a good algorithmic result for a non-submodular, non-monotone objective. The bicriteria inapproximability result is also of interest. The hardness reductions are carefully constructed and mostly check out, and the paper is generally well written. However, two load-bearing proofs contain errors that currently prevent the central claims from being regarded as established.

major comments (4)
  1. [§4, Lemma 2] The proof of the Termination Lemma contains an incorrect set inclusion. The text claims that because u∈N_G(b), we have A_{G+au}⊆A_G, where A_H={v:d_H(a,v)<d_H(b,v)}. In fact, adding the edge au can only decrease distances from a, and when ab∈E and u∈N_G(b), distances from b are unchanged (any path through the new edge has length at least d_G(b,v)+1 by the triangle inequality). Hence A_G⊆A_{G+au}, and the asserted contradiction between |A_{G+au}|>(n-2)/2 and |B_G|>(n-2)/2 does not follow. Since Lemma 2 is used to justify the early-termination condition in Algorithm 1 and is then relied upon by Lemmas 3 and 4 and Theorem 4, the 6/11-approximation proof is incomplete as written. The lemma may be true, but a different or corrected argument is required.
  2. [§3, Theorem 3] The final calibration algebra in the bicriteria inapproximability proof is incorrect. Starting from (1-ε')(5ec+1-ecδ)≥5ec+1-ε, the correct rearrangement is ε≥ε'(5ec+1)+ecδ(1-ε'), not ε≥ε'(5ec-1)+ecδ(1-ε') as written. With the stated choices ε'=ε/(2(5ec-1)) and δ=ε/(2ec(1-ε')), the required inequality fails: the right-hand side becomes ε+ε/(5ec-1)>ε. The claimed approximation barrier 5ec/(5ec+1-ε) is therefore not established by the proof as written. The argument appears repairable (e.g., setting ε'=ε/(2(5ec+1)) would make the condition hold with equality), but the current text needs correction.
  3. [§4, Lemma 4, Claim 7] In the lower-bound argument for cc_{G*}(a), the set O is defined in the text as V\(A_p∪{a,b}), but the subsequent computation uses O=V\(B_p∪{a,b}) with |B_p|=4(n-2)/5+x. This is a typo in a central bound; it should be corrected to avoid confusion. As written, the notation makes the proof difficult to follow, though the intended argument is clear.
  4. [§4, Theorem 4] The claimed O((n+m) log k) runtime is only sketched. The binary search over the k-1 previous states of S requires a precise implementation: the algorithm must record the sequence of added edges and, for a queried prefix length ℓ, compute distances from a and b in G plus the first ℓ added edges. Since each BFS costs O(n+m+ℓ) and ℓ<k, the claim is plausible, but the manuscript would benefit from an explicit description of how the prefix evaluations are performed without re-running the entire loop.
minor comments (4)
  1. [§3, Theorem 3] The displayed chain 'n/(n+ck) > n/(n·1/(1+ε′)) > 1−ε′' appears garbled; the intended inequality is n/(n+ck) > 1/(1+ε′) > 1−ε′.
  2. [§4, Lemma 4] The inference from '3n/11−8/11<k' to 'n/6<k' is not valid as a direct real inequality for all n>3 (e.g., n=6), though it becomes true for integral k in the cases that matter, and the final conclusion k+|N_G(a)|≥n/6 still holds. The proof should state the integrality argument explicitly.
  3. [§4, Lemma 4] The statement that for n<7 one may assume d_{G*}(a,b)<3 because otherwise part (iii) of Claim 5 is impossible is incorrect; for n=6, |B_p|=4 can satisfy |B_p|>4(n-2)/5 with d_{G*}(a,b)=3. The small-n case is easily handled because the lemma's conclusion is trivial for n≤6, but the current sentence should be revised.
  4. [§2.2, Observation 1] Observation 1 invokes Observation 2 before Observation 2 is stated; reordering or an explicit forward reference would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all central claims are derived from first principles against external Set Cover hardness.

full rationale

The paper's central claims are self-contained rather than circular. The NP-hardness and inapproximability results (Theorems 1–3 and Corollary 1) reduce from Set Cover and from Feige's external set-cover hardness threshold, and all reduction-specific distance and centrality arithmetic is derived explicitly in the paper. The 6/11-approximation (Theorem 4) is established by elementary structural claims (Claims 3–8) and lemmas (Lemmas 1–4) using triangle inequalities and set-size bounds; no parameter is fitted to the objective, no definition of the objective is used as its own proof, and no conclusion is imported from a self-citation. The self-citations ([7], [10], [16]) appear only in contextual motivation and open-problem discussion, not as load-bearing proof inputs. The flagged orientation issue in Claim 7 is a possible expositional omission in an internal inequality, not a reduction of a result to its own assumptions, and it does not create circularity. Overall, the derivation chain is independent of its conclusions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claims rest on standard graph theory and widely used Set Cover hardness results; no free parameters are fitted to data and no new entities are postulated.

assumptions (3)
  • standard math Set Cover is NP-hard and W[2]-hard parameterized by cover size k.
    Basis for the reductions in Theorems 1, 2, and Corollary 1. Standard result cited to the literature.
  • standard math Feige et al. strengthened hardness of Set Cover: distinguishing set cover of size k from instances where every ck sets cover at most (1 - (1-1/k)^{ck} + δ)n elements is NP-hard.
    Used in Theorem 3 for the bicriteria inapproximability bound. Strong but standard complexity result from Feige and follow-up work.
  • standard math The triangle inequality for shortest-path distances in undirected graphs.
    Used in Observation 1, Claims 4 and 6, Lemma 3, and throughout the approximation analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Equalizing Closeness Centralities via Edge Additions." pith.science (2026). https://pith.science/paper/6Z7XXHNQ

@misc{pith2026250506222,
  author       = {Pith},
  title        = {Pith review of: Equalizing Closeness Centralities via Edge Additions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6Z7XXHNQ}},
  note         = {Machine review of arXiv:2505.06222}
}
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 two 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. We show that both problems are $\textsf{NP}$-hard, and for Closeness Ratio Improvement we present a quasilinear-time $\frac{6}{11}$-approximation, complemented by a bicriteria inapproximability bound. In contrast, we show that Closeness Gap Minimization admits no multiplicative approximation unless $\textsf{P} = \textsf{NP}$. We conclude with a discussion of open directions for this style of problem, including several natural generalizations.

Figures

Figures reproduced from arXiv: 2505.06222 by the authors.

Figure 1
Figure 1. The constructions used for counterexamples in Section [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The worst possible closeness ratio when a and b are adjacent. Observation 1. If a and b are adjacent, then cc-ratioG(a, b) > 1 2 . To see Observation 1, assume WLOG that ccG(b) ≤ ccG(a). By the triangle inequality, if a and b are adjacent, then for any vertex v, dG(a, v) ≤ dG(a, b) + dG(b, v) = 1 + dG(b, v). It follows that ccG(a) = dG(a, a) + dG(a, b) + X v∈V \{a,b} dG(a, v) = dG(b, b) + dG(a, b) + X v∈V \{a,b} dG(… view at source ↗
Figure 3
Figure 3. The construction given by Theorem 1. We denote set vertices by sj and element vertices by vi . Here, ISX is an independent set of X vertices, with each vertex adjacent to a. We refer to the proof of Theorem 1 for a formal description of the construction and the accompanying analysis. Closeness Ratio Improvement (Decision Variant) Input: A graph G = (V, E), vertices a, b ∈ V , a budget k ∈ N, and a target ratio τ ∈ (… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: A depiction of the construction given by Theorem [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 44 canonical work pages

  1. [2]

    Adriaens and A

    F. Adriaens and A. Gionis. Diameter minimization by shortcutting with degree constraints. In 2022 IEEE International Conference on Data Mining (ICDM), pages 843–848. IEEE, 2022

    work page 2022

  2. [1]

    Abbasi, A

    M. Abbasi, A. Bhaskara, and S. Venkatasubramanian. Fair clustering via equitable group representations. InProceedings of the 2021 ACM conference on fairness, accountability, and transparency (FAccT), pages 504–514. ACM, 2021

    work page 2021

  3. [3]

    Ahmadi, S

    S. Ahmadi, S. Galhotra, B. Saha, and R. Schwartz. Fair correlation clustering.ArXiv preprint arxiv:2002.03508, 2020

    arXiv 2002

  4. [4]

    Ahmadian and M

    S. Ahmadian and M. Negahbani. Improved approximation for fair correlation clustering. In International Conference on Artificial Intelligence and Statistics (AISTATS) 2023, volume 206 ofProceedings of Machine Learning Research, pages 9499–9516. PMLR, 2023

    work page 2023

  5. [5]

    Ahmadian, A

    S. Ahmadian, A. Epasto, R. Kumar, and M. Mahdian. Fair correlation clustering. InThe 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, volume 108 ofProceedings of Machine Learning Research, pages 4195–4205. PMLR, 2020

    work page 2020

  6. [6]

    Avrachenkov and N

    K. Avrachenkov and N. Litvak. The effect of new links on google pagerank.Stochastic Models, 22(2):319–331, 2006. 23

    work page 2006

  7. [7]

    Bashardoust, S

    A. Bashardoust, S. Friedler, C. Scheidegger, B. D. Sullivan, and S. Venkatasubramanian. Reducing access disparities in networks using edge augmentation. InProceedings of the ACM Conference on Fairness, Accountability, and Transparency (FAccT), pages 1635–1651, 2023

    work page 2023

  8. [8]

    I. O. Bercea, M. Groß, S. Khuller, A. Kumar, C. Rösner, D. R. Schmidt, and M. Schmidt. On the cost of essentially fair clusterings. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, volume 145 ofLIPIcs, pages 18:1–18:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019

    work page 2019

Show all 47 references
  1. [9]

    Bergamini, P

    E. Bergamini, P. Crescenzi, G. D’Angelo, H. Meyerhenke, L. Severini, and Y. Velaj. Improving the betweenness centrality of a node by adding links.Journal of Experimental Algorithmics, 23:1–32, 2018

    2018

  2. [10]

    Bhaskara, A

    A. Bhaskara, A. Crane, S. Jain, M. M. H. U. Mazumder, B. D. Sullivan, and P. Yalaman- chili. Optimizing information access in networks via edge augmentation.arXiv preprint arXiv:2407.02624, 2024

    2024 arXiv

  3. [11]

    D. Bilò, L. Gualà, and G. Proietti. Improved approximability and non-approximability results for graph diameter decreasing problems.Theoretical Computer Science, 417:12–22, 2012

    2012

  4. [12]

    Boldi and S

    P. Boldi and S. Vigna. Axioms for centrality.Internet Mathematics, 10(3-4):222–262, 2014

    2014

  5. [13]

    S. P. Borgatti, C. Jones, and M. G. Everett. Network measures of social capital.Connections, 21(2):27–36, 1998

    1998

  6. [14]

    Casel, T

    K. Casel, T. Friedrich, M. Schirneck, and S. Wietheger. Fair correlation clustering in forests. In 4th Symposium on Foundations of Responsible Computing, FORC 2023, volume 256 ofLIPIcs, pages 9:1–9:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023

    2023

  7. [15]

    Chierichetti, R

    F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. Advances in Neural Information Processing Systems, 30, 2017

    2017

  8. [16]

    Crane, T

    A. Crane, T. Stanley, B. D. Sullivan, and N. Veldt. Edge-colored clustering in hypergraphs: Beyond minimizing unsatisfied edges. InProceedings of the International Conference on Machine Learning (ICML), 2025

    2025

  9. [17]

    Crescenzi, G

    P. Crescenzi, G. D’Angelo, L. Severini, and Y. Velaj. Greedily improving our own closeness centrality in a network.ACM Transcations on Knowledge Discovery from Data, 11(1):1–32, 2016

    2016

  10. [18]

    Crespelle, P

    C. Crespelle, P. G. Drange, F. V. Fomin, and P. A. Golovach. A survey of parameterized algorithms and the complexity of edge modification.Comput. Sci. Rev., 48:100556, 2023

    2023

  11. [19]

    Cygan, F

    M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.Parameterized algorithms, volume 5. Springer, 2015

    2015

  12. [20]

    Simultaneouslyapproximatingalllp-normsincorrelation clustering

    S.Davies, B.Moseley, andH.Newman. Simultaneouslyapproximatingalllp-normsincorrelation clustering. In51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, volume 297 ofLIPIcs, pages 52:1–52:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024

    2024

  13. [21]

    E. D. Demaine and M. Zadimoghaddam. Minimizing the diameter of a network using shortcut edges. InProceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 6139 ofLecture Notes in Computer Science, pages 420–431. Springer, 2010. 24

    2010

  14. [22]

    Farnad, B

    G. Farnad, B. Babaki, and M. Gendreau. A unifying framework for fairness-aware influence maximization. InCompanion Proceedings of the Web Conference 2020, pages 714–722, 2020

    2020

  15. [23]

    U. Feige. A threshold of ln n for approximating set cover.Journal of the ACM (JACM), 45(4): 634–652, 1998

    1998

  16. [24]

    Feige and J

    U. Feige and J. Vondrák. The submodular welfare problem with demand queries.Theory of Computing, 6(1):247–290, 2010

    2010

  17. [25]

    Feige, L

    U. Feige, L. Lovász, and P. Tetali. Approximating min sum set cover.Algorithmica, 40:219–234, 2004

    2004

  18. [26]

    B. Fish, A. Bashardoust, D. Boyd, S. Friedler, C. Scheidegger, and S. Venkatasubramanian. Gaps in information access in social networks? InThe World Wide Web Conference, pages 480–490, 2019

    2019

  19. [27]

    Frati, S

    F. Frati, S. Gaspers, J. Gudmundsson, and L. Mathieson. Augmenting graphs to minimize the diameter.Algorithmica, 72:995–1010, 2015

    2015

  20. [28]

    S. A. Friedler, C. Scheidegger, S. Venkatasubramanian, S. Choudhary, E. P. Hamilton, and D. Roth. A comparative study of fairness-enhancing interventions in machine learning. In Proceedings of the ACM conference on Fairness, Accountability, and Transparency, pages 329–338, 2019

    2019

  21. [29]

    Froese, L

    V. Froese, L. Kellerhals, and R. Niedermeier. Modification-fair cluster editing.Social Network Analysis and Mining, 14(1):109, 2024

    2024

  22. [30]

    Ghadiri, S

    M. Ghadiri, S. Samadi, and S. Vempala. Socially fair k-means clustering. InProceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 438–448, 2021

    2021

  23. [31]

    M. S. Granovetter. The strength of weak ties.American Journal of Sociology, 78(6):1360–1380, 1973

    1973

  24. [32]

    Hardt, E

    M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. volume 29, 2016

    2016

  25. [33]

    Z. S. Jalali, Q. Chen, S. M. Srikanta, W. Wang, M. Kim, H. Raghavan, and S. Soundarajan. Fairness of information flow in social networks.ACM Transactions on Knowledge Discovery from Data, 17(6):1–26, 2023

    2023

  26. [34]

    Komusiewicz and J

    C. Komusiewicz and J. Uhlmann. Cluster editing with locally bounded modifications.Discrete Applied Mathematics, 160(15):2259–2270, 2012

    2012

  27. [35]

    C.-L. Li, S. T. McCormick, and D. Simchi-Levi. On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems.Operations Research Letters, 11:303–308, 1991

    1991

  28. [36]

    D. Liu, Z. Shafi, W. Fleisher, T. Eliassi-Rad, and S. Alfeld. Rawlsnet: Altering bayesian networks to encode rawlsian fair equality of opportunity. InProceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 745–755, 2021

    2021

  29. [37]

    Medya, A

    S. Medya, A. Silva, A. Singh, P. Basu, and A. Swami. Group centrality maximization via network design. InProceedings of the 2018 SIAM International Conference on Data Mining, pages 126–134. SIAM, 2018. 25

    2018

  30. [38]

    Meyerson and B

    A. Meyerson and B. Tagiku. Minimizing average shortest path distances via shortcut edge addition. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, (APPROX), volume 5687 ofLecture Notes in Computer Science, ...

    2009

  31. [39]

    Olsen and A

    M. Olsen and A. Viglas. On the approximability of the link building problem.Theoretical Computer Science, 518:96–116, 2014

    2014

  32. [40]

    Puleo and O

    G. Puleo and O. Milenkovic. Correlation clustering and biclustering with locally bounded errors. InProceedings of the International Conference on Machine Learning, pages 869–877. PMLR, 2016

    2016

  33. [41]

    X. Rui, Z. Wang, J. Zhao, L. Sun, and W. Chen. Scalable fair influence maximization. In Advances in Neural Information Processing Systems, volume 36, pages 66675–66691, 2023

    2023

  34. [42]

    Saxena, G

    A. Saxena, G. Fletcher, and M. Pechenizkiy. Fairsna: Algorithmic fairness in social network analysis.ACM Computing Surveys, 56(8):1–45, 2024

    2024

  35. [43]

    L. Shan, Y. Yi, and Z. Zhang. Improving information centrality of a node in complex networks by adding edges. InProceedings of the 27th International Joint Conference on Artificial Intelligence, pages 3535–3541, 2018

    2018

  36. [44]

    Stoica and A

    A.-A. Stoica and A. Chaintreau. Fairness in social influence maximization. InCompanion Proceedings of The 2019 World Wide Web Conference, pages 569–574, 2019

    2019

  37. [45]

    Stoica, J

    A.-A. Stoica, J. X. Han, and A. Chaintreau. Seeding network influence in biased networks and the benefits of diversity. InProceedings of The Web Conference 2020, pages 2089–2098, 2020

    2020

  38. [46]

    Vakilian and M

    A. Vakilian and M. Yalciner. Improved approximation algorithms for individually fair clus- tering. InProceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 8758–8779. PMLR, 2022

    2022

  39. [47]

    M.-H. Yeh, B. Metevier, A. Hoag, and P. Thomas. Analyzing the relationship between difference and ratio-based fairness metrics. InProceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency, pages 518–528, 2024. 26

    2024

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.