Related Experiment Video
Updated: Oct 6, 2025
08:46
Analysis and Specification of Starch Granule Size Distributions
Published on: March 4, 2021
5.3K
Structural Entropy of the Stochastic Block Models
Jie Han1, Tao Guo1, Qiaoqiao Zhou2
1Theory Lab, Central Research Institute, 2012 Labs, Huawei Tech. Co., Ltd., Hong Kong SAR, China.
Entropy (Basel, Switzerland)
|January 21, 2022
Summary
This study introduces partitioned structural entropy for stochastic block models, enabling efficient data compression by preserving essential network structures. An optimal compression algorithm is presented, achieving near-perfect data compression for complex networks.
Area of Science:
- Network science
- Information theory
- Data compression
Background:
- Graphs and networks are rapidly expanding, necessitating effective data compression methods.
- Compressing data while retaining structural information, ignoring specific labels, is a key challenge.
- Previous work defined structural entropy for unlabeled graphs and developed an optimal compression algorithm.
Purpose of the Study:
- To generalize structural entropy to stochastic block models with multiple partitions.
- To define and compute partitioned structural entropy for these models.
- To develop a compression scheme that achieves this new entropy limit.
Main Methods:
- Definition of partitioned structural entropy for stochastic block models.
- Computation of this entropy for arbitrary numbers of partitions.
- Development of a compression algorithm based on the defined entropy.
Main Results:
- The partitioned structural entropy for stochastic block models was successfully defined and computed.
- A compression scheme was developed that asymptotically achieves the partitioned structural entropy limit.
- The method generalizes previous work on unlabeled graphs.
Conclusions:
- The proposed partitioned structural entropy provides a framework for understanding and compressing structured network data.
- The developed compression scheme offers an efficient way to handle large-scale network data.
- This work advances the field of network data compression and information theory.
Related Concept Videos
02:39Entropy
31.8K
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...
31.8K
02:38Third Law of Thermodynamics
19.8K
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.
19.8K
01:14The Second Law of Thermodynamics
5.9K
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...
5.9K
01:10Entropy Change in Reversible Processes
2.8K
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.
2.8K
01:20Entropy and the Second Law of Thermodynamics
3.3K
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...
3.3K
02:49Second Law of Thermodynamics
24.6K
In the quest to identify a property that may reliably predict the spontaneity of a process, a promising candidate has been identified: entropy. Processes that involve an increase in entropy of the system (ΔS > 0) are very often spontaneous; however, examples to the contrary are plentiful. By expanding consideration of entropy changes to include the surroundings, a significant conclusion regarding the relation between this property and spontaneity may be reached. In thermodynamic...
24.6K