Sampling of cycles in graphs for material networks

Defining an appropriate method for computing the cycles of a graph is complex. Sampling all cycles is intractable for large graphs because the number of simple cycles grows exponentially with the number of nodes. Instead, the conventional approach is to treat the set of cycles as a vector space where addition is given by the symmetric difference and the scalars are 0 and 1. Then, cycles are sampled from a minimum cycle basis (MCB), a basis of the cycle space that minimizes cycle lengths (Kavitha et al. 2009). However, MCBs are not unique. We construct an algorithm that samples the MCBs of a graph uniformly at random. The theory for this approach expands upon the works (Vismara 1997, Gleiss et al. 2000, Kolodzik et al. 2012). A random MCB is not deterministic, but it is statistically well-defined. We also introduce a postprocessing step so that each pair of cycles in the MCB intersects over at most one path. We define a dual graph whose nodes represent cycles in the MCB and edges represent their intersection paths. These concepts and algorithms are appropriate for the study of hydrocarbon pyrolysis, a complex chemical reaction system of carbon and hydrogen at extreme temperatures and pressures. In hydrocarbon pyrolysis simulations, we observe a phase transition for a giant component in the dual graph, or a macroscopic cluster of intersecting carbon rings.