The ARPANET was a computer network that was the precursor to the Internet. This diagram shows the nodes that made up the APRANET in 1977. In a computer network, machines called network routers store are responsible for sending data from its source to its destination. The routers store a representation of their connections and make decisions on which direction to send the data. They will often have multiple paths to choose from so that in the event that a particular path fails it can re-route the data via another path.

2 - Six Degrees, Tables, and Trees

Summary

This lesson applies networks to social connections (Six Degrees of Kevin Bacon), represents network data in a tabular form, and distinguishes between the minimal representation of a tree and the fuller network representation that contains cycles.

Context

Sequence of Lessons

In Lesson One, the students were introduced to network representation and basic terminology through a Treasure Hunt game. This lesson continues their study of networks as summarised above, covering tabular representations of networks, trees, and cycles.

In Lesson Three, students will extend their study building networks from maps and examining directed and weighted edges.

Prior Learning

The obvious prior learning is the introduction to network diagrams and terminology from Lesson One. In addition to this, students are expected to be familiar with the use of tables from Data Analysis (MS-S1) in Stage 6 as well as use of tables in earlier stages.

Future Learning

Understanding trees as minimal representations of trees will be vital for Lessons Four and Five in which strudents study spanning trees, minimum spanning trees, and shortest paths.

Goals

Represent network data in a table and then translate that data into a network diagram

Investigate the differences between simple trees and more complex cyclical networks., especially highly connected networks

Apply network techniques to common connectivity problems (connection between actors)

Syllabus Content

Identify and use network terminology: tree, cycle, cyclic network, acyclic network (not included in syllabus vocabulary list)
Solve problems involving network diagrams
- Draw a network diagram to represent information given in a table

Students develop their awareness of the applicability of networks throughout their lives, for example social media networks (from Subtopic Focus)

Working Mathematically

Build fluency and understanding about trees, cyclical networks, and highly connected networks

Apply network techniques to common connectivity problems

Possible Misconceptions

(We could not find clear misconceptions in the literature so the following our from our impressions.)

Students might not realise that network data can be contained in tables
Students might consider simple trees as ideal representations of networks and not appreciate the benefits of more complex, cyclical networks, including highly connectedd networks

Lesson - Actors, Trees, and Cycles

Time
(min)

0 - 5

Teacher

While handing out lesson worksheet ( Lesson 2 Worksheet )... or directing students to the on-line worksheet [ICT], ask students whether they have had that experience of meeting someone and then realising that you surprising now the same people are have some other things in common.

Mention that that is a characteristic of highly connected networks in which some or many individuals (vertices) have many connections.

Turn the class's attention to actors and how highly connected their networks must be. Ask about the favourite actors of the students.

Students

Students listen and participate in the conversation.

Students review the worksheet... Lesson 2 Worksheet

5 - 10

Break the students into groups of 4 (or thereabouts).

Walk through the first part of the worksheet showing students:

How to enter the first actor on the first row and column
How to mark the diagonal cell as not applicable e.g. "---" or something like that... and why we do that
How to look up the connection between the first and second actors, how to enter the names of all the actors that come up, and how to enter the names of the connecting movies.

Students choose a first/favourite actor jointly.

Then each member of the group chooses another actor.

Students use the Oracle of Bacon ( http://oracleofbacon.org/ ) [ICT] to determine how the actors they have selected are linked.

10 - 25

Provide assistance as required, checking on the progress of each group.

Students continue adding all their actors to their table, resulting in a table similar to the one below.

25 - 35

Instruct the students to build a network diagram from data in their table, reminding the students to name the vertices for each actor and label the links with the connecting movie.

If required, demonstrate by drawing up the connection between the first two actors.

Each group creates a network diagram from the connectivity data in their table, resulting in a tree similar to the one below.

35 - 45

Ask groups to pass around the diagrams that they have created.

[AFL] By examining the diagrams that the groups have created, ensure that the students remember the network diagram basics that they learnt in Lesson One. Also verbally quiz them on terms like VERTEX, VERTICES, EDGE, and PATH.

Introduce the term TREE [LIT] pointing out that a tree is the simplest form of network and has no CYCLEs [LIT].

Now ask each group to add the connection of any two of the other actors (actor 2 to actor N) to their table and diagram.

Groups compare their diagrams with that of other groups.

Then each group extends their table and network diagram to include a connection between any of the other actors (actor 2 to actor N), resulting in a diagram like the one below [WM - Understanding].

45 - 55

Again, emphasise the difference between CYCLIC NETWORKS [LIT] like the updated diagrams the groups just made and ACYCLIC NETWORKS [LIT] like the initial tree diagrams they made.

Discuss how the six degrees of Kevin Bacon is an example of a highly connected network, showing through the table below that six degrees does in fact capture 99.98% of actors. If time allows, get the students to calculate the percentage of actors covered by 5 degrees and 4 degress [NUM].

Lastly, mention how the neurons in the human brain form a highly connected and complex (cyclical) network and that it's this connectivity that produces the magic of thought and memory! Ask the students if they can think of other highly connected, complex networks.

Students listen to the points about cyclic and acyclic networks and highly connected networks.

If time permits, students calculate the percentage of actors with a bacon number of 5 or less, and the percentage of actors with a bacon number of 4 or less.

Students suggest other exxamples of highly connected and complex (cyclical) networks [WM - Understanding].

Table of Bacon Numbers from https://blogs.ams.org/mathgradblog/2013/11/22/degrees-kevin-bacon

Kevin Bacon

Neuron from https://news.harvard.edu/gazette/story/2020/12/how-neurons-form-long-term-memories/

55 - 60

Mention that there are several advantages and disadvantages to simple trees versus more complex cyclic networks, both in building networks and also in how networks can hold or represent information. Describe the homework the students are to do and how this will help them investigate these pros and cons.

Students review the homework instructions (see Homework section below)

Extension - Number of Trees

For students wanting an additional challenging, either in the class or as homework, ask them to examine the number of possible trees connecting N vertices as described below.

(Perform the first 4 steps before reading steps 5 and 6!)

Draw two vertices and then draw the number of trees that can connect these vertices (1)
Draw three vertices and then draw the number of trees that can connect these vertices (3)
Draw four vertices and then draw the number of trees that can connect these vertices (16)
From the pattern observed, propose a rule that would prodict the number of possible trees that could connect N vertices [WM - Reasoning]
Research Cayley's Formula
Apply Cayley's formula, determining the number of possible trees that could connect five vertices (125)

Homework - Redundancy and Organised Complexity

For homework, have the students read the following short article [LIT] from Khan Academy on Redundancy and Fault Tolerance.

https://www.khanacademy.org/computing/computers-and-internet/xcae6f4a7ff015e7d:the-internet/xcae6f4a7ff015e7d:routing-with-redundancy/a/redundancy-fault-tolerance

Then have the students watch the following thought provoking you tube video from RSA Animate about trees and the representation of complexity.

https://youtu.be/nJmGrNdJ5Gw

Lastly, have the students write brief responses to the following questions:

What are the pros and cons of simple tree networks, both when building systems and for holding/representing information?
What are the pros and cons of more complex/cyclical networks, both when building systems and for holding/representing information?

Early ARPANET map from Khan Academy article

The interconnectedness of the Atlantic Cod from from RSA Animate video

Differentiation

In order to provide further assistance to students in this lesson, the following differentiation is being included:

Having students work in groups so they can assist one another on the tasks
Having on hand pre-made actor tables like the one shown above. If any of the groups is struggling with filling in the table or determining the connection between one actor and another, they can skip the table building step and instead use a pre-made table, basing their network diagrams on this table.

Also, the following differentiation has been added for students who want additional challenge: