HOME

TheInfoList



OR:

In
computational biology Computational biology refers to the use of data analysis, mathematical modeling and Computer simulation, computational simulations to understand biological systems and relationships. An intersection of computer science, biology, and big data, the ...
, power graph analysis is a method for the analysis and representation of
complex network In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real ...
s. Power graph analysis is the computation, analysis and visual representation of a power graph from a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
(
networks Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...
). Power graph analysis can be thought of as a lossless compression algorithm for graphs. It extends graph syntax with representations of
cliques A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
, bicliques and
stars A star is an astronomical object comprising a luminous spheroid of plasma held together by its gravity. The nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night, but their immense distances from Earth ma ...
. Compression levels of up to 95% have been obtained for complex
biological network A biological network is a method of representing systems as complex sets of binary interactions or relations between various biological entities. In general, networks or graphs are used to capture relationships between entities or objects. A typi ...
s.
Hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) w ...
s are a generalization of graphs in which
edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed ...
s are not just couples of
node In general, a node is a localized swelling (a " knot") or a point of intersection (a vertex). Node may refer to: In mathematics * Vertex (graph theory), a vertex in a mathematical graph * Vertex (geometry), a point where two or more curves, line ...
s but arbitrary
n-tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s. 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 A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
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 Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...
.
Star A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...
s 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 = \bigl(\bigr) where V = \bigl\ is the set of nodes and E \subseteq V \times V is the set of edges, a power graph G' = \bigl(\bigr) is a graph defined on the power set V' \subseteq \mathcal \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 In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
of nodes as well as on the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
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.


Analogy to Fourier analysis

The
Fourier analysis In mathematics, Fourier analysis () is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph ...
of a function can be seen as a rewriting of the function in terms of harmonic functions instead of 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 Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, di ...
,
data compression In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressio ...
, 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.


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 In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into t ...
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 In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A ''module'' is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a p ...
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 Complex Networks is an American media and entertainment company for youth culture, based in New York City. It was founded as a bi-monthly magazine, ''Complex'', by fashion designer Marc (Ecko) Milecofsky. Complex Networks reports on popular ...
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


Biological networks

Power graph analysis has been shown 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 A gene (or genetic) regulatory network (GRN) is a collection of molecular regulators that interact with each other and with other substances in the cell to govern the gene expression levels of mRNA and proteins which, in turn, determine the fun ...
and homology/paralogy networks. Also a network of significant disease-trait pairs have been recently visualized and analyzed with power graphs. Network compression, a new measure derived from power graphs, has been proposed as a quality measure for protein interaction networks.


Drug repositioning

Power graphs have been also applied to the analysis of drug-target-disease networks for drug repositioning.


Social networks

Power graphs have been applied to large-scale data in social networks, for community mining or for modeling author types.


See also

*
Computational biology Computational biology refers to the use of data analysis, mathematical modeling and Computer simulation, computational simulations to understand biological systems and relationships. An intersection of computer science, biology, and big data, the ...
*
Networks Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...
/
Graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
*
Complex networks Complex Networks is an American media and entertainment company for youth culture, based in New York City. It was founded as a bi-monthly magazine, ''Complex'', by fashion designer Marc (Ecko) Milecofsky. Complex Networks reports on popular ...
*
Modular decomposition In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A ''module'' is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a p ...


References

{{reflist, refs= {{cite journal , author=Royer, Loïc , author2=Reimann, Matthias , author3=Andreopoulos, Bill , author4=Schroeder, Michael , title = Unraveling Protein Networks with Power Graph Analysis , journal = PLOS Computational Biology , volume = 4 , issue = 7 , date = 11 Jul 2008 , pmid=18617988 , pages = e1000108 , doi = 10.1371/journal.pcbi.1000108 , pmc = 2424176 , editor1-last = Berg , editor1-first = Johannes, bibcode=2008PLSCB...4E0108R {{cite journal , author1 = Daminelli, Simone , author2 = Haupt, Joachim V. , author3=Reimann, Matthias , author4=Schroeder, Michael , title = Drug repositioning through incomplete bi-cliques in an integrated drug–target–disease network. , journal = Integrative Biology , issue = 7 , date = 26 Apr 2012 , url = http://pubs.rsc.org/en/content/articlelanding/2012/ib/c2ib00154c , pmid= 22538435 , doi = 10.1039/C2IB00154C , volume=4 , pages=778–88 {{cite journal , author1=Royer, Loïc , author2=Reimann, Matthias , author3=Stewart, Francis A. , author4=Schroeder, Michael , title = Network compression as a quality measure for protein interaction networks. , journal = PLOS ONE , volume = 7 , issue = 6 , date = 18 Jun 2012 , pmid= 22719828 , doi = 10.1371/journal.pone.0035729 , pmc = 3377704 , page=e35729, bibcode=2012PLoSO...735729R , doi-access=free {{cite journal , author1=Martina Maisel , author2=Hans-Jörg Habisch , author3=Loïc Royer , author4=Alexander Herr , author5=Javorina Milosevic , author6=Andreas Hermann , author7=Stefan Liebau , author8=Rolf Brenner , author9=Johannes Schwarz , author10=Michael Schroeder , author11=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 = 316 , issue = 17 , date = 15 Oct 2010 , pmid= 20599952 , doi = 10.1016/j.yexcr.2010.06.012 , pages=2760–78 {{cite book , author1=George Tsatsaronis , author2=Iraklis Varlamis , author3=Sunna Torge , author4=Matthias Reimann , author5=Kjetil Nørvåg , author6=Michael Schroeder , author7=Matthias Zschunke , title = Research and Advanced Technology for Digital Libraries: International Conference on Theory and Practice of Digital Libraries, TPDL , chapter = How to Become a Group Leader? or Modeling Author Types Based on Graph Mining , series = Lecture Notes in Computer Science , volume = 6966 , pages=15–26 , year = 2011 , doi = 10.1007/978-3-642-24469-8_4 , publisher = SpringerLink, isbn=978-3-642-24468-1 , citeseerx=10.1.1.299.714 {{cite book , author1=George Tsatsaronis , author2=Matthias Reimann , author3=Iraklis Varlamis , author4=Orestis Gkorgkas , author5=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 , pages=21–26 , year = 2011 , doi = 10.1145/2064730.2064738 , isbn=9781450309592 , series=Lsds-Ir '11 , s2cid=10224386 {{cite journal , author1 = Li, Li , author2 = Ruau, David J. , author3=Patel, Chirag J. , author4=Weber, Susan C. , author5=Chen, Rong , author6=Tatonetti, Nicholas P. , author7=Dudley, Joel T. , author8=Butte, Atul J. , title = Disease Risk Factors Identified Through Shared Genetic Architecture and Electronic Medical Records , journal = Sci. Transl. Med. , volume = 6 , issue = 234 , date = 30 April 2014 , pmid= 24786325 , doi = 10.1126/scitranslmed.3007191 , pages=234ra57 , pmc=4323098 {{cite book , author1=Matthias Reimann , author2=Loïc Royer , author3=Simone Daminelli , author4=Michael Schroeder , title = Computational Network Theory: Theoretical Foundations and Applications , series = Quantitative and Network Biology Series , volume = 5 , year = 2015 , url = http://eu.wiley.com/WileyCDA/WileyTitle/productCd-3527337245,subjectCd-MA21.html , isbn = 978-3-527-33724-8 , editor=Matthias Dehmer , editor2=Frank Emmert-Streib , editor3=Stefan Pickl , publisher = Wiley-Blackwell


External links



Power Graph Analysis tools (CyOog v2.8.2) and example applications

Power Graph Analysis with CyOog v2.6 Computational science Bioinformatics Application-specific graphs