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 条

[1] Measuring graph abstractions of software: An information-theory approach [J].

Allen, EB .

EIGHTH IEEE SYMPOSIUM ON SOFTWARE METRICS, PROCEEDINGS, 2002, :182-193

[2] Revealing differences in gene network inference algorithms on the network level by ensemble methods [J].

Altay, Goekmen ;

Emmert-Streib, Frank .

BIOINFORMATICS, 2010, 26 (14) :1738-1744

[3] Entropy measures for networks: Toward an information theory of complex topologies [J].

Anand, Kartik ;

Bianconi, Ginestra .

PHYSICAL REVIEW E, 2009, 80 (04)

[4]

[Anonymous], LECT NOTES COMPUTER

[5]

[Anonymous], 2006, PRINCETON STUDIES CO

[6]

[Anonymous], 1988, Algorithms for Clustering Data

[7]

[Anonymous], GRAPHENTHEORIE

[8] NEW VERTEX INVARIANTS AND TOPOLOGICAL INDEXES OF CHEMICAL GRAPHS BASED ON INFORMATION ON DISTANCES [J].

BALABAN, AT ;

BALABAN, TS .

JOURNAL OF MATHEMATICAL CHEMISTRY, 1991, 8 (04) :383-397

[9] Hierarchic social entropy: An information theoretic measure of robot group diversity [J].

Balch, T .

AUTONOMOUS ROBOTS, 2000, 8 (03) :209-237

[10] Emergence of scaling in random networks [J].

Barabási, AL ;

Albert, R .

SCIENCE, 1999, 286 (5439) :509-512

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