Entropy of Tournament Digraphs
Authors:
- David E. BrownDBDavid E. Brown
- Eric CulverECEric Culver
- Bryce FredericksonBFBryce Frederickson
- Sidney TateSTSidney Tate
- Brent J. ThomasBTBrent J. Thomas
Preprint
Abstract
The R\'{e}nyi $\alpha$-entropy $H_{\alpha}$ of complete antisymmetric directed graphs (i.e., tournaments) is explored. We optimize $H_{\alpha}$ when $\alpha = 2$ and $3$, and find that as $\alpha$ increases $H_{\alpha}$'s sensitivity to what we refer to as `regularity' increases as well. A regular tournament on $n$ vertices is one with each vertex having out-degree $\frac{n-1}{2}$, but there is a lot of diversity in terms of structure among the regular tournaments; for example, a regular tournament may be such that each vertex's out-set induces a regular tournament (a doubly-regular tournament) or a transitive tournament (a rotational tournament). As $\alpha$ increases, on the set of regular tournaments, $H_{\alpha}$ has maximum value on doubly regular tournaments and minimum value on rotational tournaments. The more `regular', the higher the entropy. We show, however, that $H_2$ and $H_3$ are maximized, among all tournaments on any number of vertices by any regular tournament. We also provide a calculation that is equivalent to the von Neumann entropy, but may be applied to any directed or undirected graph and shows that the von Neumann entropy is a measure of how quickly a random walk on the graph or directed graph settles.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- The on-line encyclopedia of integer sequencesNotices of the American Mathematical Society, 2018
- Shannon and von Neumann entropy of random networks with heterogeneous expected degreePhysical Review E, 2011
- A history of graph entropy measuresInformation Sciences, 2011
- The Laplacian of a Graph as a Density Matrix: A Basic Combinatorial Approach to Separability of Mixed StatesAnnals of Combinatorics, 2006