An emerging problem in network analysis is ranking network nodes based on their relevance to metadata groups that share attributes of interest. The most common example lays on the context of recommender systems or node discovery services.

In our project’s latest Publication, ‘LinkAUC: Unsupervised Evaluation of Multiple Network Node Ranks Using Link Prediction’, the FuturePulse team pinpointed the importance of evaluating ranking algorithms and parameters and selecting the ones most suited to each network. Nevertheless, as Emmanouil Krasanakis, Symeon Papadopoulos, and Yiannis Kompatsiaris mention, “large real-world networks often comprise sparsely labelled nodes that hinder supervised evaluation, whereas unsupervised measures of community quality, such as density and conductance, favor structural characteristics that may not be indicative of metadata group quality.”

In this work, our partners from CERTH-ITI, introduce LinkAUC, a ‘new unsupervised approach that evaluates network node ranks of multiple metadata groups by measuring how well they predict network edges.’

The main idea behind the authors’ approach is that, if there is little information to help evaluate node ranks, it is possible evaluate other related structural characteristics instead. To this end, the FuturePulse partners propose using node rank distributions across metadata groups, in order to derive link ranks between nodes. Most importantly, link ranks can in turn be evaluated through their ability to predict the network’s edges.

Last but not least, the FuturePulse team explains that this actually accounts for relation knowledge encapsulated in known members of metadata groups and show that it enriches density-based evaluation. Experiments on one synthetic and two real-world networks indicate that LinkAUC agrees with AUC and NDCG for comparing ranking algorithms more than other unsupervised measures.

 

 

You can read the Publication on LinkAUC here.