Heat diffusion: thermodynamic depth complexity of networks
Empreu sempre aquest identificador per citar o enllaçar aquest ítem
http://hdl.handle.net/10045/35865
Títol: | Heat diffusion: thermodynamic depth complexity of networks |
---|---|
Autors: | Escolano, Francisco | Hancock, Edwin R. | Lozano, Miguel Angel |
Grups d'investigació o GITE: | Laboratorio de Investigación en Visión Móvil (MVRLab) |
Centre, Departament o Servei: | Universidad de Alicante. Departamento de Ciencia de la Computación e Inteligencia Artificial |
Paraules clau: | Diffusion kernel | Decomposition | Graph complexity | Polytopal measure | Thermodynamic depth |
Àrees de coneixement: | Ciencia de la Computación e Inteligencia Artificial |
Data de publicació: | 14-de març-2012 |
Editor: | American Physical Society |
Citació bibliogràfica: | Phys. Rev. E 85, 036206 (2012) [15 pages]. doi:10.1103/PhysRevE.85.036206 |
Resum: | 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. |
Patrocinadors: | F.E. and M.L. are funded by Project No. TIN2008-04416 of the Spanish Government. E.R.H. is funded by the EU FET Project SIMBAD and a Royal Society Wolfson Research Merit Award. |
URI: | http://hdl.handle.net/10045/35865 |
ISSN: | 1539-3755 (Print) | 1550-2376 (Online) |
DOI: | 10.1103/PhysRevE.85.036206 |
Idioma: | eng |
Tipus: | info:eu-repo/semantics/article |
Drets: | ©2012 American Physical Society |
Revisió científica: | si |
Versió de l'editor: | http://dx.doi.org/10.1103/PhysRevE.85.036206 |
Apareix a la col·lecció: | INV - MVRLab - Artículos de Revistas |
Arxius per aquest ítem:
Arxiu | Descripció | Tamany | Format | |
---|---|---|---|---|
2012_Escolano_etal_PhysRevE.pdf | 1,07 MB | Adobe PDF | Obrir Vista prèvia | |
Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.