- Access by Xinjiang University
Heat diffusion: Thermodynamic depth complexity of networks
Phys. Rev. E 85, 036206 – Published 14 March, 2012
DOI: https://doi.org/10.1103/PhysRevE.85.036206
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.
Article Text
References (49)
- Network Science: Complexity in Nature and Technology, edited by E. Estrada, N. Fox, and G.-L. O. (Springer, London, 2010).
- A. Torsello and E. Hancock, IEEE TPAMI 28, 954 (2006).
- J. Körner, in Transactions of the Sixth Prague Conference on Information Theory (Academia, Prague, 1973), pp. 411–250.
- G. Simonyi, in Perfect Graphs (John Wiley and Sons, New York, 2001), pp. 293–328.
- F. Passerini and S. Severini, e-print arXiv:0812.2597v1 [cond-mat.dis-nn].
- K. Anand, G. Bianconi, and S. Severini, e-print arXiv:1011.1565v2.
- S. Braunstein, S. Ghosh, and S. Severini, Ann. Combinatorics 10, 291 (2006).
- N. Biggs, Algebraic Graph Theory, Cambridge Tracts in Mathematics No. 67 (Cambridge University Press, Cambridge, 1974).
- D. Bonchev, Information Theoretic Indices for Characterization of Chemical Structures (Research Studies Press, Chichester, 1983).
- D. Bonchev, Complexity in Chemistry. Introduction and Fundamentals (Taylor and Francis, London, 2003).
- M. Dehmer, Appl. Math. Comput. 201, 82 (2008).
- J. Claussen, Physica A 375, 365 (2007).
- D. Feldman and J. Crutchfield, Phys. Lett. A 238, 244 (1998).
- C. H. Bennett, Found. Phys. 16, 585 (1986).
- A. N. Kolmogorov, Prob. Peredachi Inf. 1, 3 (1965).
- G. Chaitin, J. Assoc. Comput. Mach. 13, 547 (1965).
- Pudlák and V. Rödl, Combinatorica 12, 221 (1992).
- S. Jukna, Combinatorics, Probab. Comput. 15, 855 (2006).
- D. Neal and M. Orrison, Electron. J. Combinatorics 15, R9 (2006).
- M. Gell-Mann, Complexity 1, 16 (1995).
- M. Gell-Mann and S. Lloyd, in Non-extensive Entropy: Interdisciplinary Applications (2003), pp. 387–425.
- Y.-Z. Song, P. Arbelaez, P. M. Hall, C. Li, and A. Balikai, in Computer Vision–ECCV 2010, 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5–11, 2010, Proceedings, Part IV, edited by Kostas Daniilidis, Petros Maragos, and Nikos Paragios, Vol. 6314 (Springer, 2010), pp. 694–707.
- I. Gutman and B. Zhou, Lin. Alg. Appl. 414, 29 (2006).
- E. Estrada, Phys. Rev. E 82, 066102 (2010).
- S. Lloyd and H. Pagels, Ann. Phys. 188, 186 (1988).
- B. Machta and J. Machta, Phys. Rev. E 71, 026704 (2005).
- J. Machta, Complexity J. 5, 46 (2006).
- J. P. Crutchfield and C. R. Shalizi, Phys. Rev. E 59, 275 (1999).
- G. D. Birkhoff, Univ. Nacional Tucuman Rev., Ser. A 5, 147 (1946).
- R. I. Kondor and J. D. Lafferty, in Machine Learning, Proceedings of the Nineteenth International Conference (ICML 2002), University of New South Wales, Sydney, Australia, July 8–12, 2002, edited by C. Sammut and A. G. Hoffmann (Morgan Kaufmann, 2002), pp. 315–322.
- F. Escolano, E. R. Hancock, and M. A. Lozano, in 19th International Conference on Pattern Recognition (ICPR 2008), December 8–11, 2008, Tampa, Florida, USA (IEEE, 2008), pp. 1–5.
- F. Escolano, E. Hancock, and M. Lozano, in SSPR/SPR (2008), pp. 237–246.
- H. Minc, in Encyclopedia of Mathematics and its Applications, Vol. 6 (Addison-Wesley, Reading, MA, 1978).
- G. Egorychev, Adv. Math. 42, 299 (1981).
- L. G. Valiant, Theor. Comput. Sci. 8, 189 (1979).
- K. Mulmuley, J. ACM 58, 5 (2011).
- M. Jerrum, A. Sinclair, and E. Vigoda, J. Assoc. Comput. Mach. 51, 671 (2004).
- P. B. Slater, Environ. Planning 21, 1541 (1989).
- H. Qiu and E. Hancock, Pattern Recognit. 40, 2874 (2007).
- S. Agrawal, Z. Wang, and Y. Ye, in WINE, edited by C. Papadimitriou and S. Zhang (Springer-Verlag, Berlin, Heidelberg, 2008), pp. 126–137.
- R. Nock and F. Nielsen, in ECML, edited by J. Gama, R. Camacho, P. Brazdil, A. Jorge, and L. Torgo (Springer, 2005), pp. 649–656.
- I. W. Tsang, A. Kocsor, and J. T. Kwok, in ICML, edited by Z. Ghahramani (ACM, 2007), pp. 911–918.
- L. Cayton, in ICML, edited by W. W. Cohen, A. McCallum, and S. T. Roweis (ACM, 2008), pp. 112–119.
- L. Jensen, M. Kuhn, M. Stark, S. Chaffron, C. Creevey, J. Muller, T. Doerks, P. Mullien, A. Roth, M. Simonovic, P. Bork, and C. von Mering, Nucleic Acids Res. 37, D412 (2009).
- E. Estrada, Europhys. Lett. 73, 649 (2006).
- S. B. C.R. Kuske and J. Bush, Appl. Environ. Microbiol. 63, 3614 (1997).
- P. H. M. Sait and P. Janssen, Environ. Microbiol. 4, 654 (2002).
- F. Ciccarelli, F. Doerks, C. von Mering, C. Creevey, B. Snell, and P. Bork, Science 311, 1283 (2006).
- M. Wu and J. Eisen, Genome Biol. 9, R151 (2008).