CoChat

Entropy Bounds for Hierarchical Molecular Networks

Open access
Dehmer, Matthias, Borgert, Stephan, Emmert-Streib, Frank · 2008 · PLoS ONE

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1371/journal.pone.0003079

Cites

79 of 79 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Overall approach to derive entropy bounds for hierarchical graphs.
Figure 1 Overall approach to derive entropy bounds for hierarchical graphs.CC BY · PubMed Central
Figure 2 G represents an undirected and connected graph. For example, we get |S 1(vi,G)| = 5 and |S 2(vi,G)| = 9.
Figure 2 G represents an undirected and connected graph. For example, we get |S 1(vi,G)| = 5 and |S 2(vi,G)| = 9.CC BY · PubMed Central
Figure 3 An undirected tree T and its corresponding undirected generalized tree H. It holds |L| = 4 and h = |L|−1 = 3.
Figure 3 An undirected tree T and its corresponding undirected generalized tree H. It holds |L| = 4 and h = |L|−1 = 3.CC BY · PubMed Central
Figure 4 Cumulative entropy distributions of the classes CαRT for h = 8. The x-axis corresponds to the entropy IfV (T) and the y-axis represents the cumulative entropy distribution for C 1 RT -C 5 RT and C 10 RT.
Figure 4 Cumulative entropy distributions of the classes CαRT for h = 8. The x-axis corresponds to the entropy IfV (T) and the y-axis represents the cumulative entropy distribution for C 1 RT -C 5 RT and C 10 RT.CC BY · PubMed Central
Figure 5 Cumulative entropy distributions of the classes CαGT for h = 8. The x-axis corresponds to the entropy IfV (H) and the y-axis represents the cumulative entropy distribution for C 1 GT -C 5 GT and C 10 GT.
Figure 5 Cumulative entropy distributions of the classes CαGT for h = 8. The x-axis corresponds to the entropy IfV (H) and the y-axis represents the cumulative entropy distribution for C 1 GT -C 5 GT and C 10 GT.CC BY · PubMed Central

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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

Show all 79 references

Research works printed but not linked: 11

  1. 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
  2. Bunke H 1983 What is the distance between graphs? Bulletin of the EATCS 20 35 39
  3. Sobik F 1982 Graphmetriken und Klassifikation strukturierter Objekte. ZKI-Informationen, Akad Wiss DDR 2(82) 63 122
  4. Sobik F 1986 Modellierung von Vergleichsprozessen auf der Grundlage von Ähnlichkeitsmaßen für Graphen. ZKI-Informationen, Akad Wiss DDR 4 104 144
  5. Kaden F Graphmetriken und Distanzgraphen. ZKI-Informationen, Akad Wiss DDR 2(82) 1 63
  6. Fujii JI Yuki S 1997 Entropy and coding for graphs. Int J Math Stat Sci 6(1) 63 77
  7. Matula DW 1968 A natural rooted tree enumeration by prime factorization. SIAM Review 10 273
  8. Liu SC Tong LD Yeh JY 2000 Trees with the minimum wiener number. International Journal of Quantum Chemistry 78(5) 331 340
  9. Skorobogatov VA Dobrynin AA 1988 Metrical analysis of graphs. MATCH 23 105 155
  10. Semple C Steel M 2003 Phylogenetics. Graduate Series Mathematics and its Applications Oxford University Press
  11. Bang-Jensen J Gutin G 2002 Digraphs. Theory, Algorithms and Applications London, Berlin, Heidelberg Springer

Cited by

Metadata

Authors
Dehmer, M., Borgert, S., & Emmert-Streib, F.
Affiliations
  • TU Wien (AT)
  • University of Siegen (DE)
Corresponding author
Dehmer, Matthias
Venue
PLoS ONE
Published
2008-08-28
Volume
3
Issue
8
Pages
e3079
ISSN
1932-6203 (ISSN-L)
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
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.