Structural information content of networks: Graph entropy based on local vertex functionals

Matthias Dehmer; Frank Emmert-Streib

doi:10.1016/j.compbiolchem.2007.09.007

Structural information content of networks: Graph entropy based on local vertex functionals

Matthias Dehmer^*
, Frank Emmert-Streib

^*Corresponding author for this work

Vienna University of Technology (TU Vienna)
University of Washington

Research output: Contribution to journal › Article › peer-review

37 Citations (Scopus)

Abstract

In this paper we define the structural information content of graphs as their corresponding graph entropy. This definition is based on local vertex functionals obtained by calculating j-spheres via the algorithm of Dijkstra. We prove that the graph entropy and, hence, the local vertex functionals can be computed with polynomial time complexity enabling the application of our measure for large graphs. In this paper we present numerical results for the graph entropy of chemical graphs and discuss resulting properties.

Original language	English
Pages (from-to)	131-138
Number of pages	8
Journal	Computational Biology and Chemistry
Volume	32
Issue number	2
DOIs	https://doi.org/10.1016/j.compbiolchem.2007.09.007
Publication status	Published - Apr 2008
Externally published	Yes

Keywords

Chemical graph theory
Gene networks
Graph entropy
Information theory
Structural information content

Access to Document

10.1016/j.compbiolchem.2007.09.007

Cite this

@article{ee90edf34ee840e790496591cef95bee,

title = "Structural information content of networks: Graph entropy based on local vertex functionals",

abstract = "In this paper we define the structural information content of graphs as their corresponding graph entropy. This definition is based on local vertex functionals obtained by calculating j-spheres via the algorithm of Dijkstra. We prove that the graph entropy and, hence, the local vertex functionals can be computed with polynomial time complexity enabling the application of our measure for large graphs. In this paper we present numerical results for the graph entropy of chemical graphs and discuss resulting properties.",

keywords = "Chemical graph theory, Gene networks, Graph entropy, Information theory, Structural information content",

author = "Matthias Dehmer and Frank Emmert-Streib",

year = "2008",

month = apr,

doi = "10.1016/j.compbiolchem.2007.09.007",

language = "English",

volume = "32",

pages = "131--138",

journal = "Computational Biology and Chemistry",

issn = "1476-9271",

publisher = "Elsevier Ltd",

number = "2",

}

TY - JOUR

T1 - Structural information content of networks

T2 - Graph entropy based on local vertex functionals

AU - Dehmer, Matthias

AU - Emmert-Streib, Frank

PY - 2008/4

Y1 - 2008/4

N2 - In this paper we define the structural information content of graphs as their corresponding graph entropy. This definition is based on local vertex functionals obtained by calculating j-spheres via the algorithm of Dijkstra. We prove that the graph entropy and, hence, the local vertex functionals can be computed with polynomial time complexity enabling the application of our measure for large graphs. In this paper we present numerical results for the graph entropy of chemical graphs and discuss resulting properties.

AB - In this paper we define the structural information content of graphs as their corresponding graph entropy. This definition is based on local vertex functionals obtained by calculating j-spheres via the algorithm of Dijkstra. We prove that the graph entropy and, hence, the local vertex functionals can be computed with polynomial time complexity enabling the application of our measure for large graphs. In this paper we present numerical results for the graph entropy of chemical graphs and discuss resulting properties.

KW - Chemical graph theory

KW - Gene networks

KW - Graph entropy

KW - Information theory

KW - Structural information content

UR - https://www.scopus.com/pages/publications/40049085450

U2 - 10.1016/j.compbiolchem.2007.09.007

DO - 10.1016/j.compbiolchem.2007.09.007

M3 - Article

C2 - 18243802

AN - SCOPUS:40049085450

SN - 1476-9271

VL - 32

SP - 131

EP - 138

JO - Computational Biology and Chemistry

JF - Computational Biology and Chemistry

IS - 2

ER -

Structural information content of networks: Graph entropy based on local vertex functionals

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this