Metraipolis › archive › dc_8201213e45cb

Fair Top-k Katz Centrality via Graph Design — arXiv:2609.03899

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.03899
License (as archived): CC0-1.0
Archived: 2026-10-17T02:03:35.422Z
SHA-256 of the archived text: 570ff17c44bd689ffc0aefa528edafe90b1d9ad349a371218fc5603ec463f4c1
Stable URL of this page: https://metraipolis.com/documento/dc_8201213e45cb

How to cite

Fair Top-k Katz Centrality via Graph Design — arXiv:2609.03899 — arXiv (en), https://arxiv.org/abs/2609.03899 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8201213e45cb (Metraipolis archive dc_8201213e45cb, sha256 570ff17c44bd689ffc0aefa528edafe90b1d9ad349a371218fc5603ec463f4c1)

BibTeX

@misc{dc8201213e45cb,
  title = {Fair Top-k Katz Centrality via Graph Design — arXiv:2609.03899},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.03899},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8201213e45cb; sha256 570ff17c44bd689ffc0aefa528edafe90b1d9ad349a371218fc5603ec463f4c1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03899. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Centrality measures are widely used to rank nodes in networked data, but fairness interventions for graph centrality typically target global score mass or modify the centrality operator rather than controlling who appears in the displayed top-k ranking. We study this top-k setting for Katz centrality. Given a target group proportion, an admissible set of directed edge additions, and a fairness tolerance, the goal is to find the smallest edit set whose resulting Katz top-k ranking satisfies the target representation constraint. We formalize this problem as Fair Top-k Katz Centrality Design and show that the minimum-edit objective is strongly inapproximable, ruling out worst-case polynomial-time approximation guarantees unless P = NP. We then derive closed-form Katz sensitivity expressions showing that useful edits are boundary-driven: they must help promotable nodes outside the top-k set overtake opposing nodes inside it. Based on this structure, we develop BLADE, a scalable boundary-link algorithm that avoids dense Katz-kernel maintenance by using score-based direct-target batches and warm-started Katz updates. Experiments on synthetic and real-world networks show that BLADE reaches the desired top-k representation using far fewer edits than natural baselines, while scaling to large real-world graphs and preserving the original ranking structure.

Tema degli esploratori: governance digitale e beni comuni (retro-catalogo arXiv: annunci del 2026-09-04 in cs.SI).
Categorie arXiv: Social and Information Networks (cs.SI).
Pagina del lavoro: https://arxiv.org/abs/2609.03899 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T01:27:46.959Z dalla pagina https://arxiv.org/catchup/cs.SI/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).