  The hyperlink prediction task, that of proposing new links between webpages,
can be used to improve search engines, expand the visibility of web pages, and
increase the connectivity and navigability of the web. Hyperlink prediction is
typically performed on webgraphs composed by thousands or millions of vertices,
where on average each webpage contains less than fifty links. Algorithms
processing graphs so large and sparse require to be both scalable and precise,
a challenging combination. Similarity-based algorithms are among the most
scalable solutions within the link prediction field, due to their parallel
nature and computational simplicity. These algorithms independently explore the
nearby topological features of every missing link from the graph in order to
determine its likelihood. Unfortunately, the precision of similarity-based
algorithms is limited, which has prevented their broad application so far. In
this work we explore the performance of similarity-based algorithms for the
particular problem of hyperlink prediction on large webgraphs, and propose a
novel method which assumes the existence of hierarchical properties. We
evaluate this new approach on several webgraphs and compare its performance
with that of the current best similarity-based algorithms. Its remarkable
performance leads us to argue on the applicability of the proposal, identifying
several use cases of hyperlink prediction. We also describes the approach we
took for the computation of large-scale graphs from the perspective of
high-performance computing, providing details on the implementation and
parallelization of code.
