La science et ses réseaux
Internet et ses réseaux sociaux, les réseaux de transports, de télécommunication, les réseaux fluviaux, les réseaux neuronaux ou sanguins… Les réseaux sont partout : ils nous entourent et nous constituent.
Les réseaux peuvent être utilisés pour représenter et étudier des systèmes complexes (systèmes constitués de nombreuses entités en interaction). Les études menées sur les réseaux complexes ont mis en évidence des caractéristiques communes telles que le comportement sans échelle de la distribution des degrés 1, la propriété du petit monde 2 et la structure communautaire 3.
La taille croissante des réseaux du monde réel rend leur compréhension (structure et caractéristiques) plus difficile. La conception de méthodes permettant la réduction de la taille des réseaux tout en conservant les informations qu’ils contiennent devient alors indispensable.
L’extraction de la « colonne vertébrale » (backbone) d’un réseau, c’est-à-dire l’extraction des constituants les plus pertinents du réseau délesté des informations redondantes, est une solution communément utilisée pour répondre à ce besoin. Les méthodes existantes pour se faire peuvent être classées en deux catégories : les méthodes à gros grains (regroupement de nœuds partageant certaines caractéristiques communes) et les méthodes basées sur le filtrage (réduction du réseau par suppression de nœuds et de liens sur la base de propriétés définies comme étant à préserver).
1 Un réseau sans échelle est un réseau dont la probabilité qu’un nœud sélectionné au hasard dans le réseau ait un certain nombre de liens (degré) suit une distribution appelée loi de puissance ;
2 Caractéristique d’une population au sein de laquelle deux individus sélectionnés au hasard sont reliés par une courte chaine d’intermédiaires ;
3 Dans un réseau, présence de groupes de nœuds dans un réseau qui sont fortement interconnectés et faiblement connectés avec le reste du réseau. A savoir que les communautés peuvent se chevaucher.
Le Pr Hocine Cherifi, du Laboratoire d’Information de Bourgogne (LIB – EA 7534), et ses collaborateurs proposent deux méthodes de filtrage reposant sur l’exploitation de la structure communautaire du réseau.
La structure communautaire est une caractéristique fréquemment observée dans les réseaux complexes. De manière générale, dans les réseaux du monde réel, les nœuds sont naturellement organisés en communautés. Même s’il n’existe pas de définition unique de la structure communautaire, elle est généralement caractérisée comme la présence de groupes de nœuds fortement interconnectés entres eux et faiblement connectés avec les nœuds appartenant à d’autres communautés.
Les communautés peuvent se chevaucher. En effet, un nœud peut appartenir à plusieurs communautés : il s’agit alors de « nœud partagé entre plusieurs communautés » (overlapping node). Ces derniers, ainsi que les nœuds fortement connectés (appelés « hubs »), influencent la structure et la dynamique des réseaux.
Les deux méthodes proposées par le Pr Hocine Cherifi et ses collaborateurs reposent sur les nœuds fortement connectés (hubs) et les nœuds partagés entre plusieurs communautés (overlapping nodes).
La première méthode consiste à ne conserver dans un réseau que les nœuds partagés entre au moins deux communautés et les hubs. Après la mise en évidence de la structure communautaire d’un réseau, les overlapping nodes et les hubs, ainsi que les liens existants entre ces nœuds, sont extraits par ordre d’importance pour former le backbone. La seconde méthode, consiste à ne conserver que les nœuds appartenant à plusieurs communautés ainsi que leurs plus proches voisins, chacun extrait par ordre d’importance. Cette méthode repose sur une caractéristique fréquemment observée dans les réseaux du monde réel : la majorité des hubs et des nœuds appartenant à plusieurs communautés sont voisins.
Si la majorité des méthodes de filtrage alternatives reposent essentiellement sur les propriétés des liens entre les nœuds et ne tiennent pas compte de la structure communautaire du réseau, les deux méthodes proposées par le Pr Hocine Cherifi et ses collaborateurs utilisent elles la structure communautaire pour l’extraction des nœuds et les liens importants du réseau.
Ces deux méthodes ont été testées sur des réseaux pondérés du monde réel, de taille variable et issus de divers domaines tels que les domaines sociaux, biologiques ou encore technologiques. Les résultats obtenus montrent que ces deux méthodes présentent une efficacité similaire (les colonnes vertébrales extraites des réseaux par les deux méthodes sont quasiment identiques).
La performance de ces deux méthodes a été comparée à celle du filtre de disparité de Serrano, considérée comme étant la plus robuste des méthodes d’extraction. Les résultats obtenus montrent que la performance de cette dernière est moindre par rapport à celles proposées par le Pr Hocine Cherifi et ses collaborateurs.
—-
Les travaux menés par le Pr Hocine Cherifi et ses collaborateurs s’inscrivent dans le cadre du projet ANR COREGRAPHIE (COmpREssing networks and GRAPHs for efficIEnt computing) développé en partenariat avec les laboratoires IRIF (UMR 8243 : CNRS, Université de Paris), LIRIS (UMR 5205 : CNRS, INSA Lyon, Université Claude Bernard Lyon 1, Université Lumière Lyon 2, Ecole Centrale de Lyon) et l’INRIA.
L’étude décrite ci-dessus a fait l’objet d’une publication dans la revue Scientific Reports (du groupe Nature Publishing Group) : elle occupe le rang 24 au niveau mondial.
Pour la lire dans son intégralité, cliquez ici.
Référence :
Ghalmane, Z., Cherifi, C., Cherifi, H. et al. Extracting backbones in weighted modular complex networks. Sci Rep 10, 15539 (2020). https://doi.org/10.1038/s41598-020-71876-0