Tampere University of Technology

TUTCRIS Research Portal

Information theoretic measures of UHG graphs with low computational complexity

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)1783-1794
Number of pages12
JournalApplied Mathematics and Computation
Volume190
Issue number2
DOIs
Publication statusPublished - 15 Jul 2007
Externally publishedYes
Publication typeA1 Journal article-refereed

Abstract

We introduce a novel graph class we call universal hierarchical graphs (UHG) 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.

Keywords

  • Entropy, Graph classes, Graph measures, Hierarchical graphs, Information theory