Graph characterizations from von Neumann entropy

被引：82

作者：

Han, Lin ^{[1
]}

Escolano, Francisco ^{[2
]}

Hancock, Edwin R. ^{[1
]}

Wilson, Richard C. ^{[1
]}

机构：

[1] Univ York, Dept Comp Sci, York YO10 5GH, N Yorkshire, England

[2] Univ Alicante, Dept Comp Sci & Artificial Intelligence, Alicante, Spain

来源：

PATTERN RECOGNITION LETTERS | 2012年 / 33卷 / 15期

关键词：

Graph characterizations; Von Neumann entropy; Estrada's heterogeneity index; Thermodynamic depth complexity;

D O I：

10.1016/j.patrec.2012.03.016

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper we explore how the von Neumann entropy can be used as a measure of graph complexity. We also develop a simplified form for the von Neumann entropy of a graph that can be computed in terms of node degree statistics. We compare the resulting complexity with Estrada's heterogeneity index which measures the heterogeneity of the node degree across a graph and reveal a new link between Estrada's index and the commute time on a graph. Finally, we explore how the von Neumann entropy can be used in conjunction with thermodynamic depth. This measure has been shown to overcome problems associated with iso-spectrality encountered when using complexity measures based on spectral graph theory. Our experimental evaluation of the simplified von Neumann entropy explores (a) the accuracy of the underlying approximation, (b) a comparison with alternative graph characterizations, and (c) the application of the entropy-based thermodynamic depth to characterize protein-protein interaction networks. Crown Copyright (c) 2012 Published by Elsevier B.V. All rights reserved.

引用

页码：1958 / 1967

页数：10

共 33 条

[1]

Anand K., 2010, ARXIV10111565V2

[2]

Bai L, 2011, LECT NOTES COMPUT SC, V6854, P394, DOI 10.1007/978-3-642-23672-3_48

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

Barabási, AL ;

Albert, R .

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

[4]

Biggs N., 1974, CAMBRIDGE TRACTS MAT, V67

[5] The Laplacian of a graph as a density matrix: A basic combinatorial approach to separability of mixed states [J].

Braunstein, Samuel L. ;

Ghosh, Sibasish ;

Severini, Simone .

ANNALS OF COMBINATORICS, 2006, 10 (03) :291-317

[6]

Erdos P., 1959, PUBL MATH-DEBRECEN, V6, P290, DOI DOI 10.5486/PMD.1959.6.3-4.12

[7]

Escolano F, 2010, LECT NOTES COMPUT SC, V6218, P286, DOI 10.1007/978-3-642-14980-1_27

[8]

Estrada E., 2010, PUBL MATH

[9] Quantifying network heterogeneity [J].

Estrada, Ernesto .

PHYSICAL REVIEW E, 2010, 82 (06)

[10] Measures of statistical complexity: Why? [J].

Feldman, DP ;

Crutchfield, JP .

PHYSICS LETTERS A, 1998, 238 (4-5) :244-252

← 1 2 3 4 →