Random Chemistry (RC)

A bare-bones implementation of the 'Random Chemistry' (RC) algorithm for finding a defective set.
46 descargas
Actualizado 11 Sep 2019

Ver licencia

This is a bare-bones implementation of the 'Random Chemistry' (RC) algorithm for finding a defective set from a universal set of N elements in log(N) trials. Multiple calls to this function comprise statistically independent trials.

Included with the algorithm implementation are a dummy fitness function and 'defective sets' to test the algorithm. See the accompanying algorithm, 'Sampling Inspired by Group Hyperedge Testing' (SIGHT), which can also be used to find defective sets in log(N) trials. SIGHT uses the same dummy fitness function and defective sets, for easy comparison, and is available on the File Exchange at: https://www.mathworks.com/matlabcentral/fileexchange/72718-sampling-inspired-by-group-hyperedge-testing-sight. Both algorithms have been successfully applied to identify small sets of transmission lines whose simultaneous failures cause cascading blackouts in power grid simulations (see reference below).

DISCLAIMER: This implementation is designed to be easy to read and understand, but is NOT optimized for efficiency and omits all the book-keeping and options under development that are contained in our working code. This should really be viewed as readable pseudo-code that runs.

COPYRIGHT: Laurence A. Clarfeld and Margaret J. Eppstein, Department of Computer Science, Univ. of Vermont
DATE: 8/26/2019

You are free to use or modify this code for research purposes, as long as you reference the website where you obtained the code.
IF YOU PUBLISH ANYTHING USING THIS CODE OR ALGORITHM, PLEASE REFERENCE THE FOLLOWING PAPERS:

1. Eppstein, Margaret J., and Paul DH Hines. "A “random chemistry” algorithm for identifying collections of multiple contingencies that initiate cascading failure." IEEE Transactions on Power Systems 27.3 (2012): 1698-1705.

2. Rezaei, Pooya, Margaret J. Eppstein, and Paul DH Hines. "Rapid Assessment, Visualization, and Mitigation of Cascading Failure Risk in Power Systems." System Sciences (HICSS), 2015 48th Hawaii International Conference on. IEEE, 2015.

3. Clarfeld, L.A., and Eppstein, M.J. "Group-Testing on Hypergraphs with Variable-Cost Tests: A Power Systems Case Study", arXiv:1909.04513 [physics.soc-ph] (Preprint). September 9, 2019. Available from: https://arxiv.org/abs/1909.04513

Citar como

Eppstein, Margaret J., and Paul DH Hines. "A “random chemistry” algorithm for identifying collections of multiple contingencies that initiate cascading failure." IEEE Transactions on Power Systems 27.3 (2012): 1698-1705.

Rezaei, Pooya, Margaret J. Eppstein, and Paul DH Hines. "Rapid Assessment, Visualization, and Mitigation of Cascading Failure Risk in Power Systems." System Sciences (HICSS), 2015 48th Hawaii International Conference on. IEEE, 2015.

Clarfeld, L.A., and Eppstein, M.J. "Group-Testing on Hypergraphs with Variable-Cost Tests: A Power Systems Case Study", arXiv:1909.04513 [physics.soc-ph] (Preprint). September 9, 2019. Available from: https://arxiv.org/abs/1909.04513

Compatibilidad con la versión de MATLAB
Se creó con R2018a
Compatible con cualquier versión
Compatibilidad con las plataformas
Windows macOS Linux
Categorías
Más información sobre Graph and Network Algorithms en Help Center y MATLAB Answers.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Versión Publicado Notas de la versión
1.0.1

Updated "Description" to add link to SIGHT code and updated citations.

1.0.0