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.
Power graphs
Graphical representation 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.
Formal definition Given a graph G = ( V , E ) {\displaystyle G={\bigl (}{V,E}{\bigr )}} where V = { v 0 , … , v n } {\displaystyle V={\bigl \{}v_{0},\dots ,v_{n}{\bigr \}}} is the set of nodes and E ⊆ V × V {\displaystyle E\subseteq V\times V} is the set of edges, a power graph G ′ = ( V ′ , E ′ ) {\displaystyle G'={\bigl (}{V',E'}{\bigr )}} is a graph defined on the power set V ′ ⊆ P ( V ) {\displaystyle V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}} of power nodes connected to each other by power edges: E ′ ⊆ V ′ × V ′ {\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 G {\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.
Analogy to Fourier analysis The Fourier analysis of a function can be seen as a rewriting of the function in terms of harmonic functions instead of
t ↦ x {\displaystyle t\mapsto x} pairs. This transformation changes the point of view from time domain to frequency domain and enables many interesting applications in signal analysis, data compression, and filtering. Similarly, Power graph analysis is a rewriting or decomposition of a network using bicliques, cliques and stars as primitive elements (just as harmonic functions for Fourier analysis). It can be used to analyze, compress and filter networks. There are, however, several key differences. First, in Fourier analysis the two spaces (time and frequency domains) are the same function space - but stricto sensu, power graphs are not graphs. Second, there is not a unique power graph representing a given graph. Yet a very interesting class of power graphs are minimal power graphs which have the fewest power edges and power nodes necessary to represent a given graph.
Minimal power graphs
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.
… excerpt ends here. Continue reading the full article.
