Abstract
In this paper we extend the heat diffusion-thermodynamic depth approach for undirected networks/graphs to directed graphs. This extension is motivated by the need to measure the complexity of structural patterns encoded by directed graphs. It consists of: a) analyzing and characterizing heat diffusion traces in directed graphs, b) extending the thermodynamic depth framework to capture the second-order variability of the diffusion traces to measure the complexity of directed networks. In our experiments we characterize several directed networks derived from different natural languages. We show that our proposed extension finds differences between languages that are blind to the classical analysis of degree distributions.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Escolano, F., Suau, P., Bonev, B.: Information Theory in Computer Vision and Pattern Recognition. Springer, London (2009)
Torsello, A., Hancock, E.R.: Learning Shape-Classes Using a Mixture of Tree-Unions. IEEE Tran. on Pattern Analysis and Mach. Intelligence 28(6), 954–967 (2006)
Torsello, A., Lowe, D.L.: Supervised Learning of a Generative Model for Edge-Weighted Graphs. In: Proc. of ICPR (2008)
Körner, J.: Coding of an Information Source Having Ambiguous Alphabet and the Entropy of Graphs. In: Transactions of of the 6th Prague Conference on Information Theory, pp. 411–425 (1973)
Passerini, F., Severini, S.: The von Neumann Entropy of Networks. arXiv:0812.2597v1 (December 2008)
Han, L., Escolano, F., Hancock, E.R., Wilson, R.: Graph Characterizations From Von Neumann Entropy. Pattern Recognition Letters (in press, 2012)
Feldman, D.P., Crutchfield, J.P.: Measures of Statistical Complexity: Why? Physics Letters A 238(4-5), 244–252 (1998)
Estrada, E.: Quantifying Network Heterogeneity. Phys. Rev. E 82, 066102 (2010)
Randić, M.: Characterization of Molecular Branching. Journal of the American Chemical Society 97(23), 6609–6615 (1975)
Lloyd, S., Pagels, H.: Complexity as Thermodynamic Depth Ann. Phys. 188, 186 (1988)
Escolano, F., Hancock, E.R., Lozano, M.A.: Heat Diffusion: Thermodynamic Depth Complexity of Networks. Phys. Rev. E 85, 036206 (2012)
Escolano, F., Lozano, M.A., Hancock, E.R., Giorgi, D.: What Is the Complexity of a Network? The Heat Flow-Thermodynamic Depth Approach. In: Hancock, E.R., Wilson, R.C., Windeatt, T., Ulusoy, I., Escolano, F. (eds.) SSPR&SPR 2010. LNCS, vol. 6218, pp. 286–295. Springer, Heidelberg (2010)
Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank Citation Ranking: Bring Order to the Web (Technical Report). Stanford University (1998)
Chung, F.: Laplacians and the Cheeger Inequailty for Directed Graphs. Annals of Combinatorics 9, 1–19 (2005)
Johns, J., Mahadevan, S.: Constructing Basic Functions from Directed Graphs for Value Functions Approximation. In: Proc. of ICML (2007)
Zhou, D., Huang, J., Schölkopf, B.: Learning from Labeled and Unlabeled Data on a Directed Graph. In: Proc. of ICML (2005)
Brasseur, C.E., Grady, R.E., Prassidis, S.: Coverings, Laplacians and Heat Kernels of Directed Graphs. Electr. J. Comb 01/2009 16(1) (2009)
Nock, R., Nielsen, F.: Fitting Smallest Enclosing Bregman Ball. In: Gama, J., Camacho, R., Brazdil, P.B., Jorge, A.M., Torgo, L. (eds.) ECML 2005. LNCS (LNAI), vol. 3720, pp. 649–656. Springer, Heidelberg (2005)
Tsang, I.W., Kocsor, A., Kwok, J.T.: Simple Core Vector Machines with Enclosing Balls. In: Proc. of ICLM (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Escolano, F., Bonev, B., Hancock, E.R. (2012). Heat Flow-Thermodynamic Depth Complexity in Directed Networks. In: Gimel’farb, G., et al. Structural, Syntactic, and Statistical Pattern Recognition. SSPR /SPR 2012. Lecture Notes in Computer Science, vol 7626. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34166-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-34166-3_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34165-6
Online ISBN: 978-3-642-34166-3
eBook Packages: Computer ScienceComputer Science (R0)