A history of graph entropy measures

Information Sciences - Tập 181 - Trang 57-78 - 2011
Matthias Dehmer1,2, Abbe Mowshowitz3
1Institute for Bioinformatics and Translational Research, UMIT, Eduard Wallnoefer Zentrum 1, A-6060 Hall in Tyrol, Austria
2Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria
3Department of Computer Science, The City College of New York (CUNY), 138th Street at Convent Avenue, New York, NY, 10031, USA

Tài liệu tham khảo

Allen, 2002, Measuring graph abstractions of software: an information-theory approach, 182 Altay, 2010, Revealing differences in gene network inference algorithms on the network-level by ensemble methods, Bioinformatics, 26, 1738, 10.1093/bioinformatics/btq259 Anand, 2009, Entropy measures for networks: toward an information theory of complex topologies, Physical Review E, 80, 045102(R), 10.1103/PhysRevE.80.045102 Antiqueira, 2009, Characterization of subgraph relationships and distribution in complex networks, New Journal of Physics, 11, 10.1088/1367-2630/11/1/013058 Balaban, 1991, New vertex invariants and topological indices of chemical graphs based on information on distances, Journal of Mathematical Chemistry, 8, 383, 10.1007/BF01166951 Balch, 2001, Hierarchic social entropy: an information theoretic measure of robot group diversity, Autonomous Robots, 8, 209, 10.1023/A:1008973424594 Barabási, 1999, Emergence of scaling in random networks, Science, 286, 509, 10.1126/science.286.5439.509 Bertz, 1981, The first general index of molecular complexity, Journal of the American Chemical Society, 103, 3241, 10.1021/ja00402a071 Bertz, 1983, On the complexity of graphs and molecules, Bulletin of Mathematical Biology, 45, 849, 10.1007/BF02460054 Boccaletti, 2006, Complex networks: structure and dynamics, Physics Reports, 424, 175, 10.1016/j.physrep.2005.10.009 Bonchev, 1983 Bonchev, 2000, Overall connectivities and topological complexities: a new powerful tool for QSPR/QSAR, Journal of Chemical Information and Computer Science, 40, 934, 10.1021/ci990120u Bonchev, 2003 Bonchev, 2005 Bonchev, 1977, Information theory distance matrix and molecular branching, Journal of Chemical Physics, 67, 4517, 10.1063/1.434593 S. Borgert, M. Dehmer, E. Aitenbichler, On quantitative network complexity measures for business process models, Acta Universitates Apulensis, 18, in press. Bornholdt, 2003 Brandes, 2001, A faster algorithm for betweenness centrality, Journal of Mathematical Sociology, 25, 163, 10.1080/0022250X.2001.9990249 Butts, 2001, The complexity of social networks: theoretical and empirical findings, Social Networks, 23, 31, 10.1016/S0378-8733(01)00030-2 Chanda, 2009, Information-theoretic gene-gene and gene-environment interaction analysis of quantitative traits, BMC Genomics, 10, 509, 10.1186/1471-2164-10-509 Claussen, 2007, Characterization of networks by the offdiagonal complexity, Physica A, 375, 365, 10.1016/j.physa.2006.08.067 Cook, 1998 Cover, 2006 Csiszár, 1990, Entropy splitting for antiblocking corners and perfect graphs, Combinatorica, 10, 27, 10.1007/BF02122693 Costa, 2007, Characterization of complex networks: a survey of measurements, Advances in Physics, 56, 167, 10.1080/00018730601170527 Costa, 2009, Seeking for simplicity in complex networks, Europhysics Letters, 85, 48001(1), 10.1209/0295-5075/85/48001 Costa, 2009, Beyond the average: detecting global singular nodes from local features in complex networks, Europhysics Letters, 87, 18008(1), 10.1209/0295-5075/87/18008 Dehmer, 2008, Information-theoretic concepts for the analysis of complex networks, Applied Artificial Intelligence, 22, 684, 10.1080/08839510802164101 Dehmer, 2008, A novel method for measuring the structural information content of networks, Cybernetics and Systems, 39, 825, 10.1080/01969720802435925 Dehmer, 2008, Entropy bounds for molecular hierarchical networks, PLoS ONE, 3, e3079, 10.1371/journal.pone.0003079 Dehmer, 2008, Structural information content of networks: graph entropy based on local vertex functionals, Computational Biology and Chemistry, 32, 131, 10.1016/j.compbiolchem.2007.09.007 Dehmer, 2009, Towards network complexity, vol. 4, 707 M. Dehmer, A. Mehler, F. Emmert-Streib, Graph-theoretical characterizations of generalized trees, in: Proceedings of the International Conference on Machine Learning: Models, Technologies & Applications (MLMTA’07), Las Vegas/USA, 2007, pp. 113–117, 2007. Dehmer, 2010, Inequalities for entropy-based measures of network information content, Applied Mathematics and Computation, 215, 4263, 10.1016/j.amc.2009.12.051 Dehmer, 2009, On entropy-based molecular descriptors: statistical analysis of real and synthetic chemical structures, Journal of Chemical Information and Modelling, 49, 1655, 10.1021/ci900060x Dijkstra, 1959, A note on two problems in connection with graphs, Numerische Math., 1, 269, 10.1007/BF01386390 Dorogovtsev, 2003 Dragomir, 1997, Some bounds on entropy measures in information theory, Applied Mathematics Letters, 10, 23, 10.1016/S0893-9659(97)00028-1 Emmert-Streib, 2007, Information theoretic measures of UHG graphs with low computational complexity, Applied Mathematics and Computation, 190, 1783, 10.1016/j.amc.2007.02.095 Emmert-Streib, 2007, Topological mappings between graphs trees and generalized trees, Applied Mathematics and Computation, 186, 1326, 10.1016/j.amc.2006.07.162 Emmert-Streib, 2009, Fault tolerance of information processing in gene networks, Physica A, 338, 541, 10.1016/j.physa.2008.10.032 F. Emmert-Streib, M. Dehmer, J. Kilian, Classification of large graphs by a local tree decomposition, in: H.R. Arabnia, A. Scime (Eds.), Proceedings of DMIN’05, International Conference on Data Mining, Las Vegas, USA, 2005, pp. 200–207. Everett, 1985, Role similarity and complexity in social networks, Social Networks, 7, 353, 10.1016/0378-8733(85)90013-9 Freeman, 1983, Spheres cubes and boxes: graph dimensionality and network structure, Social Networks, 5, 139, 10.1016/0378-8733(83)90022-9 Halin, 1989 Harary, 1969 Hirata, 1984, Information theoretical analysis of ecological networks, International Journal of Systems Science, 15, 261, 10.1080/00207728408926559 Hosoya, 1971, Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bulletin of the Chemistry Society of Japan, 44, 2332, 10.1246/bcsj.44.2332 Jain, 1988 Jiang, 2004, A structural approach to the model generalization of an urban street network, Geoinformatica, 8, 157, 10.1023/B:GEIN.0000017746.44824.70 Kim, 2010, Learning biological network using mutual information and conditional independence, BMC Bioinformatics, 11, S9, 10.1186/1471-2105-11-S3-S9 Kim, 2008, What is a complex graph?, Physica A, 387, 2637, 10.1016/j.physa.2008.01.015 Konstantinova, 1990, Sensitivity of topological indices of polycyclic graphs, Vychisl. Sistemy., 136, 38 Konstantinova, 2002, Applications of information theory in chemical graph theory, Indian Journal of Chemistry, 42, 1227 J. Körner, 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,. Kullback, 1951, On information and sufficiency, Annals of Mathematical Statistics, 22, 79, 10.1214/aoms/1177729694 A.M. Latva-Koivisto. Finding a complexity measure for business process models, Technical report, Helsinki University of Technology, 2001. Li, 1991, Combinatorics and kolmogorov complexity Lu, 2008, Quantifying organization by means of entropy, Communications Letters IEEE, 12, 185, 10.1109/LCOMM.2008.071923 Luce, 1967 Maruyama, 2010, Interocular yoking in human saccades examined by mutual information analysis, Nonlinear Biomedical Physics, 4, S10, 10.1186/1753-4631-4-S1-S10 2009 Mehler, 2004, Towards logical hypertext structure — A graph-theoretic perspective, vol. 3473, 136 Minoli, 1975, Combinatorial graph complexity, Atti. Accad. Naz. Lincei, VIII. Ser., Rend., Cl. Sci. Fis. Mat. Nat., 59, 651 Morowitz, 1953, Some order-disorder considerations in living systems, Bulletin of Mathematical Biophysics, 17, 81, 10.1007/BF02477985 Mowshowitz, 1968, Entropy and the complexity of graphs II: the information content of digraphs and infinite graphs, Bulletin of Mathematical Biophysics, 30, 225, 10.1007/BF02476692 Mowshowitz, 1968, Entropy and the complexity of graphs III: graphs with prescribed information content, Bulletin of Mathematical Biophysics, 30, 387, 10.1007/BF02476603 Mowshowitz, 1968, Entropy and the complexity of graphs IV: entropy measures and graphical structure, Bulletin of Mathematical Biophysics, 30, 533, 10.1007/BF02476673 Mowshowitz, 1968, Entropy and the complexity of the graphs I: an index of the relative complexity of a graph, Bulletin of Mathematical Biophysics, 30, 175, 10.1007/BF02476948 Newman, 2006 Nikolić, 2000, Complexity of molecules, J. Chem. Inf. Comput. Sci., 40, 920, 10.1021/ci9901183 Passerini, 2009, The von neumann entropy of networks, International Journal of Agent Technologies and Systems, 1, 58, 10.4018/jats.2009071005 Quastler, 1954, Information theory in biology, Bulletin of Mathematical Biology, 183 Randić, 1975, On characterization of molecular branching, Journal of the American Chemical Society, 97, 6609, 10.1021/ja00856a001 Randić, 2002, Characterization of molecular complexity, International Journal of Quantum Chemistry, 91, 20, 10.1002/qua.10343 Randić, 2002, On the concept of molecular complexity, Croatica Chemica Acta, 75, 107 Rashevsky, 1955, Life information theory and topology, Bulletin of Mathematical Biophysics, 17, 229, 10.1007/BF02477860 Raychaudhury, 1984, Discrimination of isomeric structures using information theoretic topological indices, Journal of Computational Chemistry, 5, 581, 10.1002/jcc.540050612 Shannon, 1949 G. Simonyi, Graph entropy: a survey, in: W. Cook, L. Lovász, P. Seymour (Eds.), Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 20, 1995, pp. 399–441. Simonyi, 2001, Perfect graphs and graph entropy. An updated survey, 293 Skorobogatov, 1988, Metrical analysis of graphs, Communications in Mathematical and in Computer Chemistry, 23, 105 R.V. Solé, S. Valverde, Information theory of complex networks: on evolution and architectural constraints, in: Lecture Notes in Physics, vol. 650, 2004, pp. 189–207. Thurner, 2009, Statistical mechanics of complex networks, 23 Todeschini, 2002 Trucco, 1956, A note on the information content of graphs, Bulletin of Mathematical Biology, 18, 129 Türker, 2003, Contemplation on the hosoya indices, Journal of Molecular Structure (Theochem), 623, 75, 10.1016/S0166-1280(02)00664-4 Tutzauer, 2007, Entropy as a measure of centrality in networks characterized by path-transfer flow, Social Networks, 29, 249, 10.1016/j.socnet.2006.10.001 Ulanowicz, 2001, Information theory in ecology, Computers and Chemistry, 25, 393, 10.1016/S0097-8485(01)00073-0 Ulanowicz, 2004, Quantitative methods for ecological network analysis, Computational Biology and Chemistry, 28, 321, 10.1016/j.compbiolchem.2004.09.001 Wasserman, 1994 Wiener, 1947, Structural determination of paraffin boiling points, Journal of the American Chemical Society, 69, 17, 10.1021/ja01193a005 Wilhelm, 2001, Information theoretic measures for the maturity of ecosystems, 263 Xie, 2007, Measuring the structure of road networks, Geographical Analysis, 39, 336, 10.1111/j.1538-4632.2007.00707.x Yockey, 1992