{"paper":{"title":"Fair Top-k Katz Centrality via Graph Design","arxiv_id":"2609.03899","primary_cat":"cs.SI","submitted_at":"2026-09-03T14:18:31+00:00","version_compiled":"v1"},"notice":"Every quoted sentence is the authors' text from the arXiv listing abstract. Labels and probabilities are the outputs of classifier-1.13.0 on the question bank abstract-p1-20260923, exactly as returned. No sentence in this record was written by a language model.","schema":"pith.compiled-record/v0","status":"compiled","abstract":{"source":"arXiv listing abstract v1","sentences":[{"i":0,"p":0.54,"id":"s0","own":false,"role":"gap","text":"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.","hedge":{"p":1.0,"label":"asserted"},"own_p":0.06,"main_claim_p":0.04,"quantitative":false,"quantitative_p":0.29,"role_probabilities":{"gap":0.54,"method":0.0,"result":0.0,"background":0.46,"limitation":0.0,"future_work":0.0,"contribution":0.0,"interpretation":0.0}},{"i":1,"p":0.86,"id":"s1","own":true,"role":"contribution","text":"We study this top-k setting for Katz centrality.","hedge":{"p":0.82,"label":"asserted"},"own_p":0.5,"main_claim_p":0.02,"quantitative":false,"quantitative_p":0.04,"role_probabilities":{"gap":0.02,"method":0.0,"result":0.0,"background":0.12,"limitation":0.0,"future_work":0.0,"contribution":0.86,"interpretation":0.0}},{"i":2,"p":0.57,"id":"s2","own":false,"role":"contribution","text":"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.","hedge":{"p":0.98,"label":"asserted"},"own_p":0.31,"main_claim_p":0.06,"quantitative":false,"quantitative_p":0.1,"role_probabilities":{"gap":0.01,"method":0.11,"result":0.0,"background":0.31,"limitation":0.0,"future_work":0.0,"contribution":0.57,"interpretation":0.0}},{"i":3,"p":0.73,"id":"s3","own":true,"role":"result","text":"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.","hedge":{"p":1.0,"label":"asserted"},"own_p":0.96,"main_claim_p":0.36,"quantitative":false,"quantitative_p":0.37,"role_probabilities":{"gap":0.0,"method":0.0,"result":0.73,"background":0.0,"limitation":0.07,"future_work":0.0,"contribution":0.2,"interpretation":0.0}},{"i":4,"p":0.72,"id":"s4","own":true,"role":"result","text":"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.","hedge":{"p":1.0,"label":"asserted"},"own_p":0.96,"main_claim_p":0.07,"quantitative":false,"quantitative_p":0.09,"role_probabilities":{"gap":0.0,"method":0.07,"result":0.72,"background":0.0,"limitation":0.0,"future_work":0.0,"contribution":0.16,"interpretation":0.05}},{"i":5,"p":0.94,"id":"s5","own":true,"role":"method","text":"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.","hedge":{"p":1.0,"label":"asserted"},"own_p":0.95,"main_claim_p":0.08,"quantitative":false,"quantitative_p":0.05,"role_probabilities":{"gap":0.0,"method":0.94,"result":0.0,"background":0.0,"limitation":0.0,"future_work":0.0,"contribution":0.06,"interpretation":0.0}},{"i":6,"p":1.0,"id":"s6","own":true,"role":"result","text":"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.","hedge":{"p":1.0,"label":"asserted"},"own_p":0.97,"main_claim_p":0.55,"quantitative":true,"quantitative_p":0.86,"role_probabilities":{"gap":0.0,"method":0.0,"result":1.0,"background":0.0,"limitation":0.0,"future_work":0.0,"contribution":0.0,"interpretation":0.0}}]},"compiled":{"main_claim":{"p":0.95,"text":"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.","location":"abstract s6","hedge_strength":{"p":1.0,"label":"asserted"}},"provenance":{"route":{"via":"TypeSafe API","model":"classifier-1.13.0","endpoint":"https://api.typesafe.ai/v1/systemone","provider":"TypeSafe"},"packing":"one request per paper","requests":1,"input_tokens":5729,"cost_usd_reported":0.0},"compiled_at":"2026-09-23","bank_version":"abstract-p1-20260923","model_version":"classifier-1.13.0","abstract_states":{"claims_first":0.1,"states_limitation":0.86,"human_participants":0.03,"controlled_comparison":0.74,"randomized_assignment":0.01,"states_quantitative_result":0.2,"compares_with_prior_results":0.9,"mentions_code_or_data_availability":0.03},"evidential_basis":{"p":0.52,"value":"observation or experiment","probabilities":{"argument":0.0,"literature":0.0,"proof_or_derivation":0.3,"analysis_of_existing_data":0.0,"observation_or_experiment":0.52,"simulation_or_computation":0.18}},"contribution_type":{"p":0.99,"value":"method or tool","probabilities":{"review":0.0,"method_or_tool":0.99,"empirical_study":0.0,"simulation_study":0.0,"theoretical_result":0.01,"dataset_or_benchmark":0.0,"position_or_commentary":0.0}},"contribution_statement":{"p":0.8,"text":"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.","location":"abstract s5"}},"coverage":{"tier":"abstract","levels_run":["P abstract"],"not_examined":["full text","figures and tables","references and citing sentences","relations to other papers"],"sources_read":["arXiv listing abstract v1"],"levels_not_run":["S sections","T body sentences","C citations","R cross-paper relations"],"sentences_examined":7,"sentences_in_abstract":7},"measured_accuracy":{"url":"https://pith.science/accuracy","measured_on":"2026-10-02","method":"two independent model families labelled a fresh random sample blind; the figure is how often the published label matches their consensus","sentence_role_agreement":0.92,"main_claim_agreement":0.908,"typed_citation_agreement":0.933,"typed_citation_agreement_95_interval":[0.917,0.945],"review_comments_accurate":0.758,"review_comments_accurate_95_interval":[0.684,0.82],"review_caught_admitted_error_found_or_related":0.448}}