The paper you link to in the question is paywalled for me, so this answer may not be specific enough, but we'll make do.
Fundamentally, AUC is about measuring a classifier's robustness. The intuition behind the measure is that if we have classifier that outputs a score for an example, rather than a class label alone, we can choose to interpret that score in ways that trade detection rate (true positives) for false positive rate.
As a very simple example, imagine that we have a classifier that outputs a probability that an example pair is a link. By default we might chose to interpret this a probability of more than 0.5 as a link being present. Suppose this produces a certain true positive and false positive rate. Now let's change our mind. It's suddenly very important that we detect all the links, even if we get a lot of false positives. We choose to interpret any probability value > 0 as being a link. Our true positive rate will spike, but so will our false positive rate. Finally, if we care only about minimizing the prediction of fake links, we could chose to interpret only probability values that are >0.99 as being links. Our true positive rate will go way down, but our false positive rate will too.
AUC quantifies how rapidly the false positive rate increases as we increase the true positive rate by changing our interpretation of the scores the classifier outputs. Better classifiers will generally be able to increase their true positive rates quickly without introducing many false positives, while worse classifiers will not. An AUC of 1.0 indicates that we can achieve 100% true positive rate without increasing the false positive rate at all. An AUC of 0.0 indicates that increasing the true positive rate by 1% will always result in an increase of 1% in the false positive rate (i.e. the classifier is essentially just as good as a random guess without looking at the input).
In your link prediction problem, we cannot directly measure the false positive rate. However, if we treat all non-links as negative examples when we compute this measure, a classifier with a higher AUC will is one that can more rapidly separate positive examples from non-positive ones as you increase your sensitivity. Even though we aren't sure which examples are false positives and which are unseen links, a classifier with a high AUC is one where we would be more likely to trust that the non-links it labels as links are actually links we can't see.