"Le tout est plus que la somme des parties."
Cette citation est attribuée à Aristote. Cela signifie que la valeur d'un ensemble est supérieure à la somme des valeurs de chacun de ses éléments pris individuellement. Cette idée est centrale en Network Science, où la structure et les interactions des éléments d'un système sont souvent plus importantes que les propriétés individuelles de chaque élément. Mais de quoi s'agit-il concrètement ?
La Network Science est une discipline scientifique interdisciplinaire qui étudie les réseaux, leur structure et leur dynamique. Elle s'intéresse aux interactions entre les nœuds d'un réseau, que ce soit des individus, des entreprises, des molécules ou des espèces. Elle est applicable à de nombreux domaines tels que la biologie, la physique, la sociologie, l'informatique, l'économie et bien d'autres encore. La Network Science permet de mieux comprendre les relations entre les différents acteurs d'un système, de prédire leur comportement et leur évolution, ainsi que d'optimiser leur fonctionnement. Elle ouvre de nouvelles perspectives dans de nombreux domaines, tels que l'étude des réseaux sociaux, la détection de communautés dans les réseaux, l'analyse des réseaux de transport et de télécommunications, la modélisation de la propagation des maladies et des épidémies, ou encore la modélisation des réseaux neuronaux dans le cerveau. In fine, tous ces exemples représentent des systèmes.
Les systèmes sont des ensembles d'éléments interdépendants qui interagissent entre eux pour accomplir un objectif commun. Les systèmes peuvent être de nature très diverse, allant des systèmes biologiques aux systèmes sociaux, en passant par les systèmes physiques ou les systèmes informatiques. Les systèmes se caractérisent par leur complexité et leur interdépendance. La Network Science est étroitement liée aux systèmes, dans la mesure où elle permet d'analyser la structure et la dynamique des réseaux sous-jacents. En étudiant les propriétés des réseaux, la Network Science permet de mieux comprendre le fonctionnement des systèmes qui en découlent, de prédire leur comportement et leur évolution, ou de proposer des solutions pour améliorer leur efficacité.
Nous allons voir ici comment modéliser un réseau et définir quelques outils qui permettront de déterminer leurs caractéristiques dans d'autres articles.
Modéliser un réseau
Maintenant que nous avons vu ce qui conduit à utiliser la Network Science, nous allons nous pencher sur la modélisation des réseaux. La modélisation des réseaux consiste à représenter un système sous la forme d'un graphe (terme mathématique pour qualifier un réseau), où les nœuds représentent les éléments du système et les liens représentent les interactions entre ces éléments. Plus formellement :
$$G = (V, E)$$ $$u, v \in V$$ $$(u, v) \in E$$
Ce qui signifie, soit G un graphe composé de l'ensemble de ses nœuds V et l'ensemble de ses liens E. u et v sont 2 nœuds de l'ensemble V. Et le lien entre u et v est un lien de l'ensemble des liens E.
Pour illustrer nos exemples, nous utiliserons la bibliothèque networkX qui est un outil en Python qui nous permettra de créer, de modifier, de visualiser, d'analyser la topologie et les propriétés de nos réseaux. Et matplotlib pour permettre l'affichage de nos graphiques.
import networkx as nx import matplotlib.pyplot as plt
Graphes non-dirigés
$$G = (V, E)$$ $$u, v \in V$$ $$(u, v) \in E \equiv (v, u) \in E$$
L'exemple le plus parlant (et fréquemment utilisé) est la relation d'amitié proposée par Facebook. Chaque personne au sein du réseau est représentée par un nœud (un sommet) et si 2 personnes sont "amis" sur ce réseau social, alors ils sont reliés par un lien (un arc).
social_edges = [('Alice', 'Bob'), ('Alice', 'Charlie'), ('Alice', "Franck"), ('Bob', 'Charlie'), ('Charlie', 'Franck'), ('Eve', 'Franck'), ('Eve', 'Grace'), ('Eve', 'Helen'), ('Eve', 'Isabelle'), ('Franck', 'Grace'), ('Grace', 'Helen'), ('Grace', 'Isabelle'), ('Helen', 'Isabelle')] social_network = nx.Graph(social_edges) nx.draw(social_network, with_labels=True, arrows=None) plt.show()
Graphes dirigés ou orientés
$$G = (V, E)$$ $$u, v \in V$$ $$(u, v) \in E \not\equiv (v, u) \in E$$
Notez que dans ce réseau (non-dirigés), les relations d'amitié sont symétriques. Si Pierre est "ami" avec André alors André est "ami" avec Pierre. Mais dans certains réseaux (dirigés) cela ne sera pas le cas : dans le cas d'un arbre généalogique, si Pierre est le père d'André alors André ne peut être le père de Pierre. Dans ce cas, nous représentons le lien qui unit Pierre et André par une flèche dirigé vers l'un des nœuds en fonction du type de la relation (P -> A : pierre est le père d'André).
genealogy_edges = [('Alice', 'Bob'), ('Alice', 'Charlie'), ('Bob', 'David'), ('Bob', 'Eve'), ('Charlie', 'Frank'), ('Charlie', 'Grace'), ('David', 'Helen'), ('Grace', 'Isabelle')] family_tree = nx.DiGraph(genealogy_edges) nx.draw_spectral(family_tree, with_labels=True) plt.show()
Self-loops
$$G = (V, E)$$ $$\exists u \in V, (u, u) \in E$$
Une autre particularité dans les réseaux est que certains nœuds vont avoir une relation avec eux-mêmes (autrement dit un lien vers elles-mêmes). Dans ce cas, on parle de boucle (ou self-loops). Dans une chaîne alimentaire modélisée en réseau, certaines espèces peuvent se manger elles-mêmes.
food_chain_edges = [('escargot', 'végétaux'), ('abeille', 'végétaux'), ('araignée', 'abeille'), ('souris', 'abeille'), ('souris', 'escargot'), ('grenouille', 'escargot'), ('serpent', 'souris'), ('oiseau', 'souris'), ('serpent', 'grenouille'), ('grenouille', 'grenouille'), ('araignée', 'araignée'), ('serpent', 'oiseau'), ('serpent', 'serpent'), ('oiseau', 'serpent'), ('araignée', 'mouche'), ('mouche', 'mouche')] food_chain = nx.DiGraph(food_chain_edges) nx.draw_kamada_kawai(food_chain, with_labels=True) plt.show()
Poids
$$G = (V, E, w)$$ $$u, v \in V$$ $$w : (u, v) \in E \mapsto \mathbb{R}$$
Autre caractéristique clé dans la modélisation de réseaux : la pondération. L'affectation de poids aux arcs dans un réseau permet d'ajouter une dimension supplémentaire à l'analyse de la structure et de la dynamique du réseau. En effet, les poids peuvent représenter différentes informations telles que des distances, des coûts, des probabilités, des forces d'interactions, des intensités de flux, etc. Ces informations peuvent être utilisées pour mesurer la robustesse du réseau, identifier les nœuds les plus importants, détecter les communautés, prédire les flux de trafic, ou encore optimiser les itinéraires, entre autres. Notez qu'il est également possible d'attribuer des propriétés (sous la forme de tuples par exemples) aux nœuds tels qu'un nom, un âge, des centres d'intérêt, etc.
hero_edges = [('Iron Man', 'Captain America', 5), ('Iron Man', 'Spider-Man', 3), ('Iron Man', 'Hulk', 2), ('Iron Man', 'Thor', 4), ('Iron Man', 'Black Widow', 1), ('Captain America', 'Spider-Man', 4), ('Captain America', 'Hulk', 3), ('Captain America', 'Thor', 5), ('Captain America', 'Black Widow', 2), ('Spider-Man', 'Deadpool', 3), ('Spider-Man', 'Hulk', 1), ('Spider-Man', 'Thor', 2), ('Hulk', 'Thor', 3), ('Hulk', 'Black Widow', 1), ('Thor', 'Black Widow', 2), ('Black Widow', 'Hawkeye', 2), ('Black Widow', 'Scarlet Witch', 3), ('Hawkeye', 'Scarlet Witch', 1), ('Scarlet Witch', 'Vision', 4)] hero_network = nx.Graph() hero_network.add_weighted_edges_from(hero_edges,) pos = nx.spring_layout(hero_network) nx.draw(hero_network, pos, with_labels=True, arrows=None, width=[edge[2] for edge in hero_network.edges(data='weight')]) plt.show()
Dans ce graphe, nous représentons un réseau social des héros Marvel en assignant des poids (de 1 à 5) aux arcs en fonction de leur niveau de coopération, d'amitié, de rivalité, de romance... Dans notre graphique, la largeur des liens représente le poids. Nous pourrions pousser l'analyse de ce réseau en nous intéressant aux différentes mesures de centralité pour par exemple déterminer les héros les plus influents dans l'univers marvel.
Encodage
Vous aurez remarqué que depuis le début, j'utilise des listes de tuples pour représenter les relations dans les graphes. Un tuple correspond à un ensemble de valeur pouvant être de différents types et qui forme une entité (des coordonnées, une relation, etc.). Cependant, il existe une seconde façon d'encoder des graphes : les matrices d'adjacence, dans laquelle chaque ligne et chaque colonne correspondent à un nœud du réseau, et chaque cellule de la matrice indique la présence ou l'absence d'un lien entre deux nœuds. Si le nœud i est relié au nœud j, alors l'élément a_ij de la matrice vaut 1 (ou la valeur de la pondération), sinon il vaut 0. Notez que dans ce type de représentation, les diagonales de la matrice indiquent la présence de self-loops et que la matrice d'un graphe non-dirigé est symétrique.
import numpy as np ADJ_MAT = [[0, 0, 1, 4, 1], [0, 0, 5, 1, 3], [2, 0, 0, 1, 0], [1, 0, 3, 0, 1], [4, 0, 0, 1, 3]] graph = nx.from_numpy_matrix(np.matrix(ADJ_MAT), create_using=nx.DiGraph) pos = nx.circular_layout(graph) nx.draw(graph, pos, with_labels=True, width=[edge[2] for edge in graph.edges(data='weight')]) plt.show()
D'autres types de réseaux
Nous avons vu les réseaux les plus classiques, mais selon les propriétés des données, certains types de graphes sont plus appropriés et peuvent donc être plus utiles pour modéliser des phénomènes complexes. Nous allons survoler les plus connus.
Réseaux bi-partites
$$G = (U, V, E)$$ $$U \cap V = \emptyset$$ $$\forall (u, v) \in E, u \in U, v \in V$$
Un graphe bipartite est un type particulier de graphe dont les nœuds peuvent être divisés en deux ensembles distincts, tels que chaque nœud de l'un des ensembles est lié à tous les nœuds de l'autre ensemble, mais aucun nœud n'est relié à un autre nœud du même ensemble. Autrement dit, il n'y a pas d'arêtes qui connectent deux nœuds du même ensemble. Les graphes bipartites sont souvent utilisés pour modéliser des relations entre deux ensembles d'entités distinctes, telles que les utilisateurs et les produits dans un système de recommandation ou les acteurs et les films dans une base de données de cinéma.
clients = ['client1', 'client2', 'client3', 'client4', 'client5', 'client6'] products = ['produit1', 'produit2', 'produit3', 'produit4', 'produit5', 'produit6', 'produit7', 'produit8', 'produit9'] consumer_product_edges = [('client1', 'produit1'), ('client1', 'produit2'), ('client1', 'produit4'), ('client1', 'produit8'), ('client2', 'produit1'), ('client2', 'produit2'), ('client2', 'produit3'), ('client2', 'produit8'), ('client3', 'produit2'), ('client3', 'produit6'), ('client3', 'produit8'), ('client4', 'produit1'), ('client4', 'produit9'), ('client5', 'produit1'), ('client5', 'produit3'), ('client5', 'produit5'), ('client5', 'produit9'), ('client6', 'produit2'), ('client6', 'produit7')] # Création du graphe bipartite B = nx.Graph() # Ajout des nœuds B.add_nodes_from(clients, bipartite=0) B.add_nodes_from(products, bipartite=1) B.add_edges_from(consumer_product_edges) pos = {node: (0, i) for i, node in enumerate(clients)} pos.update({node: (1, i) for i, node in enumerate(products)}) nx.draw(B, pos=pos, with_labels=True, font_weight='bold') plt.show()
Nous pourrions par exemple pousser un peu l'analyse de cette modélisation en nous demandant quels sont les produits qui ont été consommés par les mêmes clients. De cette manière, nous pourrions supposer qu'il existe des points d'intérêts communs entre les clients, mais peut-être aussi entre les produits ! Au-delà de la reconstruction des caractéristiques des nœuds de notre réseau, nous pourrions également proposer une méthode de prédiction de liens en vue de recommander des produits auprès de nos clients...
Réseaux multi-couches
$$G = (V, E_i)$$ $$i \in {1, ..., n}$$
Un graphe multilayer est un graphe composé de plusieurs couches, chacune représentant un réseau distinct. Chaque couche peut avoir des nœuds communs avec les autres couches et peut également avoir des arêtes intra-couche (c'est-à-dire entre les nœuds de la même couche) et inter-couches (c'est-à-dire entre les nœuds de couches différentes). Les graphes multi-couches peuvent représenter des systèmes complexes qui ont des interactions multi-niveaux et fournissent un cadre pour modéliser des phénomènes tels que les réseaux sociaux, les réseaux de transport, les réseaux de communication et les réseaux biologiques, entre autres.
Networkx n'offre pas de fonction qui gère en quelques lignes ce type de graphes. Dans le code ci-dessous, je ne vous donne pas le code permettant de faire la représentation finale du réseau (~200 LOCs), en fin de compte le but ici est de vous initier aux représentations possibles des réseaux (ce snippet est déjà bien assez long :)). Je vous laisse donc face à votre imagination pour savoir ce que cache la fonction multilayer_network_graph().
labels = ['Alice', 'Bob', 'Charlie', 'David', 'Eve', 'Frank'] id_labels = {i: name for i, name in enumerate(labels)} # Création d'un réseau social avec des relations amicales A = nx.Graph() A.add_nodes_from(labels) A.add_edges_from([('Alice', 'Bob'), ('Alice', 'Charlie'), ('Bob', 'Charlie'), ('Charlie', 'David'), ('David', 'Eve'), ('Eve', 'Frank'), ('Frank', 'Alice')]) # Création d'une couche pour les relations familiales F = nx.Graph() F.add_nodes_from(labels) F.add_edges_from([('Alice', 'Bob'), ('Charlie', 'David'), ('David', 'Eve'), ('Eve', 'Frank')]) # Création d'une couche pour les relations professionels P = nx.Graph() P.add_nodes_from(labels) P.add_edges_from([('Alice', 'David'), ('Alice', 'Eve'), ('Bob', 'Frank'), ('Charlie', 'David')]) fig = plt.figure() ax = fig.add_subplot(111, projection='3d') multilayer_network_graph([A, F, P], node_labels=id_labels, ax=ax, layout=nx.fruchterman_reingold_layout) ax.set_axis_off() plt.show()
Dans ce réseau, nous avons donc un tissu social qui est formé de relations amicales, de relations familiales et de relations professionnelles. Chaque nœud est dupliqué dans chacun des réseaux, mais les liens quant à eux sont uniques à chaque réseau. Dans cet exemple, en augmentant les nœuds avec certaines propriétés (croyances, préférences, ...) et en procédant à de la détection de communautés, on peut étudier comment la dynamique de l'amitié entre les individus affecte leur adhésion à des idéologies ou à des mouvements sociaux, ou comment la structure des réseaux familiaux influence les choix de carrière et les parcours de vie des individus. En somme, on peut facilement analyser la complexité des relations interpersonnelles et leur impact sur le comportement individuel et collectif.
Réseaux temporels
$$G = (V, E_t = (u, v, t, d))$$ $$\textrm{avec t le temps et d la durée}$$
Un réseau temporel est un type de réseau où les interactions entre les nœuds sont liées à un certain moment ou pendant un intervalle de temps, ils sont dynamiques. Dans un réseau temporel, les arcs peuvent apparaître et disparaître au fil du temps, ou leur poids peut varier en fonction des événements qui se produisent. Les réseaux temporels sont utilisés pour modéliser des phénomènes dynamiques dans lesquels les interactions entre les nœuds peuvent changer de manière significative et où il est important de prendre en compte l'aspect temporel. Les applications des réseaux temporels vont de la modélisation des réseaux sociaux aux réseaux de transport, en passant par la biologie ou la physique. La Network Science offre de nombreux outils pour analyser les réseaux temporels et en extraire des informations utiles sur leur structure et leur dynamique. Néanmoins, ce type de graphe est légèrement plus technique et mérite par conséquent un article à part entière !
Comme pour les autres types de réseaux, nous allons tout de même faire un petit exemple pour voir de quoi il en retourne. Mais avant de commencer, il est important de noter que les réseaux dynamiques peuvent être représentés de multiples façons. Il y a des représentations dynamiques, c'est-à-dire un réseau qui évolue dans le temps sur une vidéo par exemple et d'autres méthodes qui permettent de représenter cela de manière statique (sur un unique graphique). Nous allons nous concentrer sur cette seconde méthode. Parmi les représentations statiques, il y a également plusieurs façons de représenter le graphe : je vais vous proposer 2 visualisations.
Mais avant cela, voici un peu de contexte. Vous êtes RH d'une entreprise et vous avez scrupuleusement noté qui a collaboré avec qui au cours des 10 derniers projets dans le but d'observer l'évolution des groupes de travail. Vos données sont constituées comme ceci : [dev_i, dev_j, projet_n]. Chaque dev est encodé par son identifiant. Utilisons à présent la bibliothèque teneto qui permet entre autres d'avoir des visuels pour ce type de réseaux.
import teneto import matplotlib.pyplot as plt spread_edgelist = [[0, 1, 0], [0, 2, 0], [0, 3, 0], [0, 4, 0], [5, 6, 0], [5, 7, 0], [0, 1, 1], [0, 2, 1], [0, 3, 1], [1, 4, 1], [4, 5, 1], [6, 7, 1], [0, 1, 2], [0, 2, 2], [1, 3, 2], [3, 4, 2], [5, 6, 2], [7, 8, 2], [0, 1, 3], [2, 4, 3], [4, 5, 3], [6, 7, 3], [0, 1, 4], [2, 4, 4], [4, 5, 4], [5, 6, 4], [7, 8, 4], [8, 9, 4], [0, 1, 5], [2, 4, 5], [4, 5, 5], [5, 6, 5], [7, 8, 5], [8, 9, 5], [0, 1, 6], [2, 3, 6], [3, 4, 6], [5, 7, 6], [8, 9, 6], [0, 1, 7], [2, 3, 7], [4, 5, 7], [5, 6, 7], [7, 8, 7], [0, 1, 8], [2, 3, 8], [4, 5, 8], [6, 7, 8], [8, 9, 8], [0, 1, 9], [2, 3, 9], [4, 5, 9], [6, 7, 9], [8, 9, 9]] # les prénoms de vos devs nodes_labels = ["Alice", "Bob", "Charlie", "David", "Eve", "Frank", "George", "Harry", "Isabelle", "Jane"] N = len(nodes_labels) # nombre total de dev T = len(set([edge[2] for edge in spread_edgelist])) # nombre total de projets collab_network_slice_plot = teneto.TemporalNetwork(N=N, T=T, nettype='bd', from_edgelist=spread_edgelist, timeunit='Projects', nodelabels=nodes_labels, timetype='discrete', starttime=0).plot('slice_plot', cmap='plasma') plt.show()
Cette visualisation nous permet de voir pour chaque projet les groupes de travail formés par les devs. On peut notamment remarquer qu'au fil des projets de ce dataset, les devs ont eu tendance à converger vers des binômes.
Teneto nous permet également de disposer d'une visualisation en "empilant" les matrices d'adjacences. Mais cette dernière est peut-être un peu moins efficace. Tout dépend des données que l'on souhaite observer.
collab_network_matrix_stack_plot = teneto.TemporalNetwork(N=N, T=T, nettype='bd', from_edgelist=spread_edgelist, timeunit='Projects', timetype='discrete', starttime=0).plot('graphlet_stack_plot', cmap='copper') plt.show()
En conclusion, la modélisation et l'analyse de réseaux offre une grande variété d'applications et de possibilités de compréhension des phénomènes complexes. La compréhension des différentes formes de réseaux et la possibilité de les modéliser efficacement (avec NetworkX par exemple) permet de mieux comprendre les interactions et les relations entre les entités du monde réel, qu'il s'agisse de personnes, d'organisations, de produits ou de phénomènes naturels. Les différents types de graphes tels que les graphes bipartites, les graphes multicouches et les graphes temporels ajoutent des dimensions supplémentaires à l'analyse des réseaux, offrant ainsi des opportunités encore plus vastes pour la recherche et l'analyse de données. En somme, l'utilisation de la network science ouvre des perspectives prometteuses pour l'étude de la complexité des systèmes et pour la prise de décision dans divers domaines.