Power graph analysis

[1] 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.

Graphs are drawn with circles or points that represent nodes and lines connecting pairs of nodes that represent edges.

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

First, in Fourier analysis the two spaces (time and frequency domains) are the same function space - but stricto sensu, power graphs are not graphs.

In this example (right) a graph of four nodes and five edges admits two minimal power graphs of two power edges each.

Loss of symmetry is only a problem in small toy examples since complex networks rarely exhibit such symmetries in the first place.

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.

Modules in modular decomposition are groups of nodes in a graph that have identical neighbors.

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.

Also a network of significant disease-trait pairs[4] 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.

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

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