Réseau multidimensionnel

En théorie des réseaux , les réseaux multidimensionnels , un type particulier de réseau multicouche , sont des réseaux comportant plusieurs types de relations. Des tentatives de plus en plus sophistiquées de modéliser des systèmes du monde réel sous forme de réseaux multidimensionnels ont apporté des informations précieuses dans les domaines de l'analyse des réseaux sociaux , des transports urbains et internationaux , de l'écologie , de la psychologie, de la médecine, de la biologie, du commerce, de la climatologie, de la physique, des neurosciences computationnelles , de la gestion des opérations et de la finance.

L'exploration rapide des réseaux complexes ces dernières années a été entravée par un manque de conventions de dénomination normalisées, car divers groupes utilisent une terminologie qui se chevauche et se contredit pour décrire des configurations de réseau spécifiques (par exemple, multiplex, multicouche, multiniveau, multidimensionnel, multirelationnel, interconnecté). Pour exploiter pleinement les informations de l'ensemble de données sur la nature directionnelle des communications, certains auteurs considèrent uniquement les réseaux directs sans aucune étiquette sur les sommets et introduisent la définition de multigraphes étiquetés par les arêtes qui peuvent couvrir de nombreuses situations multidimensionnelles. Le terme « entièrement multidimensionnel » a également été utilisé pour désigner un multigraphe étiqueté par les arêtes multipartite . Les réseaux multidimensionnels ont également été récemment recadrés comme des instances spécifiques de réseaux multicouches. Dans ce cas, il y a autant de couches que de dimensions, et les liens entre les nœuds au sein de chaque couche sont simplement tous les liens pour une dimension donnée.

Dans la théorie élémentaire des réseaux, un réseau est représenté par un graphe dans lequel se trouve l'ensemble des nœuds et les liens entre les nœuds, généralement représentés par un tuple de nœuds . Bien que cette formalisation de base soit utile pour analyser de nombreux systèmes, les réseaux du monde réel présentent souvent une complexité supplémentaire sous la forme de multiples types de relations entre les éléments du système. Une première formalisation de cette idée est venue par son application dans le domaine de l'analyse des réseaux sociaux (voir, par exemple, et les articles sur les algèbres relationnelles dans les réseaux sociaux) dans lesquels de multiples formes de connexion sociale entre les personnes étaient représentées par de multiples types de liens.

Pour tenir compte de la présence de plusieurs types de liens, un réseau multidimensionnel est représenté par un triplet , où est un ensemble de dimensions (ou couches), dont chaque membre est un type de lien différent, et se compose de triplets avec et .

Notez que comme dans tous les graphes orientés , les liens et sont distincts.

Par convention, le nombre de liens entre deux nœuds d'une dimension donnée est soit 0, soit 1 dans un réseau multidimensionnel. Cependant, le nombre total de liens entre deux nœuds dans toutes les dimensions est inférieur ou égal à .

Dans le cas d'un réseau pondéré , ce triplet est étendu à un quadruplet , où est le poids sur le lien entre et dans la dimension .

De plus, comme cela est souvent utile dans l'analyse des réseaux sociaux, les poids des liens peuvent prendre des valeurs positives ou négatives. De tels réseaux signés peuvent mieux refléter des relations comme l'amitié et l'inimitié dans les réseaux sociaux. Alternativement, les signes de lien peuvent être considérés comme des dimensions elles-mêmes, par exemple où et Cette approche est particulièrement intéressante lorsqu'on considère des réseaux non pondérés.

Cette conception de la dimensionnalité peut être étendue si des attributs dans plusieurs dimensions doivent être spécifiés. Dans ce cas, les liens sont des n -uplets . Une telle formulation étendue, dans laquelle des liens peuvent exister dans plusieurs dimensions, est peu courante mais a été utilisée dans l'étude de réseaux multidimensionnels variant dans le temps .

Alors que les réseaux unidimensionnels ont des matrices d'adjacence bidimensionnelles de taille , dans un réseau multidimensionnel avec des dimensions, la matrice d'adjacence devient un tenseur d'adjacence multicouche, une matrice à quatre dimensions de taille . En utilisant la notation d'index , les matrices d'adjacence peuvent être indiquées par , pour coder les connexions entre les nœuds et , tandis que les tenseurs d'adjacence multicouches sont indiqués par , pour coder les connexions entre le nœud dans la couche et le nœud dans la couche . Comme dans les matrices unidimensionnelles, les liens dirigés, les liens signés et les poids sont tous facilement pris en charge par ce cadre.

Dans le cas des réseaux multiplexés , qui sont des types particuliers de réseaux multicouches où les nœuds ne peuvent pas être interconnectés avec d'autres nœuds dans d'autres couches, une matrice tridimensionnelle de taille avec des entrées suffit à représenter la structure du système en codant les connexions entre les nœuds et dans la couche .

Dans un réseau multidimensionnel, les voisins d'un nœud sont tous des nœuds connectés à travers les dimensions.

Un chemin entre deux nœuds dans un réseau multidimensionnel peut être représenté par un vecteur r dans lequel la ième entrée de r est le nombre de liens parcourus dans la ième dimension de . Comme pour le degré de chevauchement, la somme de ces éléments peut être considérée comme une mesure approximative de la longueur d'un chemin entre deux nœuds.

L'existence de couches multiples (ou dimensions) permet d'introduire le nouveau concept de réseau de couches , propre aux réseaux multicouches. En fait, les couches peuvent être interconnectées de telle manière que leur structure puisse être décrite par un réseau, comme le montre la figure.

Le réseau de couches est généralement pondéré (et peut être dirigé), bien que, en général, les poids dépendent de l'application concernée. Une approche simple consiste, pour chaque paire de couches, à additionner tous les poids des connexions entre leurs nœuds pour obtenir des poids d'arêtes qui peuvent être codés dans une matrice . Le tenseur d'adjacence de rang 2, représentant le réseau sous-jacent de couches dans l'espace, est donné par

où est la matrice canonique dont toutes les composantes sont égales à zéro, à l'exception de l'entrée correspondant à la ligne et à la colonne , qui est égale à un. En utilisant la notation tensorielle, il est possible d'obtenir le réseau (pondéré) de couches à partir du tenseur d'adjacence multicouche comme .

Dans un réseau multidimensionnel non interconnecté, où les liens intercouches sont absents, le degré d'un nœud est représenté par un vecteur de longueur . Voici une autre façon de désigner le nombre de couches dans les réseaux multicouches. Cependant, pour certains calculs, il peut être plus utile de simplement additionner le nombre de liens adjacents à un nœud sur toutes les dimensions. Il s'agit du degré de chevauchement : . Comme pour les réseaux unidimensionnels, une distinction peut également être établie entre les liens entrants et les liens sortants. Si des liens intercouches sont présents, la définition ci-dessus doit être adaptée pour en tenir compte, et le degré multicouche est donné par

où les tenseurs et ont toutes les composantes égales à 1. L'hétérogénéité du nombre de connexions d'un nœud à travers les différentes couches peut être prise en compte grâce au coefficient de participation.

Lorsqu'il est étendu aux réseaux multicouches interconnectés, c'est-à-dire aux systèmes dans lesquels les nœuds sont connectés entre eux par couches, le concept de centralité est mieux compris en termes de polyvalence. Les nœuds qui ne sont pas centraux dans chaque couche peuvent être les plus importants pour les systèmes multicouches dans certains scénarios. Par exemple, c'est le cas lorsque deux couches codent des réseaux différents avec un seul nœud en commun : il est très probable qu'un tel nœud aura le score de centralité le plus élevé car il est responsable du flux d'informations entre les couches.

En ce qui concerne les réseaux unidimensionnels, la polyvalence des vecteurs propres peut être définie comme la solution du problème des valeurs propres donné par , où la convention de sommation d'Einstein est utilisée par souci de simplicité. Ici, donne la généralisation multicouche de la centralité des vecteurs propres de Bonacich par nœud et par couche. La polyvalence globale des vecteurs propres est simplement obtenue en additionnant les scores sur les couches comme .

Quant à son homologue unidimensionnel , la polyvalence de Katz est obtenue comme la solution de l'équation tensorielle , où , est une constante plus petite que la plus grande valeur propre et est une autre constante généralement égale à 1. La polyvalence globale de Katz est simplement obtenue en additionnant les scores sur les couches comme .

Pour les réseaux unidimensionnels, l' algorithme HITS a été introduit à l'origine par Jon Kleinberg pour évaluer les pages Web. L'hypothèse de base de l'algorithme est que les pages pertinentes, appelées autorités, sont pointées par des pages Web spéciales, appelées hubs. Ce mécanisme peut être décrit mathématiquement par deux équations couplées qui se réduisent à deux problèmes de valeurs propres. Lorsque le réseau n'est pas orienté, la centralité de l'autorité et du hub sont équivalentes à la centralité du vecteur propre. Ces propriétés sont préservées par l'extension naturelle des équations proposées par Kleinberg au cas des réseaux multicouches interconnectés, donnés par et , où indique l'opérateur de transposition, et indiquent respectivement la centralité du hub et de l'autorité. En contractant les tenseurs du hub et de l'autorité, on obtient les polyvalences globales comme et , respectivement.

Le PageRank , introduit à l'origine pour classer les pages Web, peut également être considéré comme une mesure de centralité pour les réseaux multicouches interconnectés.

Il convient de noter que le PageRank peut être considéré comme la solution à l'état stationnaire d'un processus de Markov spécial au sommet du réseau. Les marcheurs aléatoires explorent le réseau selon une matrice de transition spéciale et leur dynamique est régie par une équation maîtresse de marche aléatoire . Il est facile de montrer que la solution de cette équation est équivalente au vecteur propre principal de la matrice de transition.

Les marches aléatoires ont également été définies dans le cas de réseaux multicouches interconnectés et de multigraphes à bords colorés (également appelés réseaux multiplex). Pour les réseaux multicouches interconnectés, le tenseur de transition régissant la dynamique des marcheurs aléatoires à l'intérieur et à travers les couches est donné par , où est une constante, généralement fixée à 0,85, est le nombre de nœuds et est le nombre de couches ou de dimensions. Ici, pourrait être appelé tenseur Google et est le tenseur de rang 4 avec toutes les composantes égales à 1.

Comme son homologue unidimensionnel, la polyvalence du PageRank consiste en deux contributions : l'une codant une marche aléatoire classique avec un taux et l'autre codant la téléportation à travers les nœuds et les couches avec un taux .

Si l'on indique par le tenseur propre du tenseur Google , désignant la probabilité à l'état stationnaire de trouver le marcheur dans le nœud et la couche , le PageRank multicouche est obtenu en additionnant sur les couches le tenseur propre :

Comme beaucoup d'autres statistiques de réseau, la signification d'un coefficient de clustering devient ambiguë dans les réseaux multidimensionnels, en raison du fait que les triplets peuvent être fermés dans des dimensions différentes de celles de leur origine. Plusieurs tentatives ont été faites pour définir les coefficients de clustering locaux, mais ces tentatives ont mis en évidence le fait que le concept doit être fondamentalement différent dans les dimensions supérieures : certains groupes ont basé leur travail sur des définitions non standard, tandis que d'autres ont expérimenté différentes définitions des marches aléatoires et des 3-cycles dans les réseaux multidimensionnels.

Bien que les structures interdimensionnelles aient déjà été étudiées, elles ne parviennent pas à détecter des associations plus subtiles que l'on trouve dans certains réseaux. Adopter une approche légèrement différente de la définition de « communauté » dans le cas des réseaux multidimensionnels permet une identification fiable des communautés sans qu'il soit nécessaire que les nœuds soient en contact direct les uns avec les autres. Par exemple, deux personnes qui ne communiquent jamais directement mais qui naviguent néanmoins sur plusieurs des mêmes sites Web seraient des candidats viables pour ce type d'algorithme.

Une généralisation de la méthode bien connue de maximisation de la modularité pour la découverte de communautés a été initialement proposée par Mucha et al. Cette méthode multirésolution suppose une représentation tensorielle tridimensionnelle de la connectivité du réseau au sein des couches, comme pour les multigraphes à bords colorés, et une représentation tensorielle tridimensionnelle de la connectivité du réseau entre les couches. Elle dépend du paramètre de résolution et du poids des connexions intercouches. Dans une notation plus compacte, utilisant la notation tensorielle, la modularité peut être écrite comme , où , est le tenseur d'adjacence multicouche, est le tenseur codant le modèle nul et la valeur des composants de est définie comme étant 1 lorsqu'un nœud de la couche appartient à une communauté particulière, étiquetée par l'indice , et 0 lorsqu'il ne l'est pas.

La factorisation de matrice non négative a été proposée pour extraire la structure communauté-activité des réseaux temporels. Le réseau multicouche est représenté par un tenseur tridimensionnel , comme un multigraphe à bords colorés, où l'ordre des couches code la flèche du temps. La factorisation de tenseur au moyen de la décomposition de Kruskal est ainsi appliquée pour attribuer chaque nœud à une communauté au fil du temps.

Des méthodes basées sur l'inférence statistique, généralisant les approches existantes introduites pour les réseaux unidimensionnels, ont été proposées. Le modèle de bloc stochastique est le modèle génératif le plus utilisé, généralisé de manière appropriée au cas des réseaux multicouches.

En ce qui concerne les réseaux unidimensionnels, des méthodes fondées sur des principes telles que la longueur de description minimale peuvent être utilisées pour la sélection de modèles dans les méthodes de détection de communauté basées sur le flux d'informations.

Étant donné la complexité plus élevée des réseaux multicouches par rapport aux réseaux unidimensionnels, un domaine de recherche actif est consacré à la simplification de la structure de ces systèmes en utilisant une sorte de réduction de dimensionnalité.

Une méthode populaire est basée sur le calcul de la divergence quantique de Jensen-Shannon entre toutes les paires de couches, qui est ensuite exploitée pour ses propriétés métriques afin de construire une matrice de distance et de regrouper hiérarchiquement les couches. Les couches sont successivement agrégées selon l'arbre hiérarchique résultant et la procédure d'agrégation est arrêtée lorsque la fonction objective , basée sur l' entropie du réseau , obtient un maximum global. Cette approche gourmande est nécessaire car le problème sous-jacent nécessiterait de vérifier tous les groupes de couches possibles de n'importe quelle taille, nécessitant un nombre énorme de combinaisons possibles (qui est donné par le nombre de Bell et évolue de manière super-exponentielle avec le nombre d'unités). Néanmoins, pour les systèmes multicouches avec un petit nombre de couches, il a été démontré que la méthode fonctionne de manière optimale dans la majorité des cas.

La question des corrélations de degré dans les réseaux unidimensionnels est assez simple : les réseaux de degré similaire ont-ils tendance à se connecter les uns aux autres ? Dans les réseaux multidimensionnels, la signification de cette question devient moins claire. Lorsque nous faisons référence au degré d'un nœud, faisons-nous référence à son degré dans une dimension ou à son degré global ? Lorsque nous cherchons à sonder la connectivité entre les nœuds, comparons-nous les mêmes nœuds entre différentes dimensions, ou des nœuds différents au sein des dimensions, ou une combinaison des deux ? Quelles sont les conséquences des variations de chacune de ces statistiques sur d'autres propriétés du réseau ? Dans une étude, il a été constaté que l'assortativité diminuait la robustesse dans un réseau duplex.

Étant donné deux chemins multidimensionnels, r et s , nous disons que r domine s si et seulement si : et tel que .

Parmi les autres statistiques de réseau, de nombreuses mesures de centralité reposent sur la capacité à évaluer les chemins les plus courts d'un nœud à l'autre. L'extension de ces analyses à un réseau multidimensionnel nécessite l'incorporation de connexions supplémentaires entre les nœuds dans les algorithmes actuellement utilisés (par exemple, le algorithme de Dijkstra ). Les approches actuelles incluent la réduction des connexions multi-liens entre les nœuds dans une étape de prétraitement avant d'effectuer des variations sur une recherche en largeur du réseau.

Une façon d'évaluer la distance entre deux nœuds dans un réseau multidimensionnel consiste à comparer tous les chemins multidimensionnels entre eux et à choisir le sous-ensemble que nous définissons comme le plus court via la dominance du chemin : soit l'ensemble de tous les chemins entre et . Alors, la distance entre et est un ensemble de chemins tels que tels que domine . La longueur des éléments dans l'ensemble des chemins les plus courts entre deux nœuds est donc définie comme la distance multidimensionnelle .

Dans un réseau multidimensionnel , la pertinence d'une dimension donnée (ou d'un ensemble de dimensions) pour un nœud peut être évaluée par le ratio : .

Dans un réseau multidimensionnel dans lequel les différentes dimensions de connexion ont des valeurs réelles différentes, les statistiques caractérisant la distribution des liens vers les différentes classes présentent un intérêt. Il est donc utile de considérer deux mesures qui évaluent cela : la connectivité dimensionnelle et la connectivité dimensionnelle exclusive aux bords. La première est simplement le rapport entre le nombre total de liens dans une dimension donnée et le nombre total de liens dans chaque dimension : . La seconde évalue, pour une dimension donnée, le nombre de paires de nœuds connectés uniquement par un lien dans cette dimension : .

Le comportement en rafale est un phénomène bien connu dans de nombreux réseaux du monde réel, par exemple les réseaux de courrier électronique ou d'autres réseaux de communication humaine. Des dimensions supplémentaires de la communication fournissent une représentation plus fidèle de la réalité et peuvent mettre en évidence ces modèles ou les atténuer. Par conséquent, il est d'une importance cruciale que nos méthodes de détection de comportements en rafale dans les réseaux prennent en compte les réseaux multidimensionnels.

Les processus de diffusion sont largement utilisés en physique pour explorer les systèmes physiques, ainsi que dans d'autres disciplines comme les sciences sociales, les neurosciences, les transports urbains et internationaux ou la finance. Récemment, des processus de diffusion simples et plus complexes ont été généralisés aux réseaux multicouches. Un résultat commun à de nombreuses études est que la diffusion dans les réseaux multiplexés, un type particulier de système multicouche, présente deux régimes : 1) le poids des liens inter-couches, reliant les couches entre elles, n'est pas suffisamment élevé et le système multiplexé se comporte comme deux (ou plusieurs) réseaux découplés ; 2) le poids des liens inter-couches est suffisamment élevé pour que les couches soient couplées entre elles, ce qui donne lieu à des phénomènes physiques inattendus. Il a été démontré qu'il existe une transition abrupte entre ces deux régimes.

En fait, tous les descripteurs de réseau dépendant d'un processus de diffusion, des mesures de centralité à la détection de communauté, sont affectés par le couplage couche-couche. Par exemple, dans le cas de la détection de communauté, un faible couplage (où les informations de chaque couche séparément sont plus pertinentes que la structure globale) favorise les clusters au sein des couches, tandis qu'un couplage élevé (où les informations de toutes les couches simultanément sont plus pertinentes que celles de chaque couche séparément) favorise les clusters inter-couches.

Comme pour les réseaux unidimensionnels, il est possible de définir des marches aléatoires au sommet des systèmes multicouches. Cependant, étant donné la structure multicouche sous-jacente, les marcheurs aléatoires ne se limitent pas à se déplacer d'un nœud à un autre au sein de la même couche ( saut ), mais sont également autorisés à se déplacer entre les couches ( commutation ).

Les marches aléatoires peuvent être utilisées pour explorer un système multicouche dans le but ultime de démêler son organisation méso-échelle , c'est-à-dire de le partitionner en communautés , et ont été récemment utilisées pour mieux comprendre la navigabilité des réseaux multicouches et leur résilience aux défaillances aléatoires, ainsi que pour explorer efficacement ce type de topologies.

Dans le cas de systèmes multicouches interconnectés, la probabilité de se déplacer d'un nœud de couche à un autre peut être codée dans le tenseur de transition de rang 4 et la marche en temps discret peut être décrite par l'équation principale

où indique la probabilité de trouver le marcheur dans le nœud de la couche à l'instant .

Il existe de nombreux types de marches différents qui peuvent être codés dans le tenseur de transition , en fonction de la manière dont les marcheurs sont autorisés à sauter et à changer. Par exemple, le marcheur peut sauter ou changer en un seul pas de temps sans faire de distinction entre les liens inter- et intra-couches ( marche aléatoire classique ), ou il peut choisir soit de rester dans la couche actuelle et de sauter, soit de changer de couche puis de sauter vers un autre nœud dans le même pas de temps ( marche aléatoire physique ). Des règles plus compliquées, correspondant à des problèmes spécifiques à résoudre, peuvent être trouvées dans la littérature. Dans certains cas, il est possible de trouver, analytiquement, la solution stationnaire de l'équation principale.

Le problème de la diffusion classique dans les réseaux complexes est de comprendre comment une quantité va circuler à travers le système et combien de temps il faudra pour atteindre l'état stationnaire. La diffusion classique dans les réseaux multiplexés a été récemment étudiée en introduisant le concept de matrice de supra-adjacence, aplatissement spécial du tenseur d'adjacence multicouche. En notation tensorielle, l'équation de diffusion au sommet d'un système multicouche général peut être écrite, de manière concise, comme

où est la quantité de diffusion à l'instant dans le nœud de la couche . Le tenseur de rang 4 qui régit l'équation est le tenseur laplacien, généralisant la matrice laplacienne combinatoire des réseaux unidimensionnels. Il convient de remarquer qu'en notation non tensorielle, l'équation prend une forme plus compliquée.

De nombreuses propriétés de ce processus de diffusion sont parfaitement comprises en termes de la deuxième plus petite valeur propre du tenseur de Laplacie. Il est intéressant de noter que la diffusion dans un système multiplex peut être plus rapide que la diffusion dans chaque couche séparément, ou dans leur agrégation, à condition que certaines propriétés spectrales soient satisfaites.

Récemment, la manière dont l’information (ou les maladies) se propage à travers un système multicouche a fait l’objet de recherches intenses.

Plusieurs logiciels axés sur l'analyse et la visualisation des réseaux multicouches ont été introduits. Parmi les solutions les plus populaires, on trouve multinet (C++ / Python / R), MuxViz (R), Pymnet (Python).