Related Experiment Video
Updated: Nov 27, 2025
08:08
Using Wavelet Entropy to Demonstrate how Mindfulness Practice Increases Coordination between Irregular Cerebral and Cardiac Activities
Published on: May 10, 2017
15.0K
Relating Vertex and Global Graph Entropy in Randomly Generated Graphs
Philip Tee1,2, George Parisis2, Luc Berthouze2
1Moogsoft Inc, San Francisco, CA 94111, USA.
Entropy (Basel, Switzerland)
|December 3, 2020
Summary
This study explores graph complexity measures. We found strong correlations between local vertex measures and global entropy in random graphs, suggesting simpler calculations for graph complexity.
Area of Science:
- Graph theory
- Information theory
- Network analysis
Background:
- Combinatoric entropy measures graph complexity using independent sets, but this is computationally intractable (NP-Complete) for large graphs.
- Vertex-level measures offer a computationally feasible alternative for quantifying graph complexity.
- Previous research by Dehmer et al. and Tee et al. highlighted the potential of these local measures.
Purpose of the Study:
- To investigate the fundamental equivalence between local vertex-level complexity measures and global graph entropy measures.
- To determine if computationally accessible local measures can effectively represent global graph entropy.
- To explore the correlation between these measures in a specific class of random graphs.
Main Methods:
- Utilized a greedy algorithm approximation to compute chromatic information, serving as a proxy for Körner entropy.
- Focused analysis on a narrow subset of random graphs to facilitate the investigation.
- Compared results from local vertex-level complexity calculations with global entropy estimations.
Main Results:
- Demonstrated a strong correlation between local vertex-level measures and global entropy measures for the studied subset of random graphs.
- The findings suggest that local measures can effectively approximate global graph entropy in certain contexts.
- Identified potential theoretical underpinnings for the observed strong correlation.
Conclusions:
- Local vertex-level measures show significant promise as computationally efficient proxies for global graph entropy.
- The strong correlation observed supports the utility of these simpler measures in assessing graph complexity.
- Further theoretical work is warranted to fully understand the relationship and its implications across broader graph classes.
More Related Videos
11:15Applications of EEG Neuroimaging Data: Event-related Potentials, Spectral Power, and Multiscale Entropy
Published on: June 27, 2013
34.2K
11:00Experimental Investigation of Secondary Flow Structures Downstream of a Model Type IV Stent Failure in a 180° Curved Artery Test Section
Published on: July 19, 2016
11.8K
Related Concept Videos
02:39Entropy
33.7K
Salt particles that have dissolved in water never spontaneously come back together in solution to reform solid particles. Moreover, a gas that has expanded in a vacuum remains dispersed and never spontaneously reassembles. The unidirectional nature of these phenomena is the result of a thermodynamic state function called entropy (S). Entropy is the measure of the extent to which the energy is dispersed throughout a system, or in other words, it is proportional to the degree of disorder of a...
33.7K
01:18Entropy
3.3K
The first law of thermodynamics is quantitatively formulated via an equation relating the internal energy of a system, the heat exchanged by it, and the work done on it. A quantitative formulation of the second law of thermodynamics leads to defining a state function, the entropy.
When an ideal gas expands isothermally, the disorder in the gas increases. From the molecular perspective, the gas molecules have more volume to move around in.
Consider an infinitesimal step in the expansion, which...
When an ideal gas expands isothermally, the disorder in the gas increases. From the molecular perspective, the gas molecules have more volume to move around in.
Consider an infinitesimal step in the expansion, which...
3.3K
02:38Third Law of Thermodynamics
21.0K
A pure, perfectly crystalline solid possessing no kinetic energy (that is, at a temperature of absolute zero, 0 K) may be described by a single microstate, as its purity, perfect crystallinity,and complete lack of motion means there is but one possible location for each identical atom or molecule comprising the crystal (W = 1). According to the Boltzmann equation, the entropy of this system is zero.
21.0K
01:20Entropy and the Second Law of Thermodynamics
4.0K
The second law of thermodynamics can be stated quantitatively using the concept of entropy. Entropy is the measure of disorder of the system.
The relation between entropy and disorder can be illustrated with the example of the phase change of ice to water. In ice, the molecules are located at specific sites giving a solid state, whereas, in a liquid form, these molecules are much freer to move. The molecular arrangement has therefore become more randomized. Although the change in average...
The relation between entropy and disorder can be illustrated with the example of the phase change of ice to water. In ice, the molecules are located at specific sites giving a solid state, whereas, in a liquid form, these molecules are much freer to move. The molecular arrangement has therefore become more randomized. Although the change in average...
4.0K
01:14The Second Law of Thermodynamics
6.3K
In the quest to identify a property that may reliably predict the spontaneity of a process, a promising candidate has been identified: entropy. Scientists refer to the measure of randomness or disorder within a system as entropy. High entropy means high disorder and low energy. To better understand entropy, think of a student’s bedroom. If no energy or work were put into it, the room would quickly become messy. It would exist in a very disordered state, one of high entropy. Energy must be...
6.3K
01:10Entropy Change in Reversible Processes
3.0K
In the Carnot engine, which achieves the maximum efficiency between two reservoirs of fixed temperatures, the total change in entropy is zero. The observation can be generalized by considering any reversible cyclic process consisting of many Carnot cycles. Thus, it can be stated that the total entropy change of any ideal reversible cycle is zero.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
3.0K