Depuis la dernière décennie et avec l’apparition de services tels que Facebook, Twitter ou TikTok, tout le monde parle de réseaux sociaux. Mais, en fait, qu’est-ce qu’un réseau ? Pourquoi les utilisons-nous ? Dans cet article, nous allons essayer de comprendre la théorie des réseaux et de montrer leur importance et leur utilité dans le monde actuel.
Un réseau peut être défini comme « un ensemble de points reliés par paires par des lignes » [3].
Bien que cette définition soit très générale, elle montre également à quel point l’utilisation des réseaux est vaste - les villes reliées par des routes, les familles de langues, l’internet - tous peuvent être considérés comme des types de réseaux. D’une manière générale, l’analyse de réseau consiste à modéliser des systèmes du monde réel. Maintenant, si je vous demandais de dessiner votre réseau d’amis, que dessineriez-vous ? Je soupçonne que, dans la grande majorité des cas, vous dessineriez quelque chose comme ceci :
Rien qu’avec ce simple exemple de réseau, nous pouvons déjà observer les types d’informations qui peuvent être extraites du réseau : des informations sur les interactions entre les différentes parties du réseau. Ces modèles d’interaction (Dans notre exemple : entre les personnes, mais nous pouvons également imaginer des interactions entre les ordinateurs, les entités de transport ou les protéines.) peuvent avoir une influence différente sur le comportement de l’ensemble du réseau. Par conséquent, en modélisant le réseau et les interactions, nous pouvons ensuite déterminer leur structure et leurs propriétés. Aussi, nous pouvons faire des prédictions sur les processus dans le réseau, leur dynamique (par exemple, le mode de diffusion des informations, les parties fragiles du réseau, etc.).
Le réseau d’amis que nous venons de voir peut également être appelé un graphe. Quelle est la différence entre les deux ? Afin de dissiper toute confusion, je vais citer Albert-László Barabási, l’un des plus célèbres spécialistes des réseaux [1] :
| Network Science | Graph Theory |
|---|---|
| Network | Graph |
| Node | Vertex |
| Link | Edge |
Yet, there is a subtle distinction between the two terminologies : the {network, node, link} combination often refers to real systems: The WWW is a network of web documents linked by URLs; society is a network of individuals linked by family, friendship or professional ties; the metabolic network is the sum of all chemical reactions that take place in a cell. In contrast, we use the terms {graph, vertex, edge} when we discuss the mathematical representation of these networks: We talk about the web graph, the social graph (a term made popular by Facebook), or the metabolic graph. Yet, this distinction is rarely made, so these two terminologies are often synonyms of each other.
Par conséquent, chaque réseau (graphe) est créé à partir d’un ou plusieurs nœuds (sommets) qui sont reliés par des liens (bords). Lorsque deux nœuds ont un lien entre eux, on les appelle connectés ou adjacents. Le voisinage d’un nœud est constitué de tous les nœuds qui lui sont connectés. Nous verrons plus en détail la terminologie des réseaux dans un instant. Mais d’abord, nous allons détailler les différents types de réseaux qui existent.
Auparavant, nous avons déjà énuméré certains des réseaux possibles (amis, villes avec les routes, etc.). Mais la structure du réseau est utilisée dans de nombreuses autres disciplines. En général, nous pouvons distinguer 5 classes de réseaux différentes :
Avec toutes ces exemples et catégories, on peut voir qu’on est capable de modéliser des entités qui peuvent être abstraites ou réelles, ou les deux en même temps.
Dans la section précédente, nous avons déjà vu quelques notions utilisées pour représenter les graphes. Maintenant, nous allons plonger plus profondément dans la terminologie des graphes.
Les bords peuvent être orientés ou non orientés : les bords orientés (visualisés par des flèches) peuvent être utiles lorsqu’un lien entre les nœuds existe dans une direction mais pas dans l’autre - par exemple, dans les routes à sens unique ou le réseau de citation. Dans le cas de nœuds non dirigés, on suppose que le lien est réciproque, par exemple, dans un réseau d’amis. En outre, un poids peut être attribué à un bord, ce qui signifie une sorte de coût d’utilisation, comme le coût d’utilisation d’une autoroute. Ce poids peut être représenté par des chiffres au-dessus des bords, mais aussi par l’épaisseur de la flèche elle-même (plus elle est épaisse, plus elle a de poids). Dans le cas des graphes simples, entre chaque paire de nœuds, on peut avoir soit un bord non dirigé, soit deux bords dirigés. Il existe également des graphes multiples, dans lesquels nous pouvons avoir plusieurs bords (dirigés ou non dirigés) entre des paires de nœuds, et des auto-boucles - où un bord connecte un nœud à lui-même [4].
Les nœuds peuvent être caractérisés par le nombre de bords qu’ils possèdent. Dans le cas d’un réseau dirigé, nous pouvons distinguer deux caractéristiques d’un nœud :
D’ailleurs, les nœuds peuvent également être différenciés par leur classe, qui peut être représentée visuellement par des couleurs ou des formes différentes des nœuds. Les classes (ou les communautés) peuvent représenter des divisions d’entités du monde réel, comme les ordinateurs et les routeurs dans le cas d’un réseau informatique, ou peuvent être calculées (en utilisant des algorithmes de détection de communautés).
Centralité
Grâce à la notion de centralité, nous pouvons effectuer le classement pour comparer les nœuds, en fonction de notre mesure de centralité. Récemment, cette notion a gagné en popularité grâce aux réseaux sociaux qui utilisent parfois la métrique de centralité pour mesurer l'“influence”. Il existe maintenant plusieurs façons de calculer la métrique qui sera utilisée pour comparer les nœuds. Nous présenterons ici les mesures les plus simples mais toujours populaires [2].
Comme nous pouvons le constater, chacune des centralités donne des résultats différents et présente donc des perspectives différentes sur le même graphique. Le choix de l’une ou l’autre dépend strictement du type de réseau et d’analyse que l’on fait.
Indépendamment du type concret de centralité que nous prenons, nous pouvons également observer le niveau de centralité du réseau : haute centralité pour les réseaux plutôt centralisés et basse centralité pour les réseaux dans lesquels tous les nœuds sont connectés les uns aux autres.
Modularité
Il s’agit d’une autre mesure de la structure du réseau. La modularité évalue le niveau de division du réseau en différents modules (groupes, communautés). Une haute modularité signifie peu de connexions entre les différents groupes et beaucoup de connexions au sein de chaque groupe. A l’inverse, le réseau à basse modularité a en général plus de connexions transversales [5].
Les termes présentés ci-dessus constituent la base de la terminologie utilisée en analyse de réseau.
L’analyse de réseau utilise et combine de nombreux autres termes issus de la théorie des graphes, de la théorie de l’information et de l’exploration de données. Étant donné que le réseau est simple mais générique, il peut facilement être utilisé pour modéliser et structurer les données. Cet aspect, combiné à diverses méthodes d’analyse de réseau, est la raison de la grande utilité et de la popularité de l’analyse de réseau, qui apporte souvent une réponse à de nombreux problèmes du monde réel. Nous pouvons les regrouper en termes de questions de recherche [6]:
Quels groupes pouvons-nous former ?
L’idée est de trouver des divisions “naturelles” d’un réseau en différentes communautés. Nous utilisons des guillemets ici, car parfois la division pour nous, humains, est assez évidente, par exemple les groupes de directeurs et de managers dans un réseau social professionnel. Mais parfois, la définition d’une fonction permettant de diviser le réseau en communautés n’est pas du tout évidente. Par conséquent, afin de les détecter, différents algorithmes de détection de communautés sont utilisés. Les communautés peuvent être utilisées dans différents domaines, comme la détection d’anomalies et de fraudes, la réduction de grands réseaux en sous-réseaux, la recherche de modèles et de dynamiques cachés dans le réseau, etc.
Quel est le trajet optimal?
La traversée d’un graphe est une question importante et très difficile. Les problèmes de recherche d’un chemin entre deux nœuds, de détermination du chemin optimal ou de comparaison des coûts de différents chemins sont au cœur de la théorie des graphes. Différents algorithmes de recherche de chemin peuvent donc être utilisés pour planifier le routage des ordinateurs, le meilleur itinéraire de transport, etc.
Qui est le plus … (puissant, important) ?
Trouver les nœuds importants peut être crucial pour manipuler les réseaux de la manière la plus efficace. Qu’il s’agisse de déterminer l’influence de l’utilisateur, de trouver l’attaquant qui diffuse des logiciels malveillants ou de découvrir le meilleur film, tout peut être mesuré par l’utilisation de méthodes de l’analyse des réseaux telles que les centralités, le PageRank ou le HITS.
Qu’y a-t-il d’inhabituel ?
Étant donné que l’analyse de réseau paramètre le réseau et définit sa dynamique, on est en mesure de définir l’état “normal” (par défaut) du réseau. Par conséquent, si quelque chose d’inhabituel se produit, cela sera visible dans la structure, les caractéristiques et/ou la dynamique du réseau. L’identification des objets anormaux (nœuds, bords) ou la détermination de l’exactitude d’une structure (sous-graphe, interactions entre nœuds) est une partie importante des techniques de détection des fraudes et des anomalies.
Dans cet article, nous avons abordé ce qu’est un réseau et pourquoi il est utilisé. Nous avons détaillé la terminologie de base et l’utilisation de l’analyse de réseau. Nous avons également présenté quelques problèmes que l’analyse de réseau peut aider à résoudre.
En bref, comme nous pouvons le constater, l’analyse de réseau est un outil puissant. Il est déjà incroyablement utile dans de multiples disciplines et dans divers contextes, tels que le commerce (moteurs de recommandation, centres clients), la logistique (chaînes d’approvisionnement, routage), les ressources humaines (ciblage des candidats) ou les banques (détection des fraudes), pour n’en citer que quelques-uns. Avec l’avancée de la technologie, le nombre croissant de dispositifs IoT et l’augmentation des volumes de données, l’analyse de réseau en proposant des techniques de structuration et de compréhension de l’information deviendra encore plus indispensable.
Cover Photo by Alina Grubnyak on Unsplash
[1] Barabási, Albert-László. “Network science.” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371.1987 (2013): 20120375. accessed via: http://networksciencebook.com/chapter/2#networks-graphs on 2022-05-23
[2] Menczer, Filippo, Santo Fortunato, and Clayton A. Davis. A first course in network science. Cambridge University Press, 2020.
[3] Newman, Mark. Networks. Oxford university press, 2018.
[4] Zinoviev, Dmitry. Complex network analysis in Python: Recognize-construct-visualize-analyze-interpret. Pragmatic Bookshelf, 2018.
[5] https://cphss.wustl.edu/methodsandstrategies/social-network-analysis/network-analysis-101/
[6] “5 Graph Data Science Basics Everyone should know”, https://go.neo4j.com/rs/710-RRC-335/images/5-Graph-Data-Science-Basics-Everyone-Should-Know.pdf, accessed 31/05/2022,
