Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFast computation of von Neumann entropy for large-scale graphs via quadratic approximations
62
0
0.0
(
0
)
Added by
Hang Hu
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The von Neumann graph entropy (VNGE) can be used as a measure of graph complexity, which can be the measure of information divergence and distance between graphs. However, computing VNGE is extensively demanding for a large-scale graph. We propose novel quadratic approximations for fast computing VNGE. Various inequalities for error between the quadratic approximations and the exact VNGE are found. Our methods reduce the cubic complexity of VNGE to linear complexity. Computational simulations on random graph models and various real network datasets demonstrate superior performance.
rate research
Read More
The von Neumann graph entropy is a measure of graph complexity based on the Laplacian spectrum. It has recently found applications in various learning tasks driven by networked data. However, it is computational demanding and hard to interpret using simple structural patterns. Due to the close relation between Lapalcian spectrum and degree sequence, we conjecture that the structural information, defined as the Shannon entropy of the normalized degree sequence, might be a good approximation of the von Neumann graph entropy that is both scalable and interpretable. In this work, we thereby study the difference between the structural information and von Neumann graph entropy named as {em entropy gap}. Based on the knowledge that the degree sequence is majorized by the Laplacian spectrum, we for the first time prove the entropy gap is between $0$ and $log_2 e$ in any undirected unweighted graphs. Consequently we certify that the structural information is a good approximation of the von Neumann graph entropy that achieves provable accuracy, scalability, and interpretability simultaneously. This approximation is further applied to two entropy-related tasks: network design and graph similarity measure, where novel graph similarity measure and fast algorithms are proposed. Our experimental results on graphs of various scales and types show that the very small entropy gap readily applies to a wide range of graphs and weighted graphs. As an approximation of the von Neumann graph entropy, the structural information is the only one that achieves both high efficiency and high accuracy among the prominent methods. It is at least two orders of magnitude faster than SLaQ with comparable accuracy. Our structural information based methods also exhibit superior performance in two entropy-related tasks.
We consider in this work the problem of minimizing the von Neumann entropy under the constraints that the density of particles, the current, and the kinetic energy of the system is fixed at each point of space. The unique minimizer is a self-adjoint positive trace class operator, and our objective is to characterize its form. We will show that this minimizer is solution to a self-consistent nonlinear eigenvalue problem. One of the main difficulties in the proof is to parametrize the feasible set in order to derive the Euler-Lagrange equation, and we will proceed by constructing an appropriate form of perturbations of the minimizer. The question of deriving quantum statistical equilibria is at the heart of the quantum hydrody-namical models introduced by Degond and Ringhofer in [5]. An original feature of the problem is the local nature of constraints, i.e. they depend on position, while more classical models consider the total number of particles, the total current and the total energy in the system to be fixed.
We prove the existence of a universal recovery channel that approximately recovers states on a v. Neumann subalgebra when the change in relative entropy, with respect to a fixed reference state, is small. Our result is a generalization of previous results that applied to type-I v. Neumann algebras by Junge at al. [arXiv:1509.07127]. We broadly follow their proof strategy but consider here arbitrary v. Neumann algebras, where qualitatively new issues arise. Our results hinge on the construction of certain analytic vectors and computations/estimations of their Araki-Masuda $L_p$ norms. We comment on applications to the quantum null energy condition.
Assessing whether a given network is typical or atypical for a random-network ensemble (i.e., network-ensemble comparison) has widespread applications ranging from null-model selection and hypothesis testing to clustering and classifying networks. We develop a framework for network-ensemble comparison by subjecting the network to stochastic rewiring. We study two rewiring processes, uniform and degree-preserved rewiring, which yield random-network ensembles that converge to the Erdos-Renyi and configuration-model ensembles, respectively. We study convergence through von Neumann entropy (VNE), a network summary statistic measuring information content based on the spectra of a Laplacian matrix, and develop a perturbation analysis for the expected effect of rewiring on VNE. Our analysis yields an estimate for how many rewires are required for a given network to resemble a typical network from an ensemble, offering a computationally efficient quantity for network-ensemble comparison that does not require simulation of the corresponding rewiring process.
An alternative method is presented for extracting the von Neumann entropy $-operatorname{Tr} (rho ln rho)$ from $operatorname{Tr} (rho^n)$ for integer $n$ in a quantum system with density matrix $rho$. Instead of relying on direct analytic continuation in $n$, the method uses a generating function $-operatorname{Tr} { rho ln [(1-z rho) / (1-z)] }$ of an auxiliary complex variable $z$. The generating function has a Taylor series that is absolutely convergent within $|z|<1$, and may be analytically continued in $z$ to $z = -infty$ where it gives the von Neumann entropy. As an example, we use the method to calculate analytically the CFT entanglement entropy of two intervals in the small cross ratio limit, reproducing a result that Calabrese et al. obtained by direct analytic continuation in $n$. Further examples are provided by numerical calculations of the entanglement entropy of two intervals for general cross ratios, and of one interval at finite temperature and finite interval length.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
