Studying and Visualizing Contagion on Graphs
PublicDownloadable Content
open in viewerIn this report, we investigate the NP-complete minimum contagious set problem in bootstrap percolation. We present the following: three new bounds providing approximations for the size of minimum contagious sets, efficient and optimal algorithms for special types of graphs, and an optimal algorithm for any graph. Furthermore, we created a publicly available software product named `Booper', a web application that can help mathematicians research and visualize bootstrap percolation. Users of Booper are able to upload a custom graph, find the minimum contagious set of a graph, perform iterations of bootstrap percolation with user-defined threshold and probability parameters, and much more.
- This report represents the work of one or more WPI undergraduate students submitted to the faculty as evidence of completion of a degree requirement. WPI routinely publishes these reports on its website without editorial or peer review.
- Creator
- Publisher
- Identifier
- E-project-050421-171326
- 22011
- Keyword
- Award
- Advisor
- Year
- 2021
- Date created
- 2021-05-04
- Resource type
- Major
- Rights statement
- License
- Last modified
- 2023-01-19
Relations
- In Collection:
Items
Items
Thumbnail | Title | Visibility | Embargo Release Date | Actions |
---|---|---|---|---|
bootstrap-percolation-mqp.pdf | Public | Download |
Permanent link to this page: https://digital.wpi.edu/show/6d570066m