Power graph analysis

In computational biology, power graph analysis is a method for the analysis andrepresentation of complex networks. Power graph analysis is the computation, analysis and visual representation of a power graph from a graph (networks). In computational biology, power graph analysis is a method for the analysis andrepresentation 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. 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 G = ( V , E ) {displaystyle G={igl (}{V,E}{igr )}} where V = { v 0 , … , v n } {displaystyle V={igl {}v_{0},dots ,v_{n}{igr }}} is the set of nodes and E ⊆ V × V {displaystyle Esubseteq V imes V} is the set of edges, a power graph G ′ = ( V ′ , E ′ ) {displaystyle G'={igl (}{V',E'}{igr )}} is a graph defined on the power set V ′ ⊆ P ( V ) {displaystyle V'subseteq {mathcal {P}}{igl (}V{igr )}} of power nodes connected to each other by power edges: E ′ ⊆ V ′ × V ′ {displaystyle E'subseteq V' imes 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} .