×

Information theoretic measures of UHG graphs with low computational complexity. (English) Zbl 1123.68088

Summary: We introduce a novel graph class we call universal hierarchical graphs whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C90 Applications of graph theory
94A17 Measures of information, entropy

Software:

Graphviz; Dynagraph
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alberts, B.; Johnson, A.; Lewis, J.; Raff, M.; Roberts, K.; Walter, P., Molecular Biology of the Cell (2002), Garland
[2] L. Babai, Automorphism groups, isomorphism, reconstruction. Technical report, Chicago, IL, USA, 1994.; L. Babai, Automorphism groups, isomorphism, reconstruction. Technical report, Chicago, IL, USA, 1994. · Zbl 0846.05042
[3] L. Babai, L. Kucera, Canonical labelling of graphs in linear average time, in: Proceedings 20th IEEE Symposium on Foundations of Computer Science (FOCS), 1979. pp. 39-46.; L. Babai, L. Kucera, Canonical labelling of graphs in linear average time, in: Proceedings 20th IEEE Symposium on Foundations of Computer Science (FOCS), 1979. pp. 39-46.
[4] Bavelas, A., Communication patterns in task-oriented groups, Journal of the Acoustical Society of America, 22, 723-730 (1950)
[5] Brandstädt, A.; Le, V. B.; Sprinrand, J. P., Graph Classes. A Survey (1999), SIAM Monographs on Discrete Mathematics and Applications
[6] Bulashevska, S.; Eils, R., Inferring genetic regulatory logic from expression data, Bioinformatics, 21, 2706-2713 (2005)
[7] A. Caley, On the analytical forms called trees, with application to the theory of chemical combinatorics. Report of the British Association for the Advancement of Science, 1875. pp. 257-305.; A. Caley, On the analytical forms called trees, with application to the theory of chemical combinatorics. Report of the British Association for the Advancement of Science, 1875. pp. 257-305.
[8] Cover, T. M.; Thomas, J. A., Information Theory (1991), John Wiley and Sons, Inc.
[9] Dehmer, M., Strukturelle Analyse Web-basierter Dokumente, (Lehner, F.; Bodendorf, F., Multimedia und Telekooperation (2006), Wissenschaft-Deutscher Universitätsverlag)
[10] Dehmer, M.; Emmert-Streib, F.; Mehler, A.; Kilian, J., Measuring the structural similarity of web-based documents: A novel approach, International Journal of Computational Intelligence, 3, 1, 1-7 (2006)
[11] Ellson, J.; Gansner, E. R.; Koutsofious, E.; North, S. C.; Woodhull, G., Graph Drawing Software, (Graphviz and Dynagraph - Static and Dynamic Graph Drawing Tools (2003), Springer-Verlag)
[12] F. Emmert-Streib, M. Dehmer, J. Kilian, Classification of large graphs by a local tree decomposition, in: H.R. Arabnia, A. Scime, (Eds.), Proceedings of the 2005 International Conference on Data Mining (DMIN’05), 2005. pp. 200-207.; F. Emmert-Streib, M. Dehmer, J. Kilian, Classification of large graphs by a local tree decomposition, in: H.R. Arabnia, A. Scime, (Eds.), Proceedings of the 2005 International Conference on Data Mining (DMIN’05), 2005. pp. 200-207.
[13] Emmert-Streib, F.; Dehmer, M.; Liu, J.; Mühlhäuser, M., Ranking genes from dna microarray data of cervical cancer by a local tree comparison, International Journal of Biomedical Sciences, 1, 1, 17-22 (2006)
[14] Harary, F., Status and contrastatus, Sociometry, 22, 23-43 (1959)
[15] Harary, F., Graph theory and theoretical physics (1967), Academic Press · Zbl 0202.55602
[16] Kaden, F.; Koch, I.; Selbig, J., Knowledge-based predication of protein structures, Journal of Theoretical Biology, 147, 85-100 (1990)
[17] König, D., Theorie der endlichen und unendlichen Graphen (1936), Chelsea Publishing · JFM 62.0654.05
[18] Mathon, R., A note on the graph isomorphism counting problem, Information Processing Letters, 8, 131-132 (1979) · Zbl 0395.68057
[19] McKay, B. D., Graph isomorphisms, Congressus Numerantium, 30, 45-87 (1981)
[20] Mehler, A.; Dehmer, M.; Gleim, R., Towards logical hypertext structure. A graph-theoretic perspective, (Proceedings of I2CS’04. Proceedings of I2CS’04, Lecture Notes (2005), Springer: Springer Berlin-New York), 136-150
[21] Miyazaki, T., The complexity of Mckay’s canonical labeling algorithm (1996) · Zbl 0878.05063
[22] Mowshowitz, A., Entropy and the complexity of graphs: I. an index of the relative complexity of a graph, Bulletin of Mathematical Biophysics, 30, 175-204 (1968) · Zbl 0165.57601
[23] Mowshowitz, A., Entropy and the complexity of graphs: Ii. The information content of digraphs and infinite graphs, Bulletin of Mathematical Biophysics, 30, 225-240 (1968) · Zbl 0165.57602
[24] Mowshowitz, A., Entropy and the complexity of graphs: Iii. graphs with prescribed informationn content, Bulletin of Mathematical Biophysics, 30, 387-414 (1968) · Zbl 0165.57603
[25] Mowshowitz, A., Entropy and the complexity of graphs: Iv. entropy measures and graphical structure, Bulletin of Mathematical Biophysics, 30, 533-546 (1968) · Zbl 0204.24603
[26] Papoulis, A., Probability, Random Variables, and Stochastic Processes (1991), McGraw-Hill · Zbl 0191.46704
[27] Rashevsky, N., Life, information theory and topology, Bulletin of Mathematical Biophysics, 17, 229-235 (1955)
[28] Scott, F., Social Network Analysis (2001), Sage Publications
[29] Soinov, L. A.; Krestyaninova, M. A.; Brazma, A., Towards reconstruction of gene networks from expression data by supervised learning, Genome Biology, 4, 1, R6 (2003)
[30] Trucco, E., A note on the information content of graphs, Bulletin of Mathematical Biophysics, 18, 129-135 (1956)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.