Network Complexity Measures. An Information-Theoretic Approach.
Matthias Dehmer, Stefan Pickl
Quantitative graph analysis by using structural indices has been intricate in a sense that it often remains unclear which structural graph measures is the most suitable one, see [1, 12, 13]. In general, quantitative graph analysis deals with quantifying structural information of networks by using a measurement approach [5]. As special problem thereof is to characterize a graph quantitatively, that means to determine a measure that captures structural features of a network meaningfully. Various classical structural graph measures have been used to tackle this problem [13]. A fruitful approach by using information-theoretic [21] and statistical methods is to quantify the structural information content of a graph [1, 8, 18].
In this note, we sketch some classical information measures. Also, we briefly address the problem what kind of measures capture structural information uniquely. This relates to determine the discrimination power (or also called uniqueness) of a graph measure, that is, how is the ability of the measures to discriminate non-isomorphic graphs structurally.
[1] D. Bonchev. Information Theoretic Indices for Characterization of Chemical Structures. Research Studies Press, Chichester, 1983.
[5] M. Dehmer and F. Emmert-Streib. Quantitative Graph Theory. Theory and Applications. CRC Press, 2014.
[8] M. Dehmer, M. Grabner, and K. Varmuza. Information indices with high discriminative power for graphs. PLoS ONE, 7:e31214, 2012.
[12] F. Emmert-Streib and M. Dehmer. Exploring statistical and population aspects of network complexity. PLoS ONE, 7:e34523, 2012.
[13] F. Harary. Graph Theory. Addison Wesley Publishing Company, 1969. Reading, MA, USA.
[18] A. Mowshowitz. Entropy and the complexity of the graphs I: An index of the relative complexity of a graph. Bull. Math. Biophys., 30:175–204, 1968.
[21] C. E. Shannon and W. Weaver. The Mathematical Theory of Communication. University of Illinois Press, 1949. Full Text
|
