Power graph analysis

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 graphs (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 a 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 = igl({V,E}igr) where V = igl{v_0, dots , v_nigr} is the set of nodes and E subseteq V imes V is the set of edges, a power graph G' = igl({V',E'}igr) is a graph defined on the power set V' subseteq mathcal{P} igl(Vigr) of power nodes connected to each other by power edges: 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.

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.Verify source|date=July 2008

Analogy to Fourier analysis

The Fourier analysis of a functioncan be seen as a rewriting of the function in terms of harmonic functions instead oft->x pairs. This transformation changes the point of view from time domainto 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 starsas 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 an unique power graph representing a given graph. Yet a very interesting class of power graphs are minimal power graphs which have the least number of power edges and power nodes necessary to represent a given graph.

Minimal power graphs


right|200px">
In general, a graph can have several minimal power graphs. A minimal power graph is such that there is no other power graph for the same graph that has strictly less power edges or power nodes.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.

Power graph greedy algorithm

[


right|360px
The two steps for computing a near minimal power graph: search for candidate power nodes using hierarchical clustering, and the greedy search for power edges representing cliques and bicliques.] 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

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 thathave 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.

Applications

Power Graph Analysis 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

cite journal
last = Loic Royer
first = Matthias Reimann
coauthors = Bill Andreopoulos, and Michael Schroeder
title = Unraveling protein networks with Power Graph Analysis
journal = PLoS Computational Biology
volume = 4
issue = 7
date = 2008-07-11
url = http://www.ploscompbiol.org/doi/pcbi.1000108
format = PDF

ee also

* Computational biology
* Networks/Graph
* Complex networks
* Modular decomposition

External links

* [http://www.biotec.tu-dresden.de/schroeder/group/powergraphs] Power Graph Analysis tools and example applications
* [http://www.ploscompbiol.org/doi/pcbi.1000108] Power graph Analysis paper published in PLoS Computational Biology


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

  • analysis — /euh nal euh sis/, n., pl. analyses / seez /. 1. the separating of any material or abstract entity into its constituent elements (opposed to synthesis). 2. this process as a method of studying the nature of something or of determining its… …   Universalium

  • Bond graph — A bond graph is a graphical description of a physical dynamic system. It is an energy based graphical technique for building mathematical models of dynamic systems. A bond graph depicts the energy flow between components used to model a system.… …   Wikipedia

  • Detrended fluctuation analysis — In stochastic processes, chaos theory and time series analysis, detrended fluctuation analysis (DFA) is a method for determining the statistical self affinity of a signal. It is useful for analysing time series that appear to be long memory… …   Wikipedia

  • Oxford Capacity Analysis — This article is about the Church of Scientology personality test. For other uses, see Oxford (disambiguation). Sign advertising Scientology personality tests. San Francisco, April 2006. The Oxford Capacity Analysis (OCA), also known as the… …   Wikipedia

  • Nuclear power — Atomic Power redirects here. For the film, see Atomic Power (film). This article is about the power source. For nation states that are nuclear powers, see List of states with nuclear weapons …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

  • Periodic graph (crystallography) — For other uses, see Periodic graph. A (large) unit cell of Diamond crystal net; the balls represent carbon atoms and the sticks represent covalent bonds …   Wikipedia

  • Mathematical analysis — Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”