Power graph analysis

In Computational Biology, Power Graph Analysis is a method developed for the analysis and representation of complex networks. Power Graph Analysis is the computation, analysis and visual representation of power graphs from graphs (networks).

Given a graph $G={\bigl (}{V,E}{\bigr )}$ where $V$ is the set of nodes and $E\subseteq V\times V$ is the set of edges, a power graph $G'={\bigl (}{V',E'}{\bigr )}$ is a graph defined on the power set $V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}$ of power nodes connected to each other by power edges: $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 $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 for simplifying the representations:

• Power node hierarchy condition: Any two power nodes are either disjoint, or one is included in the other.
• Power edge disjointness condition: Each node of the original graph is represented by one and only one power edge.

Power graph analysis is essentially a compression algorithm for graphs that has several interesting properties:

• It is a loss-less and thus reversible transformation.
• The result of the transformation, a power graph, can be simply represented as a power graph diagram.
• Explicitly represents cliques and bicliques within the network as they constitute the primitive elements for the decomposition.
• Has been showed 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.

References

ichael Schroeder, Loic Royer (1999-06-25). "Unraveling protein networks with Power Graph Analysis" (PDF). PLoS Computational Biology. 19 (1). Berlin: Springer-Verlag: 50–57. {{cite journal}}: Check date values in: |date= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)

See also

• Computational Biology
• networks
• complex networks
• Modular Decomposition

External links

• [1] Power Graph Analysis tools and example applications
• [2] Power graph Analysis paper published in PLoS Computational Biology