The von Neumann entropy of networks

Passerini, Filippo and Severini, Simone (2008): The von Neumann entropy of networks.

Abstract

We normalize the combinatorial Laplacian of a graph by the degree sum, look at its eigenvalues as a probability distribution and then study its Shannon entropy. Equivalently, we represent a graph with a quantum mechanical state and study its von Neumann entropy. At the graph-theoretic level, this quantity may be interpreted as a measure of regularity; it tends to be larger in relation to the number of connected components, long paths and nontrivial symmetries. When the set of vertices is asymptotically large, we prove that regular graphs and the complete graph have equal entropy, and specifically it turns out to be maximum. On the other hand, when the number of edges is fixed, graphs with large cliques appear to minimize the entropy.

• Item Type: MPRA Paper
• Language: English
• Keywords: Networks
• Subjects: C - Mathematical and Quantitative Methods > C0 - General > C02 - Mathematical Methods

References

[1] G. Bianconi, The entropy of network ensembles. arXiv:0802.2888v2 [cond-mat.dis-nn]

[2] N. Biggs, Algebraic Graph Theory, Cambridge, UK: Cambridge University Press, 1993.

[3] B. B. Blinov, D. L. Moehring, L.-M. Duan, and C. Monroe, Nature 428, 153 (2004).

[4] S. Bose, Contemporary Physics, Vol. 48 (1), pp. 13-30, 2007. arXiv:0802.1224v1 [cond-mat.other]

[5] S. Braunstein, S. Ghosh, S. Severini, The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states, Ann. of Combinatorics, 10, no 3 (2006), 291-317.

[6] H.-J. Briegel and R. Raussendorf, Phys. Rev. Lett. 86, 910 (2001).

[7] D. Bonchev and G. A. Buck, Quantitative Measures of Network Complexity. In: Complexity in Chemistry, Biology and Ecology, D. Bonchev and D. H. Rouvray, Eds., Springer, New York, 2005, p. 191-235.

[8] T. Cover and J. Thomas, Elements of information theory, John Wiley, New York, 1991.

[9] F. R. K. Chung, Spectral graph theory, CBMS Regional Conference Series in Mathematics, 92. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.

[10] D. M. Cvetkovic, M. Doob, H. Sachs, Spectra of graph theory and applications, VEB Deutscher Berlin, Academic Press, New York, 1979.

[11] A. M. Duval and V. Reiner, Shifted simplicial complexes are Laplacian integral, Trans. Amer. Math. Soc., 354(11):4313-4344, 2002.

[12] E. Estrada, Characterization of the folding degree of proteins, Bioinformatics 18 (2002), pp. 697–704.

[13] E. Estrada and J. A. Rodr´ıguez-Vel´azquez, Subgraph centrality in complex networks, Phys. Rev. E 71 (2005), 1-9.

[14] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematics Journal, 23:298-305, 1973.

[15] L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry, 40, 35–41 (1977).

[16] R. Grone, R. Merris, V. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990), 218– 238.

[17] R. Grone, R. Merris, The Laplacian spectrum of a graph, II. SIAM J. Discrete Math. 7 (1994), no. 2, 221–229.

[18] I. Gutman, The energy of a graph, Ber. Math. Stat. Sekt. Forschungszentrum Graz., 103: 1-22 (1978).

[19] M. Hein, J. Eisert, and H.J. Briegel. Multi-party entanglement in graph states, Phys. Rev. A 69, 062311 (2004).

[20] R. Hildebrand, S. Mancini, S. Severini, Combinatorial laplacians and positivity under partial transpose, Math. Struct. in Comp. Science (2008), 18, 205–219.

[21] D. Kielpinski, C. Monroe, and D. J. Wineland, Nature 417, 709 (2002).

[22] F. Kirchhoff, ¨Uber die Aufl¨osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str¨ome gef¨uhrt wird. Ann. Phys. Chem. 72 (1847), 497—508.

[23] J. K¨orner, Coding of an information source having ambiguous alphabet and entropy of graphs, In Proc. 6th Prague Conference on Information Theory (1973), pp. 411–425.

[24] M. Lazi´c, On the Laplacian energy of a graph, Czechoslovak Math. J. 56(131) (2006), no. 4, 1207–1213.

[25] H. H. Lieb, M. B. Ruskai, Proof of the strong subadditivity of quantum-mechanical entropy, J. Math. Phys. 14, 1938–1941 (1973).

[26] L. Lov´asz, Random walks on graphs: a survey. Combinatorics, Paul Erd˝os is eighty, Vol. 2 (Keszthely, 1993), 353–397, Bolyai Soc. Math. Stud., 2, J´anos Bolyai Math. Soc., Budapest, 1996.

[27] B. Mohar, The Laplacian spectrum of graphs. Graph Theory, Combinatorics, and Applications, 2:871-898, 1991.

[28] J. von Neumann, Mathematische Grundlagen der Quantenmechanik, Berlin, 1932; English translation by R. T. Beyer, Mathematical Foundations of Quantum Mechanics, Princeton, 1955.

[29] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000.

[30] M. Ohya, D. Petz, Quantum entropy and its use. Texts and Monographs in Physics. Springer-Verlag, Berlin, 1993.

[31] S. Riis, Graph Entropy, Network Coding and Guessing games. arXiv:0711.4175v1 [math.CO]

[32] G. Simonyi, Graph entropy. In Combinatorial Optimization, L. L. W. Cook and P. Seymour, Eds., vol. 20 of DIMACS Series on Discrete Math and Computer Science. 1995, pp. 391–441.

[33] A. Terras, Fourier analysis on finite groups and applications, London Mathematical Society Student Texts, 43. Cambridge University Press, Cambridge (1999).

[34] V. Vedral, The role of relative entropy in quantum information theory, Reviews of Modern Physics, vol. 74, Issue 1, pp. 197-234