Demystification of Graph and Information Entropy

Shannon entropy is an information-theoretic measure of unpredictability in probabilistic models. Recently, it has been used to form a tool, called the von Neumann entropy, to study quantum mechanics and network flows by appealing to algebraic properties of graph matrices. But still, little is known about what the von Neumann entropy says about the combinatorial structure of the graphs themselves. This paper gives a new formulation of the von Neumann entropy that describes it as a rate at which random movement settles down in a graph. At the same time, this new perspective gives rise to a generalization of von Neumann entropy to directed graphs, thus opening a new branch of research. Finally, it is conjectured that a directed cycle maximizes von Neumann entropy for directed graphs on a fixed number of vertices