Ordering nodes by rank is a benchmark used in several contexts,from recommendation-based trust networks to e-commerce,search engines and websites ranking. In these scenarios,the node rank depends on the set of links the node establishes,hence it becomes important to choose appropriately the nodes to connect to. The problem of finding which nodes to connect to in order to achieve the best possible rank is known as the best attachment problem. Since in the general case the best attachment problem is NP-hard,in this work we propose heuristics that produce near-optimal results while being computable in polynomial time; simulations on different networks show that our proposals preserve both effectiveness and feasibility in obtaining the best rank.

Dealing with the best attachment problem via heuristics

CARCHIOLO, Vincenza;MALGERI, Michele Giuseppe;MANGIONI, GIUSEPPE
2017

Abstract

Ordering nodes by rank is a benchmark used in several contexts,from recommendation-based trust networks to e-commerce,search engines and websites ranking. In these scenarios,the node rank depends on the set of links the node establishes,hence it becomes important to choose appropriately the nodes to connect to. The problem of finding which nodes to connect to in order to achieve the best possible rank is known as the best attachment problem. Since in the general case the best attachment problem is NP-hard,in this work we propose heuristics that produce near-optimal results while being computable in polynomial time; simulations on different networks show that our proposals preserve both effectiveness and feasibility in obtaining the best rank.
978-3-319-48828-8
Trusting; Complex networks
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/61719
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact