Algorithm created to estimate node centrality in a network

ByPaula Silva
July 2024.- An algorithm to estimate node centrality in a network, which is competitive in accuracy with machine learning methods, is the innovative proposal that researchers Francisco Plana, PhD in Computing from the Universidad de Chile, Andrés Abeliuk, academic at DCC U. Chile and IMFD collaborating researcher, and Jorge Pérez, former IMFD researcher and co-founder of cero.ai, present in the scientific paper “Quickcent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networks”.
This work was recently published in Computing, a scientific journal published by Springer, focused on computer science and numerical computation.

Regarding this research, Andrés Abeliuk explains: “Centrality indices identify key nodes in a network, such as people or web pages, that are influential or prominent. Centrality assesses how centrally a node is located based on its proximity to other nodes. For example, a node with high centrality can communicate effectively with many other nodes in the network, facilitating the rapid spread of information and strengthening the network’s cohesion”.

Andrés Abeliuk and Francisco Plana.

Calculating these indices in networks is computationally expensive and does not scale efficiently, which limits its application in large networks. The academic comments that the work developed together with Francisco Plana and Jorge Pérez, “proposes a heuristic based on local indicators, such as a node’s popularity, to estimate node centrality in the network. This heuristic achieves great accuracy in networks that show an uneven distribution where a few nodes are highly connected, taking advantage of the correlation between local centrality and global centrality in a network”.

In addition, an algorithm is proposed to estimate node centrality in a network that is competitive in accuracy with machine learning methods, with the advantage of being efficient in terms of time and computational cost. “This approach suggests that simple heuristics can be effective for estimating measures in complex networks. Particularly in social networks, where the more connected a node is, the more likely it is to receive new links”, concludes Andrés Abeliuk.

Source: DCC U. Chile