<figure><img src="image_1.png" /></figure>

HAL
open science

# Network Backbone Extraction using Link Prediction

Ali Yassin, Hocine Cherifi, Hamida Seba, Olivier Togni

► To cite this version:

Ali Yassin, Hocine Cherifi, Hamida Seba, Olivier Togni. Network Backbone Extraction using Link Prediction. 7th IEEE Workshop on Complexity in Engineering (COMPENG 2024), Jul 2024, Florence, Italy. 10.1109/COMPENG60905.2024.10741362. hal-05291577

HAL Id: hal-05291577

https://hal.science/hal-05291577v1

Submitted on 1 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Network Backbone Extraction using Link Prediction

1st Ali Yassin

Laboratoire d'Informatique de Bourgogne
University of Burgundy
Dijon, France
ali.yassin@u-bourgogne.fr

3rd Hamida Seba

Laboratoire d'InfoRmatique en Image et Systèmes d'information
University of Lyon
Lyon, France
hamida.seba@univ-lyon1.fr

2nd Hocine Cherifi

Laboratoire Interdisciplinaire Carnot de Bourgogne
University of Burgundy
Dijon, France
hocine.cherifi@u-bourgogne.fr

4th Olivier Togni

Laboratoire d'Informatique de Bourgogne
University of Burgundy
Dijon, France
olivier.togni@u-bourgogne.fr

**Abstract**—Backbone extraction methods aim to reduce the size of a network while preserving its essential structural properties. They can be broadly categorized into structural and statistical approaches. Structural methods aim at preserving the network's topology, while statistical methods aim to retain edges that deviate significantly from a null hypothesis model.

This study introduces a novel approach to backbone extraction based on link prediction. Indeed, both techniques aim at predicting the likelihood of a link between two nodes in a network. For this task, link prediction methods use various similarity measures or machine learning techniques. The proposed approach Leverage link prediction scores to filter links in a network. Let's consider similarity-based link prediction methods. The proposed framework proceeds as follows: 1) Remove an edge from the network and compute its similarity score. Repeat this process on all the network edges. 2) Sort the edges based on their similarity scores. 3) Extract the backbone corresponding to the top X fraction of edges with the highest scores and the nodes attached and the bottom Y fraction of edges with the lowest scores and the nodes attached. Keeping the top X fraction of edges preserves the predictable edges based on the similarity assumption, aligning with the principles of structural backbone extraction methods. In contrast, retaining the bottom Y fraction of edges captures the unpredictable edges that deviate from the similarity assumption, similar to the statistical backbone extraction methods that retain edges deviating from a null hypothesis.

We extract the backbone of the American Elementary School social network (339 nodes, 16,546 edges) using a statistical method (disparity filter), a structural method (high salience skeleton), and the proposed approach (using the common neighbor similarity function). The disparity filter preserves ≈ 10% of the edges for a typical statistical significance level α = 0.05. The high salience skeleton preserves ≈ 7%. To compare our approach, we extract the backbone, keeping 10% of the edges (90% predictable and 10% unpredictable edges). While the disparity and high salience skeleton maintain all nodes, the former consists of four components, whereas the latter has a single component. In contrast, our proposed method isolates approximately 8% of the nodes for this fraction of edges, yet all its nodes remain within a single component.

This material is based upon work supported by the Agence Nationale de
Recherche under grant ANR-20-CE23-0002.

Fig 1 illustrates the extracted backbones. Observing the extracted edges, we notice that the disparity backbone and high salience skeleton predominantly link nodes within the classes of the same grade. Indeed, these edges form ≈ 91% and 80% of the backbones, respectively. On the other hand, we notice that the top predictable ones predominantly link nodes within and between classes of the same grade. Conversely, the unpredictable edges primarily connect nodes from distinct grades. These cross-grade interactions pose challenges for prediction, as they lack substantial common neighbors. Ultimately, examining the combined backbone, we observe that roughly half of the edges connect nodes within the same class, while the other half bridge nodes across different classes at ≈ 50%.

This hybrid approach leverages the strengths of both structural and statistical backbone extraction methods, providing a comprehensive and nuanced representation of the network's essential structure and significant deviations. In our forthcoming research, we aim to expand our exploration of link prediction methods beyond similarity-based approaches.

<figure><img src="image_3.png" /><figcaption>Fig. 1. The original network, disparity, high salience skeleton, predictable and unpredictable backbone components, and the proposed approach's backbone. Colors denote different grades, and shades represent classes within grades.</figcaption></figure>

**Index Terms**—Backbone Extraction, Link Prediction