Rapport de PFA 

Sujet :
Implémentation des indices de
centralité pour l'identification
des acteurs influents dans un
réseau social

A l’Ecole Marocaine des Sciences de l’Ingénieur

Année : 2022-2023
Réalisé par : MarzakAmine, Hamouri Walid
Filière : Ingénierie Informatique et Réseaux (MIAGE)
Encadré par : Mme Zeryouh Meryam
 Remercîments

Nous voudrons remercier la Professeur

Zeryouh Meryam, notre encadrante pour
nous avoir permis de vivre cette magnifique
expérience au sein de ce prestigieux
établissement qu’est l’EMSI.
De plus nous la remercions pour la qualité
de son encadrement exceptionnel, pour sa
patience et aussi du temps et de l’attention
qu’elle nous a consacré durant divers
entretiens au cours de ce projet.

Enfin, nous remercions l’ensemble des

membres du service pour les conseils qu’ils
ont pu nous prodiguer pendant ce projet de
fin d’année ainsi que pour leur
bienveillance.

[Date]
2
 TABLE DE MATIÈRES 

REMERCÎMENTS.......................................................................................................2
INTRODUCTION GÉNÉRAL :................................................................................. 5
CHAPITRE 1 :.............................................................................................................. 6
CONTEXTE DU PROJET...........................................................................................6
1. CONTEXTE DU PROJET :.........................................................................................7
2. ANALYSE DU BESOIN :..........................................................................................9
CHAPITRE 2 :............................................................................................................ 11
ANALYSE................................................................................................................... 11
1. ETUDE DU PROJET :............................................................................................12
2. LES TECHNOLOGIES ADOPTÉES :.........................................................................12
3. LES OUTILS UTILISÉS :........................................................................................13
CHAPITRE 3 :............................................................................................................ 15
MISE EN ŒUVRE DU PROJET..............................................................................15
1. INTRODUCTION :.................................................................................................16
2. CRÉATION DE PROJET :.......................................................................................16
3. IMPLÉMENTATION :.............................................................................................19
CONCLUSION GÉNÉRAL :.................................................................................... 23
WEBOGRAPHIE :..................................................................................................... 24

[Date]
3
 LISTE DES FIGURES

Figure 1: Représentation du réseau............................................................................19

Figure 2 : Le degré de centralité................................................................................20
Figure 3: La centralité de proximité...........................................................................20
Figure 4 : La centralité d'intermédiarité.....................................................................21
Figure 5 : la centralité de la carte thermique..............................................................21

Introduction générale :

[Date]
4
Dans le cadre de notre formation à l’École marocaine des sciences de l’ingénieur,
l’établissement cherche à développer nos capacités en nous incitant à effectuer des
projets de fin d’année, sur une durée de plusieurs semaines. Ce projet porte sur l’étude,
la réalisation et l’implémentation des indices de centralité pour l'identification des
acteurs influents dans un réseau social. Cette technique d'analyse de réseau permet de
quantifier l'influence d'un nœud par rapport à d'autres nœuds dans le réseau.
L'utilisation des mesures de centralité sur les réseaux peut conduire à une
compréhension plus complète de la dynamique et du comportement du monde réel,
tels que l'identification des individus les plus influents dans un réseau social, ou
encore les principaux aéroports d'un réseau de transport.

Pour réaliser ce travail, nous allons utiliser la technologie Phyton, qui est un langage
de programmation orienté objet, de haut niveau, en s’aidant des bibliothèques de
graphes networkX et igraph pour nous permettre de créer, manipuler et analyser les
graphes et les réseaux, tout en mettant en application les connaissances acquises
durant le cycle préparatoire de l’EMSI.

[Date]
5
 Chapitre 1 :

Contexte du Projet 

[Date]
6
 1. Contexte du Projet :

Présentation du sujet :

Le sujet de notre rapport consiste à réaliser un programme en python pour représenter

des graphes afin de calculer les 4 différents types centralités pour ensuite afficher les
résultats sous forme de graphe. L’objectif est d’illustrer l'efficacité de la mesure basée
sur le chemin le plus court.

Définition :

La centralité de mesure est une mesure utilisée en théorie des graphes pour évaluer
l'importance d'un nœud ou d'un sommet dans un réseau. Il existe plusieurs types de
centralités de mesure, chacun évaluant l'importance du nœud ou du sommet d'une
manière différente. Voici une brève explication des quatre types les plus courants.

Centralité de proximité : La centralité de proximité évalue l'importance d'un nœud en

fonction de la distance de ce nœud à tous les autres nœuds dans le réseau. Plus un
nœud est proche des autres nœuds, plus il est considéré comme important. Cette
mesure est particulièrement utile pour évaluer l'efficacité de la communication dans un
réseau.

Centralité de degré : La centralité de degré mesure l'importance d'un nœud en fonction

du nombre de liens (ou arêtes) qu'il a avec d'autres nœuds. Un nœud ayant un grand
nombre de liens est considéré comme important, car il a une forte connectivité avec
d'autres nœuds.

[Date]
7
Centralité de betweenness : La centralité de betweenness mesure l'importance d'un
nœud en fonction de la fréquence à laquelle il apparaît sur le chemin le plus court
entre deux autres nœuds. Les nœuds qui se trouvent sur les chemins les plus courts
entre de nombreux autres nœuds sont considérés comme importants, car ils sont
essentiels pour la communication dans le réseau.

Heatmap : Une heatmap (ou carte thermique) est un outil de visualisation utilisé pour
représenter graphiquement l'importance des nœuds dans un réseau. Les nœuds sont
représentés par des cercles ou des carrés, et la couleur de chaque nœud est basée sur sa
mesure de centralité. Les nœuds les plus importants sont représentés en rouge ou en
orange, tandis que les nœuds moins importants sont représentés en vert ou en bleu.

Objectif du projet :

L'objectif de ce projet est d'implémenter différents indices de centralité en utilisant le

langage de programmation Python, afin d'identifier les acteurs influents dans un réseau
social. Le but est de proposer une méthode efficace et fiable pour détecter les nœuds
clés dans un réseau social, qui peuvent avoir un impact significatif sur les autres
membres du réseau.

Solution Proposé :

Dans ce projet, nous proposons d'implémenter les différents indices de centralité tels
que la centralité de proximité, la centralité de degré, la centralité de betweenness et de
heatmap en utilisant Python et les bibliothèques Python spécialisées dans l'analyse de
réseaux sociaux, telles que NetworkX et igraph.

Nous allons tester notre méthode sur des ensembles de données réels de réseaux
sociaux, afin de déterminer l'efficacité de notre approche pour identifier les acteurs

[Date]
8
influents dans un réseau social. Nous allons également comparer les résultats de notre
méthode avec d'autres méthodes existantes pour l'analyse des réseaux sociaux, afin de
démontrer l'efficacité de notre approche proposée.
Le but ultime de ce projet est de fournir une méthode efficace et fiable pour identifier
les acteurs influents dans un réseau social, qui peut être utilisée dans divers domaines
tels que le marketing, la politique et les relations publiques.

2. Analyse du besoin :

1) Besoins fonctionnels :

Les besoins fonctionnels produisent le modèle des besoins en se basant sur les
fonctions des utilisateurs ci-dessus. Elle qualifie de produire un système adapté aux
utilisateurs :

 Interface utilisateur : Le système doit avoir une interface utilisateur conviviale

qui permet à l'utilisateur de sélectionner le type de centralité qu'il souhaite
utiliser.
 Sélection de graphes : L'utilisateur doit être en mesure de sélectionner un
graphe spécifique à partir d'un ensemble de graphes.
 Calcul de centralité : Le système doit être en mesure de calculer les différentes
mesures de centralité telles que la centralité de proximité, la centralité de
degré et la centralité de betweenness pour le graphe sélectionné.
 Visualisation de résultats : Le système doit être en mesure de représenter
graphiquement les résultats de la mesure de centralité sous forme de
graphique.

2) Besoins non fonctionnels :

[Date]
9
Les besoins non fonctionnels sont importants car ils agissent de façon indirecte sur le
résultat et sur le rendement de l'utilisateur, ce qui fait qu'ils ne doivent pas être
négligés, pour cela il faut répondre aux exigences suivantes :

 Performance : Le système doit être capable de calculer les mesures de centralité

pour les grands ensembles de données de réseaux sociaux avec une efficacité
suffisante.
 Fiabilité : Le système doit être robuste et fiable pour éviter les erreurs de calcul
de centralité ou les bugs.
 Sécurité : Le système doit être sécurisé contre les attaques informatiques et les
accès non autorisés.
 Interface utilisateur conviviale : L'interface utilisateur doit être conviviale et
facile à utiliser pour les utilisateurs de tous niveaux.
 Documentation : Le projet doit être accompagné d'une documentation complète
pour permettre aux utilisateurs de comprendre le fonctionnement du système et
d'utiliser correctement l'interface utilisateur.
 Compatibilité multiplateforme : Le système doit être compatible avec
différentes plateformes et systèmes d'exploitation tels que Windows, Mac OS et
Linux.

[Date]
10
Chapitre 2 :

Analyse

[Date]
11
1. Etude du Projet :

Etude de l’existant :

Il existe plusieurs outils et bibliothèques disponibles pour l'analyse de réseaux sociaux,

tels que Gephi, Pajek, NetworkX, igraph et d'autres. Ces outils offrent des
fonctionnalités pour l'analyse de réseaux sociaux, y compris le calcul de la centralité
de nœuds et l'affichage graphique des résultats. Cependant, ces outils peuvent être
limités en termes de performances pour les ensembles de données volumineux et
peuvent nécessiter des connaissances approfondies en analyse de réseaux sociaux.

En outre, certains de ces outils sont payants et peuvent ne pas être accessibles pour les
utilisateurs qui ont des ressources limitées. C'est pourquoi, dans ce projet, nous
proposons de créer un outil open source avec une interface utilisateur conviviale qui
peut être utilisée par les utilisateurs avec différentes compétences techniques. Nous
visons à fournir un outil simple et efficace pour l'analyse de réseaux sociaux, avec une
approche basée sur Python, qui est un langage de programmation largement utilisé
dans l'analyse de données et l'apprentissage automatique.

2. Les technologies adoptées :

- l’environnement de travail : Anaconda : Spyder

- Le langage de programmation : Python

- Les bibliothèques utilisées : networkx / numpy / matplotlib

[Date]
12
3. Les outils utilisés :

Anaconda :

Anaconda est une distribution de logiciels open-source

pour le traitement de données et l'analyse scientifique
en Python et R. Elle contient de nombreux outils et
bibliothèques populaires utilisés dans les domaines de
l'apprentissage automatique, de la science des données,
de la visualisation et plus encore. Anaconda propose
une interface graphique utilisateur (GUI) appelée
Anaconda Navigator, qui facilite l'installation, la gestion et la mise à jour des outils et
bibliothèques inclus dans la distribution. Anaconda est une plateforme multi-
plateforme qui peut être installée sur Windows, Mac OS et Linux, ce qui permet aux
utilisateurs de travailler avec les mêmes outils et bibliothèques sur différentes plates-
formes. Il est largement utilisé par les scientifiques des données, les analystes de
données et les chercheurs pour le traitement de données, l'analyse de données, la
modélisation, l'apprentissage automatique et d'autres tâches liées aux données.

Spyder :

[Date]
13
 Spyder (Scientific PYthon Development EnviRonment) est
un environnement de développement intégré (IDE) open
source conçue pour les scientifiques des données, les
analystes et les ingénieurs en Python. Spyder fournit un
environnement interactif pour travailler avec Python, en
offrant des fonctionnalités de débogage, des outils
d'exploration de données, des éditeurs de code, des consoles IPython et plus encore.
Spyder a été conçu pour offrir un environnement de développement scientifique
complet avec des fonctionnalités pour l'analyse de données, l'exploration de données,
la modélisation, l'apprentissage automatique et d'autres tâches liées aux données.
Spyder est construit sur la bibliothèque Qt, qui fournit une interface utilisateur
graphique moderne et conviviale, et il est extensible avec des plugins pour ajouter des
fonctionnalités supplémentaires.

[Date]
14
 Chapitre 3 :

Mise en œuvre du Projet 

[Date]
15
1. Introduction :

Dans ce chapitre je présente les interfaces du projet et le fonctionnement de chacune.

Pour débuter, nous avons d’abord commencé par chercher quels outils nous allons
utiliser pour créer nos graphes et à savoir comment calculer les centralitées. Après de
nombreuses recherches nous avons fini par choisir les bibliothèques networkx pour
créer, manipuler et étudier des structures de graphes, numpy pour effectuer des
opérations mathématiques et statistiques, et matplotlib pour créer des graphiques et
des visualisations de données en 2D, pour ensuite les importer sur Spyder qui sera
notre IDE tout au long de ce projet afin de nous faciliter la création de notre site web.

2. Création de projet :

Pour aboutir à l’analyse des acteurs influents au sein d’un réseau social, nous avons
choisi de se concentrer sur 4 centralités particulière :

 Degree centrality : Le degré de centralité pour le nœud vi, noté Cd(vi),

est défini comme . IL mesure l'influence d'un nœud par
le nombre d'arêtes qui lui sont connectées, où un nœud avec une valeur de
degré élevée est un nœud hautement connecté au sein du réseau et donc
impliqué dans un grand nombre d'interactions. Le degré de centralité est
considéré comme une mesure du réseau local car il ne tient pas compte de
la structure du reste du réseau.

[Date]
16
 Closeness centrality : La centralité de proximité pour le nœud vi, notée
Cc(vi), est définie comme . Plus simplement, comme
l'inverse de l'éloignement, où l'éloignement est défini comme la somme
de la longueur des chemins les plus courts entre le nœud vi et tous les
autres nœuds du réseau. Intuitivement, la centralité de proximité mesure
la rapidité avec laquelle les informations peuvent se propager à partir du
nœud vi, en utilisant l'idée qu'un nœud est proche de tous les nœuds du
réseau et pas seulement proche de son voisin. En conséquence, la
centralité de proximité est considérée comme une mesure de la
connectivité du réseau mondial.

 Betweenness centrality : La centralité d'intermédiarité pour le nœud vi,

notée Cb(vi), est définie comme . Les
interactions de deux nœuds non adjacents dépendent d'autres nœuds, qui
se trouvent généralement sur les chemins les plus courts entre les deux
nœuds. Ainsi, la centralité d'intermédiarité considère un nœud influent s'il
se trouve sur une grande partie des chemins les plus courts entre une paire
de nœuds au sein du réseau. Intuitivement, la centralité d'intermédiarité
mesure la quantité d'informations susceptibles de passer par le nœud vi.
Étant donné que la centralité de l'intermédiarité prend en compte la
structure de l'ensemble du réseau, elle est considérée comme une mesure
de réseau global. Pour calculer la centralité d'intermédiarité d'un nœud au
sein du réseau, l'algorithme connu le plus rapide est Brandes qui effectue
deux étapes de base. La centralité de proximité est une mesure
relativement moins chronophage en comparaison, car elle ne nécessite
pas beaucoup de travail de post-traitement (c'est-à-dire, calculer le
nombre de chemins les plus courts qui traversent le nœud) qui est
nécessaire pour la centralité d'intermédiarité. En particulier, pour chaque

[Date]
17
 nœud vi, les N arbres de plus courts chemins de l'algorithme BFS doivent
être parcourus afin de déterminer le nombre de plus courts chemins qui
passent par vi. Par conséquent, le calcul de la centralité d'intermédiarité
pour un nœud, Cb(vi), pourrait prendre un temps supplémentaire.

 Heatmap centrality : la centralité de la carte thermique, utilise à la fois les

informations du réseau local et mondial en comparant la distance de
chaque nœud (c'est-à-dire les informations du réseau mondial) avec la
somme moyenne de la distance de ses nœuds voisins (c'est-à-dire les
informations du réseau local). En particulier, la centralité de la carte
thermique pour le nœud vi, notée Chm(vi), est définie formellement

comme :

La mesure de la carte thermique identifie le nœud "point chaud" dans son

voisinage, car elle considère un nœud avec une distance inférieure à celle
de la moyenne de ses voisins comme un nœud influent au sein du réseau.
Intuitivement, un nœud avec la plus petite distance parmi celle de ses
voisins est plus susceptible de faire passer des informations
spécifiquement à travers lui, plutôt que par l'un des nœuds adjacents.
Lorsque le signe de Chm(vi) passe du négatif au positif, la somme
moyenne de l'éloignement des voisins de vi devient inférieure à celle du
nœud vi, ce qui diminue la probabilité que des informations passent
spécifiquement par le nœud vi.

[Date]
18
 Par conséquent, en utilisant cette intuition, la centralité de la carte
thermique peut être considérée comme une mesure basée sur le "chemin
le plus court" et utilisée dans l'identification des nœuds super-diffuseurs
qui contrôlent le flux d'informations au sein d'un réseau sans échelle.

3. Implémentation :
Après avoir définie les différentes centralités, voici un exemple de leur
implémentation suivant ce réseau :

Figure 1 : Représentation du réseau

[Date]
19
 Figure 2 : Le degré de centralité

Figure 3 : La centralité de proximité

[Date]
20
 Figure 4 : La centralité d'intermédiarité

Figure 5   : la centralité de la carte thermique

[Date]
21
En conclusion, les mesures de centralité, telles que la centralité de degré, la centralité
d'intermédiarité (betweenness) et la heatmap, sont des outils utiles pour analyser la
structure des réseaux. En utilisant ces mesures, nous avons pu identifier les nœuds clés
et les connexions importantes dans le réseau, ce qui peut aider à comprendre les
processus sous-jacents. En combinant ces différentes mesures, nous avons pu obtenir
une image plus complète de la structure du réseau. Par exemple, la centralité de degré
nous a dit quels sont les nœuds les plus connectés, mais la centralité d'intermédiarité
nous indique quels sont les nœuds les plus importants pour le flux d'information dans
le réseau. Cependant, il convient de noter que les mesures de centralité ne fournissent
qu'une vue partielle du réseau et ne doivent pas être utilisées comme une mesure
unique de l'importance d'un nœud ou d'une connexion. D'autres facteurs tels que la
nature des interactions entre les nœuds peuvent également être importants pour
comprendre le fonctionnement du réseau.

[Date]
22
 Conclusion générale :

Sur un plan personnel, ce projet nous a permis de comprendre ce qu’est travailler en

équipe, le respect des délais, et d’acquérir de profondes connaissances sur la
conception et la programmation informatique, ce qui va nous aider plus tard dans la
compréhension des cours et TP tout au long de notre formation à l’EMSI mais aussi
dans notre futur métier en tant qu’ingénieur.

Sur le plan pratique, ce travail nous a démontré que le langage Python avec de l’html
est très complexe à maitriser en aussi peu de temps, cependant nous avons pu
découvrir qu’ils disposent de nombreuse fonctionnalité pour laisser libre cours à notre
créativité. Ainsi nous avons tenté de faire de notre mieux afin d’atteindre les objectifs
fixés de notre projet.

Webographie :

[Date]
23
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0235690

https://networkx.org/documentation/stable/tutorial.html

https://numpy.org/doc/stable/

https://igraph.org/python/tutorial/0.9.8/install.html#

https://docs.anaconda.com/navigator/index.html

https://www.python.org/downloads/

[Date]
24