TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Information theoretic measures of UHG graphs with low computational complexity

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut1783-1794
Sivumäärä12
JulkaisuApplied Mathematics and Computation
Vuosikerta190
Numero2
DOI - pysyväislinkit
TilaJulkaistu - 15 heinäkuuta 2007
Julkaistu ulkoisestiKyllä
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.