Power graph analysis
In computational biology, power graph analysis is a method for the analysis and representation of complex networks. Power graph analysis is the computation, analysis and visual representation of a power graph from a graph (networks).
Power graph analysis can be thought of as a lossless compression algorithm for graphs. It extends graph syntax with representations of cliques, bicliques and stars. Compression levels of up to 95% have been obtained for complex biological networks.
Hypergraphs are a generalization of graphs in which edges are not just couples of nodes but arbitrary n-tuples. Power graphs are not another generalization of graphs, but instead a novel representation of graphs that proposes a shift from the "node and edge" language to one using cliques, bicliques and stars as primitives.
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.
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.
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.
In general, there is no unique minimal power graph for a given graph. In this example (right) a graph of four nodes and five edges admits two minimal power graphs of two power edges each. The main difference between these two minimal power graphs is the higher nesting level of the second power graph as well as a loss of symmetry with respect to the underlying graph. Loss of symmetry is only a problem in small toy examples since complex networks rarely exhibit such symmetries in the first place. Additionally, one can minimize the nesting level but even then, there is in general not a unique minimal power graph of minimal nesting level.
The power graph greedy algorithm relies on two simple steps to perform the decomposition:
The first step identifies candidate power nodes through a hierarchical clustering of the nodes in the network based on the similarity of their neighboring nodes. The similarity of two sets of neighbors is taken as the Jaccard index of the two sets.
The second step performs a greedy search for possible power edges between candidate power nodes. Power edges abstracting the most edges in the original network are added first to the power graph. Thus bicliques, cliques and stars are incrementally replaced with power edges, until all remaining single edges are also added. Candidate power nodes that are not the end point of any power edge are ignored.
Modular decomposition can be used to compute a power graph by using the strong modules of the modular decomposition. Modules in modular decomposition are groups of nodes in a graph that have identical neighbors. A Strong Module is a module that does not overlap with another module. However, in complex networks strong modules are more the exception than the rule. Therefore, the power graphs obtained through modular decomposition are far from minimality. The main difference between modular decomposition and power graph analysis is the emphasis of power graph analysis in decomposing graphs not only using modules of nodes but also modules of edges (cliques, bicliques). Indeed, power graph analysis can be seen as a loss-less simultaneous clustering of both nodes and 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, domain-peptide binding motifs, Gene regulatory networks and Homology/Paralogy networks. Also a network of significant disease-trait pairs 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.