EUVIMEDEUVIMED entdecken
Crossref

Quickcent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networks

Francisco Plana, Andrés Abeliuk, Jorge Pérez

Computing · 2024-08 · 106 (8) · 2675-2705

DOI: 10.1007/s00607-024-01303-z ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computing, online erschienen am 08.06.2024. Verfasst von Francisco Plana und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 72 Literaturangaben. Gefördert von: Agencia Nacional de Investigación y Desarrollo, National Center for Artificial Intelligence CENIA.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present a simple and quick method to approximate network centrality indexes. Our approach, called QuickCent, is inspired by so-called fast and frugal heuristics, which are heuristics initially proposed to model some human decision and inference processes. The centrality index that we estimate is the harmonic centrality, which is a measure based on shortest-path distances, so infeasible to compute on large networks. We compare QuickCent with known machine learning algorithms on synthetic network datasets, and some empirical networks. Our experiments show that QuickCent can make estimates that are competitive in accuracy with the best alternative methods tested, either on synthetic scale-free networks or empirical networks. QuickCent has the feature of achieving low error variance estimates, even with a small training set. Moreover, QuickCent is comparable in efficiency—accuracy and time cost—to more complex methods. We discuss and provide some insight into how QuickCent exploits the fact that in some networks, such as those generated by preferential attachment, local density measures such as the in-degree, can be a good proxy for the size of the network region to which a node has access, opening up the possibility of approximating expensive indices based on size such as the harmonic centrality. This same fact may explain some evidence we provide that QuickCent would have a superior performance on empirical information networks, such as citations or the internet. Our initial results show that simple heuristics are a promising line of research in the context of network measure estimations.

Förderung

  • Agencia Nacional de Investigación y Desarrollo
  • National Center for Artificial Intelligence CENIA

Zitieren

APA

Plana, F., Abeliuk, A., & Pérez, J. (2024). Quickcent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networks. Computing, 106(8), 2675-2705. https://doi.org/10.1007/s00607-024-01303-z

Vancouver

Plana F, Abeliuk A, Pérez J. Quickcent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networks. Computing. 2024;106(8):2675-2705. doi:10.1007/s00607-024-01303-z

BibTeX
@article{Plana2024,
  author = {Plana, Francisco and Abeliuk, Andrés and Pérez, Jorge},
  title = {Quickcent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networks},
  journal = {Computing},
  year = {2024},
  volume = {106},
  number = {8},
  pages = {2675--2705},
  doi = {10.1007/s00607-024-01303-z}
}
Kostenlos starten →