Physics-inspired link prediction for social networks, based on Newton's law of universal gravitation: node centrality plays the role of mass, and the inverse of node-pair similarity plays the role of distance.
Score(vi, vj) ∝ P(vi) · P(vj) / D(vi, vj)²
where P is a vertex centrality (degree, closeness or betweenness) and D is
a dissimilarity — the shortest path length, or the inverse of a similarity
score (Katz, AdamicAdar, Rooted PageRank, Matrix Forest Index, …). The
attraction "force" between two nodes is used as the likelihood that a link
forms between them, coupling popularity with similarity in a single
predictor.
This is a reference implementation of the method introduced in:
Akanda Wahid-Ul-Ashraf, Marcin Budka, Katarzyna Musial. How to predict social relationships — Physics-inspired approach to link prediction. Physica A: Statistical Mechanics and its Applications 523 (2019) 1110–1129. DOI: 10.1016/j.physa.2019.04.246
Earlier version: Wahid-Ul-Ashraf, Budka, Musial-Gabrys. Newton's gravitational law for link prediction in social networks. COMPLEX NETWORKS 2017. DOI: 10.1007/978-3-319-72150-7_8
Companion application: Wahid-Ul-Ashraf, Budka, Musial. Simulation and Augmentation of Social Networks for Building Deep Learning Models. arXiv:1905.09087 — uses the gravity similarity to augment graphs fed to GCNs (see examples/gcn_augmentation_demo.py).
This work comes from the author's PhD research at Bournemouth University, supervised by the papers' co-authors Marcin Budka and Katarzyna Musial — see Acknowledgements.
Everything below was produced with this repository (full tables in benchmarks/ and docs/USAGE.md):
- First public implementation. As of 2026, no other implementation of the method existed — on GitHub, PyPI, CRAN, or in any link-prediction library. This repository is the reference implementation.
- The method holds up on data that did not exist when the papers were
written. On TGB's tgbl-flight benchmark (16.7k airports, 2019–2022,
138.5M candidate pairs per predictor, evaluated on a laptop GPU),
DC1*DC2*RPR0.25^2is the best predictor at 31.7× the random baseline, beating standalone RPR (22.4×). Same pattern on a modern email network (10.6×) and the karate club (6.6×). - Even the papers' negative results replicate: the Katz combination fails to beat standalone Katz on every new dataset — exactly as Section 5.1.1 of the Physica A paper reported. Selective replication of this kind is stronger evidence than uniform improvement would be.
- The GCN-augmentation companion paper works on real data: on Cora, the RPR-augmented graph representative significantly outperforms the original GCN (0.8089 vs 0.8004, paired t(9) = 2.88, p < 0.05), and the paper's proposed validation-based threshold selection recovers the optimal configuration automatically.
- The paper's conjecture about the distance exponent is confirmed: the
optimal order is a per-network property, learnable from data. The
Physica A paper adopted n = 2 in
Score = DC·DC·sⁿby deliberate physical analogy and explicitly anticipated (§6) that other orders might predict better. A six-dataset study bears that out: tuned exponents outperform the n = 2 default on every dataset tested, with optima from n ≈ 1–1.5 (hub-dominated, weakly clustered networks: bitcoin-otc, CollegeMsg) to n ≈ 3.5–5.5 (strongly clustered ones: email, flight, karate) and gains of up to +20–81% AUC-PR. The tuned combination beats both family endpoints — pure popularity (n = 0 is exactly Preferential Attachment) and pure similarity — in 10 of 12 cases. Optimal n correlates with the clustering coefficient (Spearman ρ ≈ 0.89 for MFI): the exponent is precisely the popularity-vs-similarity balance, and network metrics can guide its selection instead of brute force — on these data, clustering picks the correct search regime 12/12 times, and a regime-restricted validation search keeps 100% of the brute-force gain at half the cost. Study and caveats: benchmarks/gravity-exponent-study.md.
From a clone of this repository:
pip install -e . # development installor build a wheel and install that anywhere:
pip install build
python -m build # produces dist/akanda_method-<version>-py3-none-any.whl
pip install dist/akanda_method-*.whlRequires Python ≥ 3.10; depends on networkx, numpy, scikit-learn.
import networkx as nx
from akanda_method import akanda_score, rank_links
G = nx.karate_club_graph()
# Gravitational score for all unlinked pairs:
# degree centrality as mass, inverse Matrix Forest Index as distance
scores = akanda_score(G, centrality="degree", similarity="mfi")
# Top-10 predicted links
for (u, v), s in rank_links(scores)[:10]:
print(u, v, s)Evaluating a predictor with a temporal train/test split and AUC-PR (the paper's protocol):
from akanda_method import evaluate, temporal_split
# timestamped_edges: any iterable of (u, v, timestamp) tuples
train_G, test_edges = temporal_split(timestamped_edges, ratio=0.5)
result = evaluate(train_G, test_edges, centrality="degree", similarity="rpr", alpha=0.25)
print(result.auc_pr, result.random_baseline)Full usage guide — installation (CPU & GPU), every predictor and parameter, evaluation protocols, and all benchmark results: docs/USAGE.md. See docs/METHOD.md for the precise formulas implemented and examples/ for runnable walkthroughs.
On TGB's modern tgbl-flight benchmark (16.7k airports, 1M training
routes, 2019–2022; 138.5M candidate pairs scored per predictor on an RTX
3070 in under a minute each), the gravitational combination DC1*DC2*RPR0.25^2
is the best predictor at 31.7× the random baseline, improving on standalone
RPR (22.4×) — see benchmarks/tgbl-flight.md and
examples/tgbl_flight_demo.py.
evaluate_matrix is a fully vectorized drop-in for evaluate — identical
protocol and AUC-PR (to ~1e-9 relative in float64), but computed with dense
matrix algebra instead of per-pair dicts, optionally on a CUDA GPU via
CuPy:
from akanda_method import evaluate_matrix
result = evaluate_matrix(
train_G, test_edges,
centrality="degree", similarity="rpr", alpha=0.25,
dtype="float32", # "float64" (default) or "float32" (halves memory)
device="auto", # "auto" (GPU if CuPy is available), "cpu", or "gpu"
)Install the GPU extra with pip install akanda-method[gpu] (pulls in
cupy-cuda12x; needs an NVIDIA GPU with CUDA 12). If your system has no CUDA
toolkit — or an older CUDA ≤ 11 one — install the self-contained
nvidia-*-cu12 runtime wheels as described in
docs/USAGE.md. Notes:
result.scoresisNonein matrix mode — the per-pair dict would be O(N²); only the aggregate metrics are returned.- All heavy work (adjacency, similarity matrix, BFS distance matrix, score matrix) stays on the chosen device; only the flattened candidate vectors come back to the host for scikit-learn's AUC-PR.
- Matrices are dense, so memory is the bound: peak usage is roughly
5 · N² · itemsizebytes. Practical guidance: up to N ≈ 25k nodes in float32 on an 8 GB GPU (e.g. the 18k-nodetgbl-flightgraph in examples/tgbl_flight_demo.py fits comfortably); beyond that, subsample or use the dict API on selected pairs.
- Centralities (mass): degree (DC), closeness (CC), betweenness (BC)
- Similarities (inverse → distance): Common Neighbours, Jaccard, AdamicAdar, Preferential Attachment, Katz, Rooted PageRank, Average Commute Time (plain and normalised), Laplacian pseudoinverse kernel, Local Path Index, Leicht–Holme–Newman Global Index, Matrix Forest Index, shortest path
- Model: the gravitational combination (Eq. 2 of the paper) for any centrality × similarity pair — 50+ predictors
- Evaluation: temporal splitting, AUC of the Precision–Recall curve, random-predictor baseline
- GCN augmentation (the arXiv:1905.09087 companion paper): Katz-, RPR- and Graph-Gravity-based graph representatives for graph convolutional networks, with the paper's threshold preprocessing and its future directions (validation-based threshold selection, depth sweeps) — examples/gcn_augmentation_demo.py, examples/gcn_future_directions.py
- Studies: the six-dataset distance-exponent study answering the Physica A paper's §6 open question — examples/gravity_exponent_study.py
- Papers: PDF copies of all three papers (the CC-BY published Physica A article, the COMPLEX NETWORKS 2017 accepted manuscript, and the arXiv companion paper) in docs/paper/
This is a re-implementation from the paper text — the original experiment code is lost. Expect the paper's qualitative findings to reproduce (gravitational combinations outperforming standalone similarity measures, and the strong RPR+DC / MFI+DC / DC+shortest-path families), but not the exact AUC values of Tables 2–13: the precise temporal split boundaries, multi-edge handling, dataset snapshots, and the AUC-PR estimator (R's PRROC vs. scikit-learn) all differ in unrecoverable details. See docs/METHOD.md §7 for the full assessment. Compare re-runs at the level of rankings and improvement patterns, not decimal-exact AUCs.
As of 2026 this is, to the best of our knowledge, the first public implementation of the method. It should not be confused with other "gravity"-themed link prediction lines, which are unrelated methods:
- Gravity-Inspired Graph Autoencoders (Salha et al., CIKM 2019) and descendants — a gravity-inspired decoder over learned GNN embeddings;
- Bastami et al., A gravitation-based link prediction approach in social networks (Swarm Evo. Comp., 2019) — an independent heuristic using community information;
- econometric "gravity models" of trade networks (GDP × distance).
The Akanda method instead applies Newton's law directly to network-topological quantities: vertex centrality as mass, inverse similarity as distance.
The Akanda method and the papers underpinning this repository are the product of the author's PhD research, funded by Bournemouth University and carried out there under the supervision of Marcin Budka and Katarzyna Musial, who are co-authors of all three papers. The method, its evaluation methodology, and the ideas explored in this repository's experiments build directly on that joint work, their guidance, and the university's support.
If you use this code, please cite the Physica A paper above.
MIT — see LICENSE.