122.107.72.26: /* Formal definition */

2013-10-02T00:39:50Z

Formal definition

New page

In [[computational biology]], '''power graph analysis''' is a method for the analysis and
representation of [[complex network]]s. Power graph analysis is the computation, analysis and visual representation of a power graph from a [[Graph (mathematics)|graphs]] ([[network (mathematics)|networks]]).

Power graph analysis can be thought of as a [[Lossless data compression|lossless]] compression algorithm for graphs. It extends graph syntax with representations of [[Clique (graph theory)|cliques]], [[Complete bipartite graph|bicliques]] and [[star graph|stars]]. Compression levels of up to 95% have been obtained for complex biological networks.

[[Hypergraph]]s 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 an using cliques, bicliques and stars as primitives.

==Power graphs==
[[Image:PowerGraphs.png|thumb|The primitive motifs used for power graph analysis and their corresponding diagrammatic representation: biclique, clique and star.]]

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

[[Complete bipartite graph|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.

[[Clique (graph theory)|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 (graph theory)|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 <math>G = \bigl({V,E}\bigr)</math> where <math> V = \bigl\{v_0, \dots , v_n\bigr\} </math> is the set of nodes and <math>E \subseteq V \times V</math> is the set of edges, a '''power graph''' <math>G' = \bigl({V',E'}\bigr)</math> is a graph defined on the power set <math>V' \subseteq \mathcal{P} \bigl(V\bigr)</math> of '''power nodes''' connected to each other by '''power edges''': <math>E' \subseteq V'\times V'</math>. Hence power graphs are defined on the [[power set]] of nodes as well as on the [[power set]] of edges of the graph <math>G</math>.

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 [[Surjective function|onto mapping]] from edges of the original graph to power edges.{{citation needed|date=September 2012}}

==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
<math>t \mapsto x</math> 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 least number of power edges and power nodes necessary to represent a given graph.

==Minimal power graphs==
[[Image:PowerGraphNonUnicity.png|thumb|right|200px|Two different power graphs that represent the same graph.]]
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==
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 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.

==Applications==

===Protein-protein interaction networks===
Power Graph Analysis has been showed to be useful for the analysis of several types of biological networks such as [[Protein-protein interaction]] networks,<ref name="powergraphs"/> domain-peptide binding motifs, [[Gene regulatory networks]]<ref name="mir-124"/> and Homology/Paralogy networks.
Network compression, a new measure derived from Power Graphs, has been proposed as a quality measure for protein interaction networks.<ref name="net_comp"/>

===Drug repositioning===
Power Graphs have been also applied to the analysis of drug-target-disease networks for [[Drug repositioning]].<ref name="inc_bicliques"/>

===Social networks===
Power Graphs have been applied to large-scale data in social networks, for community mining<ref name="lsds"/> or for modeling author types.<ref name="lncs"/>

==See also==
* [[Computational biology]]
* [[network (mathematics)|Networks]]/[[Graph (mathematics)|Graph]]
* [[Complex networks]]
* [[Modular decomposition]]

==References==

{{reflist|refs=
<ref name="powergraphs">
{{cite journal
| author = Royer, Loïc; Reimann, Matthias; Andreopoulos, Bill; Schroeder, Michael;
| title = Unraveling Protein Networks with Power Graph Analysis
| journal = PLoS Computational Biology
| volume = 4
| issue = 7
| date = 11 Jul 2008
| url = http://www.ploscompbiol.org/doi/pcbi.1000108
| pmid=18617988
| pages = e1000108
| doi = 10.1371/journal.pcbi.1000108
| pmc = 2424176
| editor1-last = Berg
| editor1-first = Johannes}}
</ref>
<ref name="inc_bicliques">
{{cite journal
| author1 = Daminelli, Simone
| author2 = Haupt, Joachim V.
| coauthor = Reimann, Matthias; Schroeder, Michael;
| title = Drug repositioning through incomplete bi-cliques in an integrated drug–target–disease network.
| journal = Integrative Biology (Camb.)
| issue = 7
| date = 26 Apr 2012
| url = http://pubs.rsc.org/en/content/articlelanding/2012/ib/c2ib00154c
| pmid= 22538435
| doi = 10.1039/C2IB00154C}}
</ref>
<ref name="net_comp">
{{cite journal
| author = Royer, Loïc; Reimann, Matthias; Stewart, Francis A.; Schroeder, Michael;
| title = Network compression as a quality measure for protein interaction networks.
| journal = Plos One
| volume = 7
| issue = 6
| date = 18 Jun 2012
| url = http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0035729
| pmid= 22719828
| doi = 10.1371/journal.pone.0035729
| pmc = 3377704}}
</ref>
<ref name="mir-124">
{{cite journal
| author = Martina Maisel, Hans-Jörg Habisch, Loïc Royer, Alexander Herr, Javorina Milosevic, Andreas Hermann, Stefan Liebau, Rolf Brenner, Johannes Schwarz, Michael Schroeder, Alexander Storch
| title = Genome-wide expression profiling and functional network analysis upon neuroectodermal conversion of human mesenchymal stem cells suggest HIF-1 and miR-124a as important regulators.
| journal = Experimental Cell Research
| volume = 16
| issue = 17
| date = 15 Oct 2010
| url = http://www.sciencedirect.com/science/article/pii/S0014482710003216
| pmid= 20599952
| doi = 10.1016/j.yexcr.2010.06.012}}
</ref>
<ref name="lncs">
{{cite book
| author = George Tsatsaronis, Iraklis Varlamis, Sunna Torge, Matthias Reimann, Kjetil Nørvåg, Michael Schroeder and Matthias Zschunke
| title = How to Become a Group Leader? or Modeling Author Types Based on Graph Mining
| series = Lecture Notes in Computer Science
| volume = 6966
| year = 2011
| url = http://www.springerlink.com/content/m26570821873lp83/
| doi = 10.1007/978-3-642-24469-8_4
| publisher = SpringerLink}}
</ref>
<ref name="lsds">
{{cite journal
| author = George Tsatsaronis, Matthias Reimann, Iraklis Varlamis, Orestis Gkorgkas, Kjetil Nørvåg
| title = Efficient community detection using power graph analysis
| journal = Proceedings of the 9th workshop on Large-scale and distributed informational retrieval
| year = 2011
| url = http://dl.acm.org/citation.cfm?doid=2064730.2064738
| doi = 10.1145/2064730.2064738 }}
</ref>
}}

==External links==
* [http://www.biotec.tu-dresden.de/research/schroeder/powergraphs/] Power Graph Analysis tools and example applications
* [http://wiki.cytoscape.org/CyOogPowerGraphAnalysisRecipe] Power Graph Analysis with CyOog

[[Category:Computational science]]
[[Category:Bioinformatics]]
[[Category:Graph theory]]

Essential range - Revision history

122.107.72.26: /* Formal definition */