Analyse en graphe de puissance

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 d'autres nœuds de puissance), et des arêtes de puissance, qui sont des lignes entre les nœuds de puissance.

Soit un graphe ${\displaystyle G=(V,E)}$ où ${\displaystyle V}$ dénote l'ensemble des nœuds et ${\displaystyle E\subset V\times V}$ l'ensemble des liens.

Une clique est un ensemble de nœuds entièrement reliés. C'est-à-dire que ${\displaystyle C\subset V}$ est une clique si :

${\displaystyle \forall a,b\in C,(a,b)\in E}$

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 ${\displaystyle A}$ et ${\displaystyle B}$ forment une biclique si :

${\displaystyle \forall a\in A,\forall b\in B,(a,b)\in E}$

Dans un graphe de puissance, une biclique est représentée comme une arête entre deux nœuds de puissance.

Les étoiles sont un ensemble de nœuds avec un bord entre chaque membre de cet ensemble et un seul nœud à l'extérieur de l'ensemble. (Autrement dit, une biclique dont l'un des deux ensembles est un singleton.) Dans un graphe de puissance, une étoile est représentée par une arête de puissance entre un nœud régulier et un nœud de puissance.

Étant donné un graphique ${\displaystyle G={\bigl (}{V,E}{\bigr )}}$ où ${\displaystyle V={\bigl \{}v_{0},\dots ,v_{n}{\bigr \}}}$ est l'ensemble des nœuds et ${\displaystyle E\subseteq V\times V}$ est l'ensemble des arêtes, un graphe de puissance ${\displaystyle G'={\bigl (}{V',E'}{\bigr )}}$ est un graphe défini sur l'ensemble de puissance ${\displaystyle V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}}$ de nœuds de puissance connectés entre eux par des liens de puissance : ${\displaystyle E'\subseteq V'\times V'}$. Les graphes de puissance sont ainsi définis sur l'ensemble de puissance des nœuds ainsi que sur l'ensemble de puissance des arêtes du graphe ${\displaystyle G}$.

La sémantique des graphes de puissance est la suivante : si deux nœuds de puissance sont connectés par une arête de puissance, cela signifie que tous les nœuds du premier nœud de puissance sont connectés à tous les nœuds du deuxième nœud de puissance. De même, si un nœud de puissance est connecté à lui-même par un bord de puissance (i.e. une boucle), cela signifie que tous les nœuds du nœud de puissance sont connectés les uns aux autres par des bords.

Les deux conditions suivantes sont requises :

• Hiérarchie des nœuds de puissance : deux nœuds de puissance sont soit disjoints, soit l'un est inclus dans l'autre.
• Disjonction des arêtes de puissance : il existe une surjection des arêtes du graphe d'origine vers les arêtes de puissance.

L'analyse en graphe de puissance s'est avérée utile pour l'analyse de plusieurs types de réseaux biologiques tels que les réseaux d' interaction protéine-protéine les motifs de liaison domaine-peptide, les réseaux de régulation génétique et les réseaux d'homologie/paralogie. De plus, un réseau de paires maladie-trait intéressants a été récemment visualisé et analysé avec des graphes de puissance.

La compression de réseau, une nouvelle mesure dérivée des graphes de puissance, a été proposée comme mesure de qualité pour les réseaux d'interaction protéique.

Les graphes de puissances ont également été appliqués à l'analyse des réseaux médicament-cible-maladie pour le repositionnement des médicaments .

Les graphes de puissance ont été appliqués à des données à grande échelle dans les réseaux sociaux, pour la détection de communauté ou pour la modélisation de types d'auteurs.

• Électroencéphalographie quantitative
• Biologie computationnelle
• Réseaux / Graphique
• Réseaux complexes