Hands-on Activity Graphing the Spread of Disease

Learning Objectives

After this activity, students should be able to:

• Use graph theory to complete depth first search (DFS) and breadth first search (BFS).
• Analyze of the spread of disease using Graph theory concepts.

Educational Standards

Each TeachEngineering lesson or activity is correlated to one or more K-12 science, technology, engineering or math (STEM) educational standards.

All 100,000+ K-12 STEM standards covered in TeachEngineering are collected, maintained and packaged by the Achievement Standards Network (ASN), a project of D2L (www.achievementstandards.org).

In the ASN, standards are hierarchically structured: first by source; e.g., by state; within source by type; e.g., science or mathematics; within type by subtype, then by grade, etc.

NGSS: Next Generation Science Standards - Science

Common Core State Standards - Math

International Technology and Engineering Educators Association - Technology

State Standards

Materials List

Each group needs:

• computer with Internet access and Java installed and appropriate editing software (Eclipse, NetBeans, Java_Editor, JCreator, Jedi, etc.)
• (optional) Android device with Bluetooth discovery application
• DFS and BFS Algorithms Instructions
• Bluetooth Analysis Project - Part 1: Project Setup
• Bluetooth Analysis Project - Part 2: Graph Analysis
• Bluetooth Analysis Project - Part 3: Class Files
• Java zip files for data collection and analysis (to be installed and used for the analysis using an appropriate editing software): Graphing the Spread of Disease Java and Graphing the Spread of Disease Java Jung
• graph paper or Microsoft Excel, to graph collected data
• Data Collection Tables
• Lab Report Checklist
• Graphing the Spread of Disease Assessment, one per student

Worksheets and Attachments

Pre-Req Knowledge

Knowledge of the Java programming language is required.

The teacher and students should have knowledge of graph theory including the following vocabulary terms: vertex, edge, adjacency list, adjacency matrix, depth first search (DFS) and breadth first search (BFS). For students, this knowledge can be gained in the associated lesson Making the Connection.

Introduction/Motivation

Graph theory is used by engineers in many different disciplines. Biomedical engineers use a process that is similar to what you will do in today's activity to simulate disease transmission. Graph theory can be used to represent the current state of the disease and help predict future spread of the disease. It is a very easy way to visually show the relationships present in a data set. Communication networks can be represented using graph theory as well as social networks like Facebook. Electrical and computer engineers use graph theory to show the relationships between components when designing new computer hardware like CPUs.

In this activity, you will explore the transmission of disease through a simulation. In our real-life simulation, you will determine who gets infected by the disease based on an individual's proximity to other people, who are infected, and by analyzing the data using graph theory concepts. Once the initial simulation is complete the students will develop possible solutions to preventing the spread of disease by changing the location of those who spread the infection.

The simulation will be ran again with the new location of the students. The students will analyze the data and reflect about the outcome of their second simulation.

Procedure

Background

This activity explores the application of graph theory, which is a visual representation for relationships present in a data set. In the activity, students model the collection of data related to how a disease is transmitted by collecting data on their proximity to others, based on the assumption that close proximity to an infected individual causes the disease to spread. The simulation activity is engaging because it uses a real-world application that affects all of us.

The data collection for this activity must be done before any analysis can be conducted. The method of data collection depends on whether or not Bluetooth devices are available; if not, data is collected manually. Both methods are outlined in detail in the Procedure section.

It is assumed that if you are reading and planning to use this activity that you are familiar with Java and Java editors since Java tools (such as the Java classes provided in the Attachments section) are the primary data analysis method of the activity. Complete step-by-step instructions are included in the attachments, which the teacher can use to learn the material as well as instruct students. If desired, print them out as student instruction sheets. So, if conducting with Bluetooth devices, the following documents provide the activity instructions: Part 1: Project Setup, Part 2: Graph Analysis, and Part 3: Class Files. The Java files for data collection and analysis are Graphing the Spread of Disease Java (zip), and Graphing the Spread of Disease Java Jung (zip). In addition, see examples from conducting the activity with students in Example Data and Graphs.

Before the Activity

• Review and familiarize yourself with all the instructions provided in the attachments.
• Decide if you are going to conduct multiple simulations (numerous trials) and if so, what they are. For example, multiple simulations could be performed to produce different datasets for each student. Or multiple simulations could mean that you re-conduct the proximity data collection experiment or set different condition for "infection" (such as 2/3 contacts result in infection, 1/3 contacts result in infection, etc.). Each simulation requires that students fill in separate data tables.
• Discuss possible ways to limit the spread of infection based on the inputs to run the simulation.
• Gather materials and make paper and digital copies of the necessary handouts and files.
• You need only make copies of one of the tables in the Data Collection Tables, depending on how the data is being collected. Also, make enough copies so students have a new table for each planned simulation/trial, if conducting more than one.
• Prepare for the students all the computers and attachments with instructions and Java files.

With the Students—Data Collection

After presenting the Introduction/Motivation content, hand out the data collection worksheets and have students collect data on their proximity to others, either by Bluetooth Android device or manually, following the pertinent steps below.

If Bluetooth Android devices are the collection method, have students use Bluetooth discovery to collect the data in the classroom with all students following these steps.

1. As you recall, we are collecting data that will be used to simulate disease transmission.
2. You are considered in close enough contact (proximity) to transmit the disease (with Bluetooth, this could mean everyone within 10 meters) when your Bluetooth devices discover other Bluetooth devices. Only Bluetooth devices participating in the simulation are considered.
3. Direct students to make their Bluetooth either "discoverable" or "not discoverable" and then every so often change their status randomly. This means that at any given time some devices are on (discoverable) while others are off (not discoverable). The device recognitions found via Bluetooth count as disease transmissions and need to be recorded.
4. Let's set a data collection time period of three minutes. (Make this three to five minutes or longer, as determined by the teacher.)
5. The Bluetooth detections must be noted so that the transmissions can be counted. So when another Bluetooth device is discovered, you must record in your data collection table (see Figure 1) all data related to that contact, including:

• which simulation is being conducted, if different trials are going to be conducted, for instance, to run simulations with different infection rates (contact only provides infection 2/3 times, etc.)
• UserID: the device name of the person recording data
• close proximity to UserID: the device name of who you came in contact with
• time of infection: The time of infection column is used to identify when the other data in the same line of the table was recorded, which is important because diseases have incubation periods and take time to run their course. Knowing the time of infection is critical to understanding the duration and onset of the disease. The UserID and time of infection will be used to sort the data when students combine all their data into one table.

  

6. Then have students collect data on their interactions within the course of their normal activities. They can freely move around the classroom during the collection period and do as they wish, as long as they follow any classroom rules and make sure to collect data as specified (described below). If some students want to remain at their desks, that is fine as well. Only those who are in close proximity to each other are exposed to the disease, so students sitting at desks away from others represent being isolated in remote areas where the disease is less likely to be transmitted.
7. Then the teacher should run additional simulations in order to collect different data sets, simply end the simulation, ask students to change or not change their Bluetooth status.
8. Before beginning the next simulation, get feedback from the students about how to limit the spread of the infection. Then begin the simulation again for another three minutes.

If Bluetooth Android devices are not available, have students collect proximity data manually within the classroom, following these steps.

1. As you recall, we are collecting data that will be used to simulate disease transmission.
2. First, let's set a proximity estimate, such as being within arm's length. That means that you are considered in close enough contact (proximity) to transmit the disease when you are within arm's length of another person.
3. Then, let's set a data collection time period of five minutes. (Make this three to five minutes or longer, as determined by the teacher.)
4. Every time you come in contact with another person, you must record it as a contact in your data collection table (see Figure 2). For each contact, record the following data:

• which simulation is being conducted, if different trials are going to be conducted (for instance, to run simulations with different infection rates [contact only provides infection 2/3 times, etc.])
• name of the person recording data
• name of the person who you came in contact with
• time of infection: The time of infection column is used to identify when the other data in the same line of the table was recorded, which is important because diseases have incubation periods and take time to run their course. Knowing the time of infection is critical to understanding the duration and onset of the disease. The name of the recorder and time of infection will be used to sort the data when students combine all their data into one table.

  

5. Then have students collect data on their interactions within the course of their normal activities. They can freely move around the classroom during the collection period and do as they wish, as long as they follow any classroom rules and make sure to collect data as specified (described below). If some students want to remain at their desks, that is fine as well. Only those who are in close proximity to each other are exposed to the disease, so students sitting at desks away from others represent being isolated in remote areas where the disease is less likely to be transmitted.
6. The teacher should run additional simulations (trials) in order to collect different data sets.
7. Before the next trial, discuss ways to limit the spread of the infection. Then talk about the pros and cons of implementing their suggestions in the real world. Repeat the simulation process again for another five minutes, filling in new data tables.

With the Students—Data Analysis

1. After collecting data (and depending on the data collected in the simulation), a number of questions could be answered through analysis of the data, such as:

• Which students are connected through close proximity to all other students?
• Given an initial infected individual, which students are infected?
• How could the spread of infection be minimized?

2. After some class analysis of the data, have student groups create graphs of nodes and edges representing their disease transmission simulations (see Figure 3).
3. Provide groups with the lab report checklist, assigning them to each create lab write-ups of the simulation that include the following components: procedure, data in table format, drawn graphs, data analysis, calculations (vertex list, edge list, adjacency matrix, adjacency list, DFS search, and BFS search) and conclusions.
4. Conclude by administering summative assessment graph theory problems, as described in the Assessment section.

   

Vocabulary/Definitions

adjacency list: An adjacency list for a graph has a row for each vertex and contains the vertex label followed by the vertex labels of adjacent vertices.

adjacency matrix: An adjacency matrix for a graph with n vertices is an n x n matrix where each entry (i, j) is a 1 if there is an edge in the graph between vertex i and j; otherwise the entry is 0.

breadth first search (BFS): An algorithm or method of graph traversal that considers a given node as the parent and connected nodes as children; BFS visits the sibling vertices before the child vertices.

child vertex: Nodes in a graph that are directly connected to the current node. If the first node (parent node) is selected, then one of the nodes connected to it is the child node. That child node then becomes a parent node, and a node connected to it becomes a child node.

depth first search (DFS): An algorithm or method of graph traversal that considers a given node as the parent and connected nodes as children; DFS visits the child vertices before visiting sibling vertices.

edge (edge graph): A connection between nodes.

graph theory: The study of mathematical structures (graphs) so as to model relationships between objects from a collection.

sibling vertex: Nodes in a graph that are on the same level as the child node, connected to the same parent node with a single edge. Sibling nodes may or may not be connected to each other.

six degrees of separation: The theory that everyone is six or fewer steps away from knowing any other person in the world. This theory implies that a chain of "friend to friend" can be made to connect any two people in the world in a maximum of six steps.

vertex list: A listing of all the vertices present in a graph.

vertex or node: The fundamental unit of which graphs are formed. Plural: vertices.

Assessment

Opening Questions: Review and confirm students' understanding of key pre-requisite concepts by asking the following questions:

• In the context of graph theory, what is an edge? (Answer: An edge is a connection between two vertices showing a relationship.)
• What are vertices? (Answer: Vertices are the points in the graph representing what is being analyzed. In a social network or disease transmission application, vertices are people. In a network, the vertices are computers and devices.)
• How can graph theory be applied to engineering? (Answer: Graph theory can be applied any time a visual representation of the relationships between objects is desired. For example, engineers use graph theory in computer networks [computer engineers], social networks and computer programming [software engineers], the arrangement and design of computer hardware [electrical and computer engineers].)
• How can the information obtained from graph theory lead to a solution to preventing the spread of disease? (Answer: By running computer simulations we can see which people may be infected the quickest. Knowing this enables emergency responders to know where to focus their efforts to prevent further spread of the infection.

Formative Assessment: While students are engaged in the activity, observe and verify these (or similar) assessment queries:

• Are students able to realize and record how the disease is being transmitted between people?
• Are students able to create graphs representing the data collected in the simulation?
• Do students understand the concepts of vertex, edge, depth first search and breadth first search?

Summary Lab Report: At activity end, have students each complete and turn in lab reports summarizing the activity, using the Lab Report Checklist to inform their report requirements. Use the same checklist as a grading rubric. Review their reports to assess their level of comprehension of the concepts.

Summative Assessment: Have students complete the five problems provided on the Graphing the Spread of Disease Assessment (as well as below) to gauge their understanding of graph theory. Answers are provided on the Graphing the Spread of Disease Assessment Answer Key.

Given the Figure 4 graph, answer the following questions:

1. What is the vertex list for this graph?
2. What is the edge list for this graph?
3. What is the adjacency matrix for this graph?
4. What is the adjacency list for this graph?
5. Starting at vertex 1 and using a DFS search, what would be the visitation order of the vertices? Do the same for a BFS search.

Copyright

Contributors

Supporting Program

Acknowledgements

The contents of this digital library curriculum were developed as a part of the RET in Engineering and Computer Science Site on Infusing Mobile Platform Applied Research into Teaching (IMPART) Program at the University of Nebraska-Omaha under National Science Foundation RET grant number CNS 1201136. However, these contents do not necessarily represent the policies of the National Science Foundation, and you should not assume endorsement by the federal government.