Lesson 3 ~40 min Introduction to Networks · Path +90 XP

Networks in the Real World

The mathematics of networks is the same everywhere it is used. What changes from one application to the next is the decision about what a vertex represents and what an edge represents, and that decision is made by you, not by the situation.

Today's hook: Social media, electricity distribution, the routes a delivery van takes, the pages of the internet and the spread of an infection are all studied with the same mathematics. That is either a remarkable coincidence or a sign that the mathematics is about something quite general.

0/5QUESTS

Think First

warm-up

Take one situation: the students at your school. Give two genuinely different ways of turning it into a network, by choosing different meanings for the edges. What question would each one help you answer?

Record your answer in your workbook.

The Big Idea

+5 XP to read

Building a network model is two decisions. What is a vertex, and what is an edge? Make them differently and you get a different network from the same situation, which answers a different question.

$$\text{situation} + \text{two decisions} = \text{model}$$

Different applications produce networks with recognisably different shapes. Social networks are dense and full of short loops, because your friends tend to know each other. Supply chains spread outwards with few loops, because goods flow one way.

$\text{vertices} = ?, \quad \text{edges} = ?$

State both decisions

"Vertices are airports, edges are direct flights." A model is not described until both halves are given.

Degree usually means something

Friends, connections, routes. Whatever the edges are, the degree of a vertex counts them.

Know what the model dropped

A plain network carries no strength, cost or timing. If a question needs those, the model needs extending.

What You'll Master

objectives

Know

that networks model social connections, supply chains, communication infrastructure, transport and many other systems
that building a model requires choosing what a vertex represents and what an edge represents
that a plain network records only connection, and that cost, capacity, strength and direction are extra information

Understand

why the same situation can yield several different and equally valid network models
why the shape of a network reflects the kind of system it models
why a vertex of degree one is a point of vulnerability in an infrastructure network

Can Do

build a network model of a described situation, stating both modelling decisions
interpret the degree of a vertex in the context of the system being modelled
state what a given network model cannot tell you about the situation

Words You Need

vocabulary

ModelA mathematical description of a real situation, keeping some features and discarding others.

Social networkA network whose vertices are people and whose edges are relationships between them.

Supply chainA network whose vertices are producers, storage sites and sellers, and whose edges are the movements of goods between them.

InfrastructureThe physical systems a society runs on, such as power, water and communications, all of which are naturally networks.

Weighted edgeAn edge carrying an extra number, such as a distance, cost or time. An extension beyond a plain network.

The Two Decisions

+5 XP to read

Every network model starts from the same pair of questions. What are the objects? What counts as a connection between two of them?

Take a school. If the vertices are students and the edges are friendships, the network answers questions about who influences whom. If the vertices are students and the edges join two students who share a class, it answers questions about who could pass on an illness. If the vertices are classes and the edges join two classes with a student in common, it answers questions about timetabling.

Same school, three different networks, three different sets of answers. None of them is the right one in the abstract; each is right for a particular question.

So a model is not fully described until both decisions are stated. "A network of the school" says almost nothing. "Vertices are classes, edges join classes sharing at least one student" says everything.

Social Networks

+5 XP to read

Vertices are people; edges are relationships. The relationship has to be chosen carefully, because different relationships behave differently.

Friendship is symmetric: if you are my friend I am yours, so one edge serves both directions. Following is not symmetric, since you can follow someone who does not follow you. Modelling following properly needs edges with arrows, called directed edges, which are beyond this area but worth knowing exist.

The degree of a vertex is the number of friends that person has. High-degree vertices are influential, because a message reaches many people from them in one step.

Social networks have a characteristic shape: lots of triangles. If Ana knows Ben and Ben knows Cara, there is a good chance Ana knows Cara, so the network is full of short loops. That is not true of every kind of network, and it is one of the ways a social network can be recognised from its structure alone.

Supply Chains and Transport

+5 XP to read

Vertices are places: factories, warehouses, ports, shops. Edges are the routes goods travel between them.

These networks have the opposite shape to social ones. Goods flow outwards from few sources to many destinations, so the network branches and rarely loops back.

Real supply-chain questions almost always need more than a plain network. How far is it? How long does it take? How much can this route carry? Each of those attaches a number to an edge, giving a weighted network.

Weights are outside this focus area, but the reason they are needed is worth seeing now. A plain network answers "is there a route?" and "how many steps?", and nothing more. Every other question requires putting some of the discarded information back.

Transport networks work the same way, with stations as vertices and track sections as edges, which is why the train map in Lesson 1 was a network all along.

Communication Infrastructure

+5 XP to read

Vertices are exchanges, data centres or transmission towers; edges are the cables or links between them.

The design question here is not usually "is everything connected?" but "does the system survive damage?", and the network answers it directly.

A vertex of degree $1$ is connected to the rest of the system by a single edge. Cut that edge and the vertex is isolated, so a degree of $1$ marks a single point of failure. Engineers deliberately add edges to raise the degree, which is called building in redundancy, and it is why undersea cable maps show several routes between the same pair of continents.

The same reasoning applies to a vertex whose removal disconnects the network, even if its degree is high. A single exchange that every route passes through is a vulnerability of the whole system rather than of one site, and spotting it is a network question, not an engineering one.

What the Model Leaves Out

+5 XP to read

Every model discards information, and being clear about what was discarded is part of using it honestly.

A plain network does not record strength: a close friendship and a passing acquaintance are the same edge. It does not record direction: an edge does not say which way anything travels. It does not record capacity or cost: a country road and a six-lane motorway are the same edge. It does not record time: two people who were friends in different decades appear connected.

None of that makes the model wrong. It makes it a model of connection specifically, and it will answer questions about connection correctly and questions about anything else not at all.

The failure to avoid is drawing a conclusion the model cannot support. "These two are connected in the network, so information reaches one from the other quickly" is exactly such a conclusion, because the network says nothing about speed.

Watch Me Solve It · 3 examples

Watch Me Solve It · Modelling one situation two ways

+15 XP per step

PROBLEM

A school runs six subjects. Some students take more than one subject. Give two different network models of this situation, stating both modelling decisions in each, and name a question that each model can answer.

1

The first model

Vertices are the six subjects. An edge joins two subjects when at least one student takes both.
2

What it answers

Timetabling. Two subjects joined by an edge cannot be scheduled at the same time, because at least one student would have to be in two places at once.
3

The second model

Vertices are the students. An edge joins two students when they share at least one subject.
4

What it answers

Contact tracing during an illness outbreak, since an edge marks a pair who spend time in the same room. It also answers questions about which students never encounter each other.
5

Compare

The two models come from the same facts and share no vertices at all. Neither is more correct; the question decides which is useful.

AnswerSubjects joined by shared students for timetabling; students joined by shared subjects for contact tracing

Watch Me Solve It · Reading degree in context

+15 XP per step

PROBLEM

In a social network of $8$ people with edges for friendship, one vertex has degree $6$ and another has degree $1$. Interpret both, and say what each implies about how a message spreads.

1

Interpret the high degree

A degree of $6$ means that person is friends with six of the other seven, so almost everybody. A message starting there reaches six people in one step.
2

Interpret the low degree

A degree of $1$ means that person has exactly one friend in the group. Every message reaching them must pass through that single friend.
3

Draw the consequence for spread

Removing the high-degree person slows the spread everywhere. Removing the single friend of the low-degree person cuts them off entirely, even though only one edge was lost.
4

Note the limit

The network says nothing about how likely any friend is to pass a message on, so it can identify who is well placed to spread it but not how fast anything actually travels.

AnswerDegree $6$ marks a hub; degree $1$ marks someone dependent on a single connection

Watch Me Solve It · Spotting a vulnerability

+15 XP per step

PROBLEM

A communications network has vertices $A$ to $F$ with edges $AB$, $BC$, $BD$, $DE$, $DF$ and $EF$. Identify which single edge, if cut, would isolate a vertex, and which single vertex, if it failed, would split the network into two disconnected parts.

1

Find the degrees

$A: 1, \quad B: 3, \quad C: 1, \quad D: 3, \quad E: 2, \quad F: 2$

Count how many edges meet at each vertex.
2

Identify the fragile edges

Vertices $A$ and $C$ have degree $1$, so cutting $AB$ isolates $A$ and cutting $BC$ isolates $C$. Either edge alone is a single point of failure.
3

Identify the fragile vertex

If $B$ fails, the edges $AB$, $BC$ and $BD$ go with it, leaving $A$ and $C$ isolated and $D$, $E$, $F$ connected only to each other. The network splits.
4

Suggest the fix

Adding an edge such as $AC$, or $CD$, gives $A$ and $C$ a second route and removes the dependence on $B$. That is redundancy, and it costs one extra cable.

AnswerCutting $AB$ or $BC$ isolates a vertex; the failure of $B$ splits the network

Brain Trainer · 5 problems

Brain Trainer · Vertices, edges, and what they mean

5 problems

Five items about network models. State both modelling decisions wherever a model is asked for.

1 In an airline route network, what are the vertices and edges?

The objects are places, the connections are services between them.Airports; direct flights
2 In a friendship network, what does the degree of a vertex represent?

Degree counts the edges at a vertex, and the edges are friendships.That person's number of friends
3 Why is a vertex of degree $1$ a concern in an infrastructure network?

It has only one edge connecting it to everything else.One cut isolates it
4 A plain network models a road system. Can it tell you the shortest driving distance between two towns?

Edges have no length in a plain network.No, not without weights
5 Why are social networks full of triangles?

Two people with a friend in common are likely to know each other.Friends of friends are often friends

Complete in your workbook.

Multiple Choice · 5 questions

MC1

Describing a model

+10 XP

Which of these describes a network model completely?

MC2

Same situation, different model

+10 XP

A university is modelled twice: once with vertices as courses and edges joining courses that share a student, and once with vertices as students and edges joining students who share a course. These two models:

MC3

Reading a degree

+10 XP

In a supply network where vertices are warehouses and edges are delivery routes, a vertex has degree $5$. This means:

MC4

What the model cannot do

+10 XP

A plain network models friendships in a class. Which question can it NOT answer?

MC5

Shape and application

+10 XP

A network is found to contain many triangles, with most pairs of a vertex's neighbours joined to each other. This suggests it models:

Short Answer · 3 questions

Build and justify a model

+15 XP

SHORT ANSWER

A council wants to know whether its bus network lets residents reach the hospital from every suburb, possibly with changes. Describe a suitable network model by stating what the vertices and edges represent, explain why your choice suits the question, and state one thing your model cannot tell the council.

Write your working in your book.

Two models, one situation

+15 XP

SHORT ANSWER

Eight friends play in a five-a-side competition, spread across three teams. Give two genuinely different network models of this situation, stating both decisions in each, and give a question that each model answers and the other does not.

Write your working in your book.

Find the weak points

+15 XP

SHORT ANSWER

A regional data network has vertices $P$, $Q$, $R$, $S$, $T$, $U$ with edges $PQ$, $QR$, $QS$, $RS$, $ST$, $TU$. Find the degree of every vertex, identify every single point of failure, and recommend one edge to add, justifying your choice.

Write your working in your book.

Stretch Challenge · Six degrees of separation

+25 XP

CHALLENGE

A well-known claim is that any two people on Earth are connected by a chain of at most six acquaintances. Suppose everyone knows exactly $100$ people, and that no two of your acquaintances know each other. Work out how many people you could reach in six steps, compare that with the world population, and then explain why the assumption you were given is badly wrong and what it does to the argument.

Under the stated assumptions, the number of new people reached at each step multiplies by $100$.

Step $1$: $100$ people. Step $2$: $100^2 = 10\,000$. Step $3$: $10^6$. Step $4$: $10^8$. Step $5$: $10^{10}$. Step $6$: $10^{12}$, a trillion.

The world population is around $8 \times 10^9$, which is reached somewhere between step $4$ and step $5$. So the calculation suggests that six steps is not merely enough but generous.

The assumption is badly wrong. It says none of your acquaintances know each other, which is false for almost everyone. Your friends overlap heavily: they share schools, workplaces, families and neighbourhoods, and Lesson 2 has already noted that social networks are full of triangles for exactly this reason.

Overlap destroys the multiplication. If half of the $100$ people your friend knows are people you already know, the second step adds $50$ new people per friend rather than $100$, and the effect compounds at every subsequent step. The reach still grows quickly, but from a much smaller base, and the calculation above becomes a wild overestimate.

What rescues the claim is a small number of unusual edges. Most of your acquaintances are local, but a few are not: someone who moved from another country, or works internationally, or met a stranger while travelling. Those long-range edges act as shortcuts between otherwise distant regions of the network, and a surprisingly small number of them is enough to bring the whole network back within a handful of steps.

So the six-degrees claim survives, but not for the reason the naive calculation gives. It survives because of the rare long connections rather than the common local ones, which is the opposite of what the multiplication suggests.

The wider lesson is about modelling rather than about friendship. An assumption that makes a calculation easy can also make it meaningless, and the honest response is to state the assumption, do the calculation, and then say plainly how far the assumption can be trusted.

Quick Review

recap

A model is two decisions

What is a vertex, and what is an edge? State both. Different choices from the same situation give different networks answering different questions.

Degree carries the application's meaning

Number of friends, number of direct routes, number of cables. Whatever the edges represent, the degree of a vertex counts them.

Shape reflects the system

Social networks are dense in triangles because friends of friends are often friends. Supply chains branch outwards and rarely loop back.

Know what was discarded

A plain network records connection only. Strength, direction, cost, capacity and timing are all absent, and conclusions needing them are not supported.

Your Badges

0 of 6

First Steps

3-Day Streak

3 in a Row

Lesson Ace

Stretch Seeker

Daily Warrior

Mark lesson as complete

Tick when you've finished Learn, Practice and the Stretch. Earns +90 XP and +25 coins.

Introduction to Networks (Path) index · Maths subject page