×

Thermodynamic depth in undirected and directed networks. (English) Zbl 1328.05175

Dehmer, Matthias (ed.) et al., Advances in network complexity. Chichester: Wiley-Blackwell (ISBN 978-3-527-33291-5/hbk; 978-3-527-67046-8). Quantitative and Network Biology 4, 229-247 (2013).
Summary: In this paper, we explore how the concept of heat flow can be used to compute the thermodynamic depth complexity of both undirected and directed graphs. We commence with the case of undirected graphs. Here we establish a formal link between network complexity in terms of the Birkhoff-von Neumann decompositions and heat flow complexity. This link is in terms of quantifying the heat flowing through the network at a given time. Based on an analysis of heat flow in a network we derive an important flow characterization theorem. Furthermore, we also show how to define heat flow complexity in terms of thermodynamic depth, which gives a novel means of characterizing networks and quantifying their complexity. With the apparatus for describing and analyzing heat flow complexity in undirected networks to hand, we then explore how it may be extended to directed networks. Our approach consists of (a) analyzing and characterizing heat diffusion traces in directed graphs, and (b) extending the thermodynamic depth framework to capture the second-order variability of the diffusion traces to measure the complexity of directed networks. We provide experiments on real-world problems involving 3D shape analysis and language processing.
For the entire collection see [Zbl 1269.00010].

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
80A10 Classical and relativistic thermodynamics
PDFBibTeX XMLCite
Full Text: DOI