## Algorithmes des graphes



### Introduction contextuelle



**1.1 Les graphes : un outil essentiel en sciences sociales**



Dans le cadre de la sociologie quantitative, les graphes sont des outils puissants pour modéliser et analyser les relations entre individus, groupes et institutions. En effet, une grande partie des études sociologiques se concentre sur les **interactions entre les individus** et sur la manière dont ces interactions influencent des phénomènes sociaux tels que la diffusion des idées, la formation de communautés, ou l’influence sociale. 

Les graphes permettent de représenter ces relations de façon structurée et d’appliquer des méthodes d’analyse rigoureuses pour en extraire des informations pertinentes.

Un **graphe** est une structure composée de deux ensembles :

​	• Les **nœuds** (ou sommets) qui représentent les entités (par exemple, des individus dans une communauté).

​	• Les **arêtes** (ou liens) qui représentent les relations entre ces entités (par exemple, les relations d’amitié, de collaboration, ou d’interaction).



![graphe](assets/graphe.png)





**Exemple : Réseaux sociaux**



Prenons l’exemple d’un **réseau social** comme Facebook, LinkedIn ou Twitter. Dans ce contexte :

​	• Chaque **utilisateur** est un nœud du graphe.

​	• Une **arête** relie deux nœuds lorsqu’il existe une relation sociale entre ces utilisateurs (par exemple, ils sont amis, ils se suivent, ou ils interagissent).

<img src="assets/fb.png" alt="fb"  />

*Exemple de graphe représentant des relations sur Facebook*



<img src="assets/X.png" alt="X" style="zoom: 50%;" />



*Exemple de graphe représentant des relations sur Twitter / X.*



Ce type de représentation permet de répondre à plusieurs questions pertinentes en sociologie :

​	• Quels individus jouent un rôle central dans un réseau social ?

​	• Comment l’information se diffuse-t-elle au sein d’un groupe ?

​	• Quelles sous-communautés ou groupes se forment dans une société donnée ?



-------------------

**1.2 Types de graphes couramment utilisés en sociologie**



Il existe plusieurs types de graphes, chacun adapté à différents types de relations sociales et de données. Voici les plus courants :

​	•	**Graphe non dirigé** : Un graphe où les relations entre les nœuds ne sont pas orientées. Cela signifie que si une relation existe entre A et B, elle est réciproque. Par exemple, dans un réseau d’amis, si A et B sont amis, cela est vrai dans les deux sens.

​	•	**Graphe dirigé** : Un graphe où les relations ont une direction. Cela est utile pour représenter des relations non réciproques, comme les relations de suivi sur Twitter, où un utilisateur A peut suivre un utilisateur B, mais B ne suit pas nécessairement A.

​	•	**Graphe pondéré** : Chaque arête d’un graphe est associée à un poids qui peut représenter la force d’une relation (par exemple, la fréquence des interactions entre deux individus). Cela permet de modéliser des relations plus fines et nuancées.

​	•	**Graphe biparti** : Ce type de graphe est utile lorsqu’il s’agit de modéliser des relations entre deux types distincts d’entités. Par exemple, il peut être utilisé pour représenter les relations entre des individus et des événements (comme des personnes assistant à des conférences) ou des individus et des opinions (qui supporte telle ou telle idée politique).



**Exemple : Graphe biparti en sociologie**



Dans une étude de sociologie politique, on pourrait modéliser un **graphe biparti** où :



​	•	Les **nœuds de gauche** représentent des individus.

​	•	Les **nœuds de droite** représentent des opinions ou partis politiques.

​	•	Une **arête** existe entre un individu et une opinion s’il soutient cette idée.





![biparti](assets/bi.svg)



Ce type de représentation permet d’analyser les relations complexes entre les individus et leurs idéologies ou appartenances politiques, et de voir comment ces relations évoluent dans le temps ou dans des contextes sociaux spécifiques.



**1.3 Applications sociologiques des graphes**



Les graphes offrent une **flexibilité exceptionnelle** pour modéliser et analyser une grande variété de phénomènes sociaux. Voici quelques exemples d’applications courantes en sociologie :



​	1.	**Analyse des réseaux sociaux** :

L’analyse des réseaux sociaux permet d’identifier les individus les plus influents dans un groupe donné, de comprendre comment l’information ou les idées se diffusent, et de repérer des sous-groupes au sein de plus grandes communautés.

​	•	**Centralité** : Un concept clé dans cette analyse est la notion de **centralité**. Un individu central dans un réseau est souvent celui qui a le plus d’interactions (mesuré par le nombre d’arêtes) ou celui qui est le mieux placé pour diffuser l’information dans le groupe.

​	•	**Diffusion des idées** : Les graphes permettent aussi de modéliser la propagation des idées ou des innovations au sein d’une société, en identifiant les chemins les plus courts ou les relais clés dans la diffusion.

​	2.	**Détection de communautés** :

Les graphes peuvent être utilisés pour détecter des **communautés** au sein d’un réseau, c’est-à-dire des groupes d’individus plus fortement connectés entre eux qu’au reste du réseau. Ces communautés peuvent représenter des groupes d’intérêts communs, des sous-cultures ou des classes sociales dans des contextes plus larges.

​	•	**Exemple : Groupes d’amis dans un lycée** : On peut modéliser les interactions entre étudiants et utiliser des algorithmes pour identifier les groupes d’amis les plus cohésifs.

​	3.	**Étude des inégalités sociales** :

Les graphes peuvent également servir à modéliser et analyser des phénomènes tels que les **inégalités sociales**. Par exemple, en étudiant les relations de collaboration ou de mentorat dans une entreprise, un graphe peut révéler des structures de pouvoir ou des barrières à la mobilité sociale.

​	•	**Accès aux ressources** : En étudiant la distribution des liens dans un réseau, il est possible de comprendre qui a accès à des ressources critiques (telles que des informations ou des opportunités professionnelles) et qui est marginalisé.



**Transition vers les concepts techniques :**

Dans le chapitre suivant, nous allons introduire les **concepts fondamentaux des graphes** en informatique et voir comment ils peuvent être formalisés et analysés à l’aide de différents algorithmes.

-------

Auteur : Florian Mathieu

Licence CC BY NC

<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img alt="Licence Creative Commons" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" /></a> <br />Ce cours est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.