Information processing in complex networks: Graph entropy and information functionals. (English) Zbl 1152.05361

Summary: This paper introduces a general framework for defining the entropy of a graph. Our definition is based on a local information graph and on information functionals derived from the topological structure of a given graph. More precisely, an information functional quantifies structural information of a graph based on a derived probability distribution. Such a probability distribution leads directly to an entropy of a graph. Then, the structural information content of a graph will be interpreted and defined as the derived graph entropy. Another major contribution of this paper is the investigation of relationships between graph entropies. In addition to this, we provide numerical results demonstrating not only the feasibility of our method, which has polynomial time complexity, but also its usefulness with regard to practical applications aiming to an understanding of information processing in complex networks.


05C75 Structural characterization of families of graphs
94A17 Measures of information, entropy
Full Text: DOI


[1] Bavelas, A., A mathematical model for group structure, Hum. organ., 7, 16-30, (1948)
[2] Bavelas, A., Communication patterns in task-oriented groups, J. acoust. soc. am., 22, 725-730, (1950)
[3] Bonchev, D., Information theoretic indices for characterization of chemical structures, (1983), Research Studies Press Chichester
[4] Brandes, U., A faster algorithm for betweenness centrality, J. math. sociol., 25, 2, 163-177, (2001) · Zbl 1051.91088
[5] Buckley, F.; Harary, F., Distance in graphs, (1990), Addison Wesley Publishing Company · Zbl 0688.05017
[6] Claussen, J.C., Characterization of networks by the offdiagonal complexity, Physica A, 365-373, 321-354, (2007)
[7] Claussen, J.C., Offdiagonal complexity: a computationally quick network complexity measure – application to protein networks and cell division, (), 303-311
[8] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), MIT Press · Zbl 1158.68538
[9] M. Dehmer, A novel method for measuring the structural information content of networks, Cybern. Syst. (2007) in press. · Zbl 1290.94022
[10] M. Dehmer, F. Emmert-Streib, Local information spread in networks, Private Communication, Seattle, USA, 2007.
[11] Dijkstra, E.W., A note on two problems in connection with graphs, Numer. math., 1, 269-271, (1959) · Zbl 0092.16002
[12] Diudea, M.V.; Gutman, I.; Jäntschi, L., Molecular topology, (2001), Nova Publishing
[13] Emmert-Streib, F., The chronic fatigue syndrome: a comparative pathway analysis, J. comput. biol., 14, 7, (2007)
[14] Emmert-Streib, F.; Dehmer, M., Information theoretic measures of UHG graphs with low computational complexity, Appl. math. comput., 190, 2, 1783-1794, (2007) · Zbl 1123.68088
[15] F. Emmert-Streib, M. Dehmer, Global information processing in gene networks: fault tolerance, in: Proceedings of the Workshop on Computing and Communications from Biological Systems: Theory and Applications, in press. · Zbl 1141.92043
[16] Fradkov, A.L., Cybernetical physics: from control of chaos to quantum control, (2007), Springer · Zbl 1117.81002
[17] Godsil, C.; Royle, G., Algebraic graph theory. graduate texts in mathematics, (2001), Academic Press
[18] Gutman, I.; Polansky, O.E., Mathematical concepts in organic chemistry, (1986), Springer · Zbl 0657.92024
[19] Harary, F., Structural models. an introduction to the theory of directed graphs, (1965), Wiley · Zbl 0139.41503
[20] Harary, F., Graph theory, (1969), Addison Wesley Publishing Company · Zbl 0797.05064
[21] J. Koerner, Coding of an information source having ambiguous alphabet and the entropy of graphs, in: Transactions of the Sixth Prague Conference on Information Theory, 1973, pp. 411-425.
[22] Lezon, T.R.; Banavar, J.R.; Cieplak, M.; Maritan, A.; Fedoroff, N.V., Using the principle of entropy maximization to infer genetic interaction networks from gene expression patterns, Proc. natl. acad. sci., 103, 50, 19033-19038, (2006)
[23] Luger, G.F., Artificial intelligence: structures and strategies for complex problem solving, (2004), Addison Wesley
[24] Mowshowitz, A., Entropy and the complexity of graphs. II: the information content of digraphs and infinite graphs, Bull. math. biophys., 30, 225-240, (1968) · Zbl 0165.57602
[25] Mowshowitz, A., Entropy and the complexity of graphs. III: graphs with prescribed information content, Bull. math. biophys., 30, 387-414, (1968) · Zbl 0165.57603
[26] Mowshowitz, A., Entropy and the complexity of graphs. IV: entropy measures and graphical structure, Bull. math. biophys., 30, 533-546, (1968) · Zbl 0204.24603
[27] Mowshowitz, A., Entropy and the complexity of the graphs. I: an index of the relative complexity of a graph, Bull. math. biophys., 30, 175-204, (1968) · Zbl 0165.57601
[28] Negotia, C.V., Cybernetics and applied systems, (1992), CRC Press
[29] Rashewsky, N., Life, information theory, and topology, Bull. math. biophys., 17, 229-235, (1955)
[30] Scott, F., Social network analysis, (2001), Sage Publications
[31] Skorobogatov, V.A.; Dobrynin, A.A., Metrical analysis of graphs, Match, 23, 105-155, (1988) · Zbl 0666.05065
[32] Trinajstivć, N., Chemical graph theory, (1992), CRC Press
[33] Trucco, E., A note on the information content of graphs, Bull. math. biol., 18, 2, 129-135, (1956)
[34] Wasserman, S.; Faust, K., Social network analysis: methods and applications, Structural analysis in the social sciences, (1994), Cambridge University Press
[35] Zurek, W.H., Complexity, entropy and the physics of information, (1990), Westview Press · Zbl 0800.94140
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.