Link prediction in social networks: a physics-inspired guide

The problem, stated precisely

Link prediction asks: given a snapshot of a network, which edges that do not yet exist are most likely to appear next — or which observed edges are missing from the data? The first framing is temporal (predicting evolution), the second is a completion problem on incomplete observations. They are not the same task, and conflating them is the most common methodological error in the literature.

It matters because the network is usually the only signal available. Friend and follower recommendation, collaboration and co-authorship discovery, fraud-ring detection, protein interaction prediction and knowledge-graph completion are all the same mathematical problem wearing different clothes.

Similarity indices: the baselines that are hard to beat

Local similarity measures score a candidate pair from its neighbourhood alone. Common Neighbours counts shared contacts; Jaccard normalises that by the union; Adamic–Adar and Resource Allocation down-weight hubs so that a shared contact with fifty thousand connections counts for less than a shared contact with five; Preferential Attachment scores by the product of degrees, encoding the rich-get-richer effect.

Global measures such as Katz, SimRank and rooted PageRank propagate along all paths and often score better, at a cost that grows badly with network size. The unglamorous finding, replicated many times over, is that Adamic–Adar and Resource Allocation are strong, near-free baselines. Any new method — mine included — must be reported against them or the result is not interpretable.

A physics-inspired model: gravitation between nodes

My doctoral work took a different starting point. If nodes carry a notion of mass and sit at some distance in a latent space, then the tendency to form a link can be modelled in the shape of Newton's gravitational law: proportional to the product of the masses, inversely proportional to the square of the distance.

Degree, or a centrality measure, supplies mass; shortest-path length or a latent-space embedding distance supplies separation. What the formulation buys is that two very different intuitions — popularity and proximity — combine in a single expression with interpretable parameters, rather than being bolted together as an ad-hoc weighted sum. It generalises preferential attachment and distance-decay behaviour as limiting cases.

Published as Newton's Gravitational Law for Link Prediction in Social Networks (Complex Networks & Their Applications VI, Springer, 2018) and extended in How to Predict Social Relationships — a Physics-Inspired Approach to Link Prediction (Physica A, 2019).

Graph neural networks and where learning helps

Learned approaches replace a hand-designed score with a representation. Matrix factorisation and shallow embeddings such as node2vec map nodes to vectors and score pairs by proximity in that space. Graph neural networks aggregate features across neighbourhoods, and subgraph-based methods classify the local structure around a candidate pair directly, which is usually the strongest family on standard benchmarks.

The trade-off is not accuracy versus elegance, it is accuracy versus cost and explainability. A GNN needs training data, hyperparameter search and retraining as the graph drifts, and its output is difficult to justify to a human. A similarity index computes in microseconds and can be explained in one sentence. On sparse graphs with no node attributes, the learned model's advantage often collapses to within noise of Resource Allocation.

Evaluation: where most published results quietly break

Link prediction is extremely imbalanced — candidate non-edges outnumber true future edges by orders of magnitude — so accuracy is meaningless and AUC is over-optimistic, because a random negative sample is trivially easy to reject. Report precision@k and average precision on a realistic candidate set, and state how negatives were sampled.

Split by time, never at random, when the question is temporal: a random edge holdout leaks future structure into the training graph and inflates every method uniformly. Report against local-index baselines, and check performance stratified by node degree — many methods score well overall while failing completely on the low-degree nodes that a recommender most needs to serve.

Generating networks to test against: NetSim

Benchmark graphs are few and their idiosyncrasies get baked into methods. To evaluate systematically you need synthetic networks with controllable degree distribution, clustering and community structure, which is why I built NetSim, a framework for complex network generation published in Procedia Computer Science (2018).

Synthetic generation lets you ask which structural property a predictor actually depends on — sweep clustering coefficient or community strength and watch the score move. That is a causal statement about the method, which no amount of benchmark leaderboard placement gives you.

What is link prediction?

Link prediction is the task of estimating which currently absent edges in a network are most likely to exist or to form in the future, using the observed structure of the graph and any available node attributes. It underpins friend recommendation, collaboration discovery, fraud-ring detection and knowledge-graph completion.

Which link prediction method should I start with?

Start with Adamic–Adar and Resource Allocation. They are near-free to compute, require no training, and are strong enough that they remain the standard baselines. Only move to embeddings or graph neural networks once you have measured how much headroom is actually left above them on your own graph.

How does a gravitational-law model apply to social networks?

Node degree or centrality plays the role of mass and shortest-path or latent-space distance plays the role of separation, so link likelihood scales with the product of the masses and inversely with the square of the distance. This combines popularity and proximity in one interpretable expression, and generalises preferential attachment and distance decay as limiting cases.

Are graph neural networks better than similarity indices for link prediction?

Usually on attributed benchmark graphs, and often not by much on sparse graphs with no node features. GNNs cost training, tuning, retraining under drift and explainability, so the right comparison is accuracy gain over a local index against that total cost.

Why is AUC a poor metric for link prediction?

Because the candidate set is extremely imbalanced. Randomly sampled non-edges are trivially easy to reject, so AUC looks high for almost any method. Precision@k and average precision on a realistic candidate set, with a time-based split and degree-stratified reporting, are far more informative.