A history of graph entropy measures

被引：390

作者：

Dehmer, Matthias ^{[1
,2
]}

Mowshowitz, Abbe ^{[3
]}

机构：

[1] UMIT, Inst Bioinformat & Translat Res, Eduard Wallnoefer Zentrum 1, A-6060 Hall In Tirol, Austria

[2] Vienna Univ Technol, Inst Discrete Math & Geometry, A-1040 Vienna, Austria

[3] CUNY City Coll, Dept Comp Sci, New York, NY 10031 USA

来源：

INFORMATION SCIENCES | 2011年 / 181卷 / 01期

关键词：

Graphs; Information theory; Information measures; Information inequalities; Entropy; Graph entropy; Graph complexity; Structural complexity; STRUCTURAL INFORMATION-CONTENT; COMPLEX NETWORKS; INDEX;

D O I：

10.1016/j.ins.2010.08.041

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples. (C) 2010 Elsevier Inc. All rights reserved.

引用

页码：57 / 78

页数：22

共 95 条

[21] A faster algorithm for betweenness centrality [J].

Brandes, U .

JOURNAL OF MATHEMATICAL SOCIOLOGY, 2001, 25 (02) :163-177

[22] The complexity of social networks: theoretical and empirical findings [J].

Butts, CT .

SOCIAL NETWORKS, 2001, 23 (01) :31-71

[23] Information-theoretic gene-gene and gene-environment interaction analysis of quantitative traits [J].

Chanda, Pritam ;

Sucheston, Lara ;

Liu, Song ;

Zhang, Aidong ;

Ramanathan, Murali .

BMC GENOMICS, 2009, 10 :509

[24] Offdiagonal complexity: A computationally quick complexity measure for graphs and networks [J].

Claussen, Jens Christian .

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2007, 375 (01) :365-373

[25]

Cook W., 1998, COMBINATORIAL OPTIMI

[26] Characterization of complex networks: A survey of measurements [J].

Costa, L. Da F. ;

Rodrigues, F. A. ;

Travieso, G. ;

Boas, P. R. Villas .

ADVANCES IN PHYSICS, 2007, 56 (01) :167-242

[27] Beyond the average: Detecting global singular nodes from local features in complex networks [J].

Costa, L. da F. ;

Rodrigues, F. A. ;

Hilgetag, C. C. ;

Kaiser, M. .

EPL, 2009, 87 (01)

[28] Seeking for simplicity in complex networks [J].

Costa, L. da F. ;

Rodrigues, F. A. .

EPL, 2009, 85 (04)

[29]

Cover T. M., 1999, Elements of information theory

[30] ENTROPY SPLITTING FOR ANTIBLOCKING CORNERS AND PERFECT GRAPHS [J].

CSISZAR, I ;

KORNER, J ;

LOVASZ, L ;

MARTON, K ;

SIMONYI, G .

COMBINATORICA, 1990, 10 (01) :27-40

← 1 2 3 4 5 6 7 8 9 10 →