Related Experiment Videos
Properties of random graphs with hidden color
1Complex Systems Division, Department of Theoretical Physics, Lund University, Lund, Sweden. Bo.Soderberg@thep.lu.se
Summary
This study introduces a new class of random graph ensembles using hidden stub coloring. These ensembles allow for the calculation of graph properties and reveal a clear percolation threshold.
Area of Science:
- Graph theory
- Statistical physics
- Network science
Background:
- Random graphs are fundamental in modeling complex systems.
- Existing models may not capture all desired structural properties.
- A general class of ensembles based on hidden stub coloring has been proposed.
Purpose of the Study:
- To investigate a general class of sparse undirected random graph ensembles.
- To demonstrate the calculability of graph properties within these ensembles.
- To analyze structural properties like cluster statistics and subgraph enumeration.
Main Methods:
- Utilizing generating function techniques to derive cluster size statistics.
- Developing explicit rules for enumerating small subgraphs.
- Analyzing properties with and without the restriction to nondegenerate graphs.
Main Results:
- Demonstrated calculability of local and global structural properties.
- Derived cluster size statistics, identifying a well-defined percolation threshold.
- Established explicit rules for subgraph enumeration and discussed duality and redundancy.
Conclusions:
- The proposed random graph ensembles are mathematically tractable.
- These ensembles provide a flexible framework for studying network structures.
- Subclasses of commonly studied random graph models can be identified within this framework.