Entropy Bounds for Hierarchical Molecular Networks
Open accessThe DOI matches its Crossref record; 79 of the 82 references it cites were found in a registry or an index.
Abstract
In this paper we derive entropy bounds for hierarchical networks. More precisely, starting from a recently introduced measure to determine the topological entropy of non-hierarchical networks, we provide bounds for estimating the entropy of hierarchical graphs. Apart from bounds to estimate the entropy of a single hierarchical graph, we see that the derived bounds can also be used for characterizing graph classes. Our contribution is an important extension to previous results about the entropy of non-hierarchical networks because for practical applications hierarchical networks are playing an important role in chemistry and biology. In addition to the derivation of the entropy bounds, we provide a numerical analysis for two special graph classes, rooted trees and generalized trees, and demonstrate hereby not only the computational feasibility of our method but also learn about its characteristics and interpretability with respect to data analysis.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures





Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“Although previous work using complex networks theory has quantitatively tackled the problem [3, 4, 22-25, 27-31], some questions remain:”
From On the origins of hierarchy in complex networks (2013) · cites this paper as [29]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb00917.x · Cited by 48,949
Harary, F. (1969) · Cited by 10,739
The Mathematical Theory of Communication
Shannon, C. E., Weaver, W., & Wiener, N. (1950) · Physics Today · doi:10.1063/1.3067010 · Cited by 9,801
Harary, F. (1969) · doi:10.21236/ad0705364 · Cited by 4,861
ASH, R. B. (1966) · Cited by 3,990
Dorogovtsev, S. N., & Mendes, J. F. F. (2002) · Advances in Physics · doi:10.1080/00018730110112519 · Cited by 3,171
Wooding, S. (2004) · The American Journal of Human Genetics · doi:10.1086/383584 · Cited by 3,032
Science and Information Theory
Brillouin, L., & Hellwarth, R. W. (1956) · Physics Today · doi:10.1063/1.3059856 · Cited by 1,915
Bang-Jensen, J., & Gutin, G. (2002) · doi:10.1007/978-1-4471-3886-0 · Cited by 1,856
ON THE MATHEMATICAL THEORY OF COMMUNICATION
Takada, Y. (1954) · The Japanese journal of psychology · doi:10.4992/jjpsy.25.110 · Cited by 1,631
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
Trinajstic, N. (2018) · Routledge eBooks · doi:10.1201/9781315139111 · Cited by 1,491
Topological Indices and Related Descriptors in QSAR and QSPR
(2000) · CRC Press eBooks · doi:10.1201/9781482296945 · Cited by 1,316
Mathematical Concepts in Organic Chemistry
Gutman, I., & Polansky, O. E. (1986) · Springer eBooks · doi:10.1007/978-3-642-70982-1 · Cited by 1,230
Linked: How Everything Is Connected to Everything Else and What It Means
Barabási, A.-Ĺ. (2003) · Plume eBooks · Cited by 734
Foulds, L. R. (1992) · Universitext · doi:10.1007/978-1-4612-0933-1 · Cited by 544
Information theory, distance matrix, and molecular branching
Bonchev, D., & Trinajstić, N. (1977) · The Journal of Chemical Physics · doi:10.1063/1.434593 · Cited by 529
Information theoretic indices for characterization of chemical structures
Bonchev, D. (1983) · Research Studies Press eBooks · Cited by 454
Life, information theory, and topology
Rashevsky, N. (1955) · The Bulletin of Mathematical Biophysics · doi:10.1007/bf02477860 · Cited by 427
Whitesides, G. M., & Ismagilov, R. F. (1999) · Science · doi:10.1126/science.284.5411.89 · Cited by 423
Felsenstein, J. (2004) · Cited by 404
Graph theory and networks in Biology
Mason, O., & Verwoerd, M. (2007) · IET Systems Biology · doi:10.1049/iet-syb:20060038 · Cited by 398
Cook, D. J., & Holder, L. B. (2006) · Wiley-Interscience eBooks · Cited by 396
Entropy and the complexity of graphs: I. An index of the relative complexity of a graph
Mowshowitz, A. (1968) · The Bulletin of Mathematical Biophysics · doi:10.1007/bf02476948 · Cited by 330
Comparing multiple RNA secondary structures using tree comparisons
Shapiro, B. A., & Zhang, K. (1990) · Bioinformatics · doi:10.1093/bioinformatics/6.4.309 · Cited by 319
Cyclic pattern kernels for predictive graph mining
Horváth, T., Gärtner, T., & Wrobel, S. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014072 · Cited by 308
Information processing in complex networks: Graph entropy and information functionals
Dehmer, M. (2008) · Applied Mathematics and Computation · doi:10.1016/j.amc.2007.12.010 · Cited by 286
Self-citationDesign of drugs involving the concepts and theories of drug metabolism and pharmacokinetics
Smith, D. A., Jones, B., & Walker, D. K. (1996) · Medicinal Research Reviews · doi:10.1002/(sici)1098-1128(199605)16:3<267::aid-med3>3.0.co;2-x · Cited by 239
Local similarity in RNA secondary structures
Hochsmann, M., Toller, T., Giegerich, R., & Kurtz, S. (2004) · Computational Systems Bioinformatics. CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference. CSB2003 · doi:10.1109/csb.2003.1227315 · Cited by 235
Chemical graph theory, introduction and fundamentals
M, R. B. (1993) · Journal of Molecular Structure: THEOCHEM · doi:10.1016/0166-1280(93)80032-u · Cited by 219
A note on the information content of graphs
Trucco, E. (1956) · The Bulletin of Mathematical Biophysics · doi:10.1007/bf02477836 · Cited by 218
Recent developments in graph matching
Bunke, H. (2002) · Proceedings 15th International Conference on Pattern Recognition. ICPR-2000 · doi:10.1109/icpr.2000.906030 · Cited by 180
A supertree method for rooted trees
Semple, C., & Steel, M. (2000) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(00)00202-x · Cited by 174
Some order-disorder considerations in living systems
Morowitz, H. J. (1955) · Bulletin of Mathematical Biology · doi:10.1007/bf02477985 · Cited by 153
Complexity in Chemistry, Biology, and Ecology
Bonchev, D., & Rouvray, D. H. (2005) · Springer eBooks · doi:10.1007/b136300 · Cited by 151
Chemical Group Theory: Introduction and Fundamentals
Bonchev, D., & Rouvray, D. H. (1994) · Medical Entomology and Zoology · Cited by 140
Rashevsky, N. P. (1954) · Bulletin of Mathematical Biology · doi:10.1007/bf02478375 · Cited by 133
Entropy and the complexity of graphs: II. The information content of digraphs and infinite graphs
Mowshowitz, A. (1968) · Bulletin of Mathematical Biology · doi:10.1007/bf02476692 · Cited by 121
Quantitative Structure-Activity Relationship (QSAR) Models of Mutagens and Carcinogens
Benigni, R. (2003) · CRC Press eBooks · doi:10.1201/9780203010822 · Cited by 119
Simonyi, G. (1995) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/020/08 · Cited by 117
On a certain distance between isomorphism classes of graphs
Zelinka, B. (1975) · Časopis pro pěstování matematiky · doi:10.21136/cpm.1975.117890 · Cited by 115
Visco, D. P., Pophale, R. S., Rintoul, M. D., & Faulon, J. (2002) · Journal of Molecular Graphics and Modelling · doi:10.1016/s1093-3263(01)00144-9 · Cited by 111
(1995) · Topics in current chemistry · doi:10.1007/3-540-58672-5 · Cited by 108
Entropy and the complexity of graphs: IV. Entropy measures and graphical structure
Mowshowitz, A. (1968) · Bulletin of Mathematical Biology · doi:10.1007/bf02476673 · Cited by 88
Entropy and the complexity of graphs: III. Graphs with prescribed information content
Mowshowitz, A. (1968) · Bulletin of Mathematical Biology · doi:10.1007/bf02476603 · Cited by 86
Points of View Simple but Fundamental Limitations on Supertree and Consensus Tree Methods
Steel, M., Dress, A., & Böcker, S. (2000) · Systematic Biology · doi:10.1093/sysbio/49.2.363 · Cited by 84
Kernel Approach to Molecular Similarity Based on Iterative Graph Similarity
Rupp, M., Proschak, E., & Schneider, G. (2007) · Journal of Chemical Information and Modeling · doi:10.1021/ci700274r · Cited by 68
Quantitative structure-activity relationship (QSAR) models of mutagens and carcinogens
Benigni, R. (2007) · Cited by 68
Overall Connectivities/Topological Complexities: A New Powerful Tool for QSPR/QSAR
Bonchev, D. (2000) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci990120u · Cited by 59
Complexity in chemistry : introduction and fundamentals
Bonchev, D., & Rouvray, D. H. (2003) · Taylor & Francis eBooks · Cited by 57
Essays on the Use of Information Theory in Biology
Quastler, H., & Hoffman, J. (1955) · Physics Today · doi:10.1063/1.3062071 · Cited by 55
A Study of Graph Spectra for Comparing Graphs
Zhu, P., & Wilson, R. C. (2005) · British Machine Vision Conference (BMVC) · doi:10.5244/c.19.69 · Cited by 54
On Distances in Benzenoid Systems
Chepoi, V. D. (1996) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci9600869 · Cited by 45
Bartholomew, C. H., & Farrauto, R. J. (2005) · doi:10.1002/9780471730071.ch1 · Cited by 44
Structural information content of networks: Graph entropy based on local vertex functionals
Dehmer, M., & Emmert‐Streib, F. (2007) · Computational Biology and Chemistry · doi:10.1016/j.compbiolchem.2007.09.007 · Cited by 44
Self-citationThe concept for the centre of a chemical structure and its applications
Bonchev, D. (1989) · Journal of Molecular Structure THEOCHEM · doi:10.1016/0166-1280(89)85011-0 · Cited by 33
Classification of large Graphs by a local Tree decomposition
Emmert‐Streib, F., Dehmer, M., & Kilian, J. (2005) · Research Portal (Queen's University Belfast) · Cited by 31
Self-citationTowards Logical Hypertext Structure A Graph-Theoretic Perspective
Mehler, A., Dehmer, M., & Gleim, R. (2006) · TUbilio (Technical University of Darmstadt) · Cited by 30
Self-citationMolecular Similarity. 1. Analytical Description of the Set of Graph Similarity Measures
Скворцова, М. И., Baskin, I. I., Stankevich, I. V., Palyulin, V. A., & Zefirov, N. S. (1998) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci970037b · Cited by 29
Time-dependent differential virial theorems
Qian, Z., & Sahni, V. (2000) · International Journal of Quantum Chemistry · doi:10.1002/(sici)1097-461x(2000)78:5<331::aid-qua4>3.0.co;2-v · Cited by 26
Symmetry of chemical structures: A novel method of graph automorphism group determination
Bohanec, S., & Perdih, M. (1993) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci00015a010 · Cited by 24
Halin, R. (1989) · De Gruyter eBooks · doi:10.1515/9783112471401 · Cited by 23
A Linear Algorithm for the Hyper-Wiener Index of Chemical Trees
Aringhieri, R., Hansen, P., & Malucelli, F. (2001) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci0001536 · Cited by 19
Measuring The Structural Similarity Of Web-Based Documents: A Novel Approach
Dehmer, M., Emmert‐Streib, F., Mehler, A., & Kilian, J. (2007) · TUbilio (Technical University of Darmstadt) · doi:10.5281/zenodo.1086030 · Cited by 17
Self-citationBrinkmeier, M., & Schank, T. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31955-9_11 · Cited by 17
Chemical trees enumeration algorithms
Aringhieri, R., Hansen, P., & Malucelli, F. (2003) · 4OR · doi:10.1007/s10288-002-0008-9 · Cited by 16
Ergodic behavior of graph entropy
Kieffer, J. C., & Yang, E. (1997) · Electronic Research Announcements of the American Mathematical Society · doi:10.1090/s1079-6762-97-00018-8 · Cited by 15
Graph Matching—Exact and Error‐Tolerant Methods and the Automatic Learning of Edit Costs
Bunke, H., & Neuhaus, M. (2006) · doi:10.1002/9780470073049.ch2 · Cited by 13
Sahu, P. K., & Lee, S. (2008) · Chemical Physics Letters · doi:10.1016/j.cplett.2008.01.055 · Cited by 13
Pap, L. (1990) · Cited by 12
A canonical ordering of polybenzenes and polymantanes using a prime number factorization technique
Elk, S. B. (1990) · Journal of Mathematical Chemistry · doi:10.1007/bf01170004 · Cited by 11
Gambin, A., & Słonimski, P. P. (2004) · Comptes Rendus Biologies · doi:10.1016/j.crvi.2004.11.001 · Cited by 10
QSPR QSAR studies by molecular descriptors
Diudea, M. V. (2001) · Cited by 8
Ranking Genes From Dna Microarray Data Of Cervical Cancer By A Local Tree Comparison
Emmert‐Streib, F., Dehmer, M., Liu, J., & Mühlhäuser, M. (2007) · TUbilio (Technical University of Darmstadt) · doi:10.5281/zenodo.1060016 · Cited by 4
Self-citationThe Hosoya-Wiener Polynomial of Weighted Trees
Zmazek, B., & Žerovnik, J. (2007) · University of Maribor digital library (University of Maribor) · Cited by 3
A NOVEL CLUSTERING METHOD FOR ANALYSIS OF BIOLOGICAL NETWORKS USING MAXIMAL COMPONENTS OF GRAPHS
Hayashida, M., Akutsu, T., & Nagamochi, H. (2007) · Asia-Pacific Bioinformatics Conference · doi:10.1142/9781860947995_0028 · Cited by 2
A Comparison between the Matula Numbers and Bit-tuple Notation for Rooted Trees
Mueller, W. R., Szymanski, K., Knop, J. V., & Trinajstić, N. (1995) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci00024a007 · Cited by 2
Hayashida, M., Akutsu, T., & Nagamochi, H. (2008) · IPSJ Digital Courier · doi:10.2197/ipsjdc.4.207 · Cited by 1
Research works printed but not linked: 11
- Batagelj V 1988 Similarity measures between structured objects. Graovac A Dubrovnik/Yugoslavia: Proceedings of an International Course and Conference on the Interfaces between Mathematics, Chemistry and Computer Sciences 25 40
- Bunke H 1983 What is the distance between graphs? Bulletin of the EATCS 20 35 39
- Sobik F 1982 Graphmetriken und Klassifikation strukturierter Objekte. ZKI-Informationen, Akad Wiss DDR 2(82) 63 122
- Sobik F 1986 Modellierung von Vergleichsprozessen auf der Grundlage von Ähnlichkeitsmaßen für Graphen. ZKI-Informationen, Akad Wiss DDR 4 104 144
- Kaden F Graphmetriken und Distanzgraphen. ZKI-Informationen, Akad Wiss DDR 2(82) 1 63
- Fujii JI Yuki S 1997 Entropy and coding for graphs. Int J Math Stat Sci 6(1) 63 77
- Matula DW 1968 A natural rooted tree enumeration by prime factorization. SIAM Review 10 273
- Liu SC Tong LD Yeh JY 2000 Trees with the minimum wiener number. International Journal of Quantum Chemistry 78(5) 331 340
- Skorobogatov VA Dobrynin AA 1988 Metrical analysis of graphs. MATCH 23 105 155
- Semple C Steel M 2003 Phylogenetics. Graduate Series Mathematics and its Applications Oxford University Press
- Bang-Jensen J Gutin G 2002 Digraphs. Theory, Algorithms and Applications London, Berlin, Heidelberg Springer
Cited by
A history of graph entropy measures
Dehmer, M., & Mowshowitz, A. (2011) · Information Sciences · doi:10.1016/j.ins.2010.08.041 · Cited by 565
Self-citationExtremality of degree-based graph entropies
Cao, S., Dehmer, M., & Shi, Y. (2014) · Information Sciences · doi:10.1016/j.ins.2014.03.133 · Cited by 182
Self-citationA Note on Distance-based Graph Entropies
Chen, Z., Dehmer, M., & Shi, Y. (2014) · Entropy · doi:10.3390/e16105416 · Cited by 176
Self-citationOn the origins of hierarchy in complex networks
Corominas-Murtra, B., Goñi, J., Solé, R. V., & Rodríguez-Caso, C. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1300832110 · Cited by 160
Hierarchy and dynamics of neural networks
Kaiser, M. (2010) · Frontiers in Neuroinformatics · doi:10.3389/fninf.2010.00112 · Cited by 136
Metadata
- Authors
- Dehmer, M., Borgert, S., & Emmert-Streib, F.
- Affiliations
- TU Wien (AT)
- University of Siegen (DE)
- Corresponding author
- Dehmer, Matthias
- ORCID
- Dehmer, Matthias
- Venue
- PLoS ONE
- Publisher
- Public Library of Science (PLoS)
- Published
- 2008-08-28
- Volume
- 3
- Issue
- 8
- Pages
- e3079
- ISSN
- 1932-6203 (ISSN-L)
- PMC
- PMC2518648
- OpenAlex
- W2026781624
- Cited by
- 40
- References
- 82
- Citations by year
- 2026: 1 · 2025: 1 · 2021: 1 · 2019: 1 · 2018: 1 · 2017: 1 · 2016: 6 · 2015: 2 · 2014: 6 · 2013: 1 · 2012: 9
- FWCI
- 4.75
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- PLoS ONE (publishedVersion, cc-by)
- Europe PMC (PubMed Central) (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) (submittedVersion, cc-by)
- Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) (submittedVersion, other-oa)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) (submittedVersion)
- Research Portal (Queen's University Belfast) (submittedVersion)
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Graph theory and applications
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Keywords
- entropy bounds, hierarchical networks, topological entropy, molecular networks, graph classes, rooted trees, network topology
- MeSH terms
- Algorithms, Artificial Intelligence, Computer Simulation, Models, Molecular, Pattern Recognition, Automated, Probability, Models, Statistical, Entropy, Computational Biology
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.