Power graph analysis

Graphs are drawn with circles or points that represent nodes and lines connecting pairs of nodes that represent edges. Power graphs extend the syntax of graphs with power nodes, which are drawn as a circle enclosing nodes or other power nodes, and power edges, which are lines between power nodes.

Bicliques are two sets of nodes with an edge between every member of one set and every member of the other set. In a power graph, a biclique is represented as an edge between two power nodes.

Cliques are a set of nodes with an edge between every pair of nodes. In a power graph, a clique is represented by a power node with a loop.

Stars are a set of nodes with an edge between every member of that set and a single node outside the set. In a power graph, a star is represented by a power edge between a regular node and a power node.

Given a graph ${\displaystyle G={\bigl (}{V,E}{\bigr )}}$ where ${\displaystyle V={\bigl \{}v_{0},\dots ,v_{n}{\bigr \}}}$ is the set of nodes and ${\displaystyle E\subseteq V\times V}$ is the set of edges, a power graph ${\displaystyle G'={\bigl (}{V',E'}{\bigr )}}$ is a graph defined on the power set ${\displaystyle V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}}$ of power nodes connected to each other by power edges: ${\displaystyle E'\subseteq V'\times V'}$. Hence power graphs are defined on the power set of nodes as well as on the power set of edges of the graph ${\displaystyle G}$.

The semantics of power graphs are as follows: if two power nodes are connected by a power edge, this means that all nodes of the first power node are connected to all nodes of the second power node. Similarly, if a power node is connected to itself by a power edge, this signifies that all nodes in the power node are connected to each other by edges.

The following two conditions are required:

• Power node hierarchy condition: Any two power nodes are either disjoint, or one is included in the other.
• Power edge disjointness condition: There is an onto mapping from edges of the original graph to power edges.

Power graph analysis has been shown to be useful for the analysis of several types of biological networks such as protein-protein interaction networks,[2] domain-peptide binding motifs, gene regulatory networks[3] and homology/paralogy networks. Also a network of significant disease-trait pairs[4] have been recently visualized and analyzed with power graphs.

Network compression, a new measure derived from power graphs, has been proposed as a quality measure for protein interaction networks.[5]

Power graphs have been also applied to the analysis of drug-target-disease networks[6] for drug repositioning.

Power graphs have been applied to large-scale data in social networks, for community mining[7] or for modeling author types.[8]