Information theoretic measures of UHG graphs with low computational complexity

Frank Emmert-Streib, M. Dehmer

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)

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. (c) 2007 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)1783-1794
Number of pages12
JournalApplied Mathematics and Computation
Volume190
Issue number2
DOIs
Publication statusPublished - 15 Jul 2007

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Numerical Analysis

Fingerprint Dive into the research topics of 'Information theoretic measures of UHG graphs with low computational complexity'. Together they form a unique fingerprint.

Cite this