EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fast algorithms to improve fair information access in networks

Dennis Robert Windham, Caroline J. Wendt, Alex Crane, Madelyn J. Warr, Freda Shi, Sorelle A. Friedler, Blair D. Sullivan, Aaron Clauset

PLOS Complex Systems · 04.03.2026 · 3 (3) · e0000094

DOI: 10.1371/journal.pcsy.0000094 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS Complex Systems, online erschienen am 04.03.2026. Verfasst von Dennis Robert Windham und 7 weiteren Autor:innen. Die Arbeit nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the problem of selecting k seed nodes in a network to maximize the minimum probability of activation under an independent cascade beginning at these seeds. The motivation is to promote fairness by ensuring that even the least advantaged members of the network have good access to information. Our problem can be viewed as a variant of the classic influence maximization objective, but it appears somewhat more difficult to solve: only heuristics are known. Moreover, the scalability of these methods is sharply constrained by the need to repeatedly estimate access probabilities. We design and evaluate a suite of 10 new scalable algorithms which crucially do not require probability estimation. To facilitate comparison with the state-of-the-art, we make three more contributions which may be of broader interest. We introduce a principled method of selecting a pairwise information transmission parameter used in experimental evaluations, as well as a new performance metric which allows for comparison of algorithms across a range of values for the parameter k . Finally, we provide a new benchmark corpus of 174 networks drawn from 6 domains. Our algorithms retain most of the performance of the state-of-the-art while reducing running time by orders of magnitude. Specifically, a meta-learner approach is on average only 20% less effective than the state-of-the-art on held-out data, but about 75-130 times faster. Further, the meta-learner’s performance exceeds the state-of-the-art on about 20% of networks, and the magnitude of its running time advantage is maintained on much larger networks.

Förderung

  • National Science Foundation

Zitieren

APA

Windham, D. R., Wendt, C. J., Crane, A., Warr, M. J., Shi, F., Friedler, S. A., Sullivan, B. D., & Clauset, A. (2026). Fast algorithms to improve fair information access in networks. PLOS Complex Systems, 3(3), e0000094. https://doi.org/10.1371/journal.pcsy.0000094

Vancouver

Windham DR, Wendt CJ, Crane A, Warr MJ, Shi F, Friedler SA, et al. Fast algorithms to improve fair information access in networks. PLOS Complex Systems. 2026;3(3):e0000094. doi:10.1371/journal.pcsy.0000094

BibTeX
@article{Windham2026,
  author = {Windham, Dennis Robert and Wendt, Caroline J. and Crane, Alex and Warr, Madelyn J. and Shi, Freda and Friedler, Sorelle A. and Sullivan, Blair D. and Clauset, Aaron},
  title = {Fast algorithms to improve fair information access in networks},
  journal = {PLOS Complex Systems},
  year = {2026},
  volume = {3},
  number = {3},
  pages = {e0000094},
  doi = {10.1371/journal.pcsy.0000094}
}
Kostenlos starten →