Analyse en graphe de puissance

En biologie computationnelle, l'analyse en graphes de puissance est une méthode d'analyse et de représentation de réseaux complexes. Cette méthode regroupe le calcul, l'analyse et la représentation visuelle d'un graphe de puissance à partir d'un graphe (réseaux). L'analyse en graphe de puissance est une forme d'algorithme de compression sans perte sur les graphes. Il s'agit en pratique d'étendre la syntaxe des graphes fin de représenter les cliques, les bicliques et les étoiles de manière efficace. Des niveaux de compression allant jusqu'à 95 % ont été obtenus pour des réseaux biologiques complexes. Les hypergraphes sont une généralisation des graphes dans lesquels les arêtes ne sont pas seulement des couples de nœuds mais des n-uplets arbitraires. Les graphes de puissance ne sont pas une autre généralisation des graphes, mais plutôt une nouvelle représentation des graphes qui propose un passage du langage « nœuds et liens » à un langage utilisant des cliques, des bicliques et des étoiles comme primitives. Traditionnellement, les graphes sont dessinés avec des cercles ou des points qui représentent des nœuds et des lignes reliant des paires de nœuds qui représentent des arêtes . Pour leur part, les graphes de puissance étendent la syntaxe des graphes avec des nœuds de puissance, qui sont dessinés comme un cercle englobant des nœuds (ou dautres nœuds de puissance), et des arêtes de puissance, qui sont des lignes entre les nœuds de puissance. Soit un graphe où dénote l'ensemble des nœuds et l'ensemble des liens. Une clique est un ensemble de nœuds entièrement reliés. C'est-à-dire que est une clique si : Dans un graphe de puissance, une clique est représentée par un nœud de puissance avec une boucle. Les bicliques sont deux ensembles de nœuds avec un bord entre chaque membre d'un ensemble et chaque membre de l'autre ensemble. C'est-à-dire que et forment une biclique si : Dans un graphe de puissance, une biclique est représentée comme une arête entre deux nœuds de puissance.