Heat diffusion: Thermodynamic depth complexity of networks

Francisco Escolano, Edwin R. Hancock, and Miguel A. Lozano

Phys. Rev. E 85, 036206 – Published 14 March 2012

Abstract

In this paper we use the Birkhoff–von Neumann decomposition of the diffusion kernel to compute a polytopal measure of graph complexity. We decompose the diffusion kernel into a series of weighted Birkhoff combinations and compute the entropy associated with the weighting proportions (polytopal complexity). The maximum entropy Birkhoff combination can be expressed in terms of matrix permanents. This allows us to introduce a phase-transition principle that links our definition of polytopal complexity to the heat flowing through the network at a given diffusion time. The result is an efficiently computed complexity measure, which we refer to as flow complexity. Moreover, the flow complexity measure allows us to analyze graphs and networks in terms of the thermodynamic depth. We compare our method with three alternative methods described in the literature (Estrada's heterogeneity index, the Laplacian energy, and the von Neumann entropy). Our study is based on 217 protein-protein interaction (PPI) networks including histidine kinases from several species of bacteria. We find a correlation between structural complexity and phylogeny (more evolved species have statistically more complex PPIs). Although our methods outperform the alternatives, we find similarities with Estrada's heterogeneity index in terms of network size independence and predictive power.

Received 22 September 2011

DOI:https://doi.org/10.1103/PhysRevE.85.036206

Authors & Affiliations

Francisco Escolano^*

University of Alicante, Alicante, Spain

Edwin R. Hancock^†

University of York, York, United Kingdom

Miguel A. Lozano^‡

University of Alicante, Alicante, Spain

^*sco@dccia.ua.es
^†erh@cs.york.ac.uk
^‡malozano@dccia.ua.es

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 85, Iss. 3 — March 2012

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Heat kernel–thermodynamic depth complexities for graphs of $| V | = 10$ . From top to bottom and left to right, Gauss10, Grid8N10, Grid4N10, Line10, and Circle10 graphs.Reuse & Permissions
Figure 2
Diffusion process in a linear graph with $n = 100$ nodes. The horizontal axes are assigned to nodes $1, ..., n$ (therefore the horizontal plane represents the adjacency matrix). Snapshots taken at $β = 0.64$ , 100, 1000, and 6070 (top left to bottom right). The vertical axis represents the value of the kernel at a given point. In each case lighter gray means higher $K_{β_{i j}}$ . In all cases the kernel overlays a contour plot. Extreme nodes (1 and 100) lose less heat than the rest of the nodes. As $β > 0.64$ increases, the closer the nodes are to the extremes the less heat they lose. The true value of $β_{max}$ is $10 717$ , which gives an idea of the slow convergence of the diffusion process. In terms of flow we have $F_{β = 0.64} = 43.274$ , $F_{β = 100} = 6.5185$ , and $F_{β = 1000} = 2.7483$ . For $F_{β = 6070} = 1.9849$ we are close to the equilibriumflow [ $(2 \times 99) / 100 = 1.9800$ ].Reuse & Permissions
Figure 3
Computing heat flow and thermodynamic depth for a four-connected grid graph of $n = 25$ nodes. Left column: expansion subgraphs and node histories at nodes 1 (top), 11 (middle), and 13 (bottom); in each case we show the first-order expansion subgraph in black, the next one in dark gray, and so on. Center column: Minimum enclosing Bregman balls for the histories of these nodes with their radii; in each case, the center of the ball (in bold) and the boundaries (given by the support vectors) are heat flow complexity traces inferred from the corresponding node history. Right column, top: projecting $f^{\infty}$ (van der Waerden trace) on the Bregman ball given by the centers of all the $n = 25$ balls. Right column, bottom: plot of Bregman ball radii (BB $r$ ) corresponding to all node histories; symmetry is given by the structure and the maximal radii correspond to nodes 1, 5, $21,$ and 25 (the four corners).Reuse & Permissions
Figure 4
PPI examples for protein histidine kinase. From top left to bottom right: Aquifex (hksP2, 207 nodes, $TD = 57.8926$ ), Thermotoga (TM_0127, 201 nodes, $TD = 69.2323$ ), Gram positive (SaurJH1_1973, 186 nodes, $TD = 85.6689$ ), Cyanobacteria (Ava_0062, 224 nodes, $TD = 4.6383$ ), Proteobacteria (Aave_0867, 202 nodes, $TD = 58.3774$ ), and Acidobacteria (Acid345_0474, 136 nodes, $TD = 618.1457$ ).Reuse & Permissions
Figure 5
Cumulatives for heat flow (top left), Estrada's heterogeneity (top right), Laplacian energy (bottom left), and von Neumann entropy (bottom right).Reuse & Permissions
Figure 6
Network size vs complexity ln-ln plots for heat flow (top left), Estrada's heterogeneity (top right), Laplacian energy (bottom left), and von Neumann entropy (bottom right). In all cases the natural logarithm is used.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics