Centrality is a relevant topic in the field of network research, due to its various theoretical and practical implications. In general, all centrality metrics aim at measuring the importance of nodes (according to some definition of importance), and such importance scores are used to rank the nodes in the network, therefore the rank improvement is a strictly related topic. In a given network, the rank improvement is achieved by establishing new links, therefore the question shifts to which and how many links should be collected to get a desired rank. This problem, also known as link-building has been shown to be NP-hard, and most heuristics developed failed in obtaining good performance with acceptable computational complexity. In this article, we present LB-GDM, a novel approach that leverages Geometric Deep Learning to tackle the link-building problem. To validate our proposal, 31 real-world networks were considered; tests show that LB-GDM performs significantly better than the state-of-the-art heuristics, while having a comparable or even lower computational complexity, which allows it to scale well even to large networks.

Efficient Node PageRank Improvement via Link-building using Geometric Deep Learning

Carchiolo V.;Grassia M.;Longheu A.;Malgeri M.;Mangioni G.
2023-01-01

Abstract

Centrality is a relevant topic in the field of network research, due to its various theoretical and practical implications. In general, all centrality metrics aim at measuring the importance of nodes (according to some definition of importance), and such importance scores are used to rank the nodes in the network, therefore the rank improvement is a strictly related topic. In a given network, the rank improvement is achieved by establishing new links, therefore the question shifts to which and how many links should be collected to get a desired rank. This problem, also known as link-building has been shown to be NP-hard, and most heuristics developed failed in obtaining good performance with acceptable computational complexity. In this article, we present LB-GDM, a novel approach that leverages Geometric Deep Learning to tackle the link-building problem. To validate our proposal, 31 real-world networks were considered; tests show that LB-GDM performs significantly better than the state-of-the-art heuristics, while having a comparable or even lower computational complexity, which allows it to scale well even to large networks.
2023
best attachment
complex networks
Graph Attention Network
Link-building
Machine Learning
PageRank
ranking
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/558203
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
social impact