Institute for Transport Studies
EARTH & ENVIRONMENT

Transport + Network Science= Transport Network Science?
Richard Connors
Senior Research Fellow

Research in collaboration with
Steven O’Hare [PhD student]
David Watling [Professor]
1

2

3

4

5

Is Network Structure Important?
Some Questions…

What structure [topology] do these networks have?
[taxonomy?]
Is network structure/topology important? [When/where?]
Is it meaningful to compare different networks, and theirperformance? [Could we make it meaningful?]
Can we understand anything about transferability e.g. of atransport policy? [If policy A works in city X will it work incity Y?]
Are there common emergent properties arising fromnetwork structure? [Would this allow representation ofdetailed networks in an aggregate way?]6

In the 1960s there was an interest in considering
the properties of “idealized” networks…

7

Street Routing Topologies:[Holroyd 1966]

Compare for theoreticalcity networks…
Ignores congestion, which
would need demandlocation.
8Planar Networks
Topology & Routing Factor: [Smeed 1968]

9

Planar Networks
Theoretical Network Topologies [1850-1963]

10

Can we add anything to this?
Who is interested in such questions?

11Network Science• In the last 20 years the research area of Network
Science has exploded in terms of activity.
• Attempt to characterise the shape and structure ofnetworks - often huge networks that are difficult toobserve directly e.g. the WWW.
• Investigate how structure affects network properties(e.g. efficiency, vulnerability)12

A simple idea to start with….

13Performance“Performance” vs “Structure”

Structure/Topology

How to proceed?
What is on the x-axis?
How to arrange networks
in a meaningful order?

What is on the y-axis?

What methodology?

Metrics & measuresfrom NetworkScience?

Typically
non-planarno congestion
no demand.

Price of Anarchy?
[Some work exists]

Depends on
demand, which
is anothernetwork. Tricky!

Use real networks?

Range?

Use syntheticnetworks?

How realistic?
Generation?

15

How to proceed?
What is on the x-axis?
How to arrange networks
in a meaningful order?

What is on the y-axis?

What Methodology?

Metrics & measuresfrom NetworkScience?

Typically
non-planarno congestion
no demand.

Price of Anarchy?
[Some work exists]

Depends on
demand, which
is anothernetwork. Tricky!

Use real networks?

Range?

Use syntheticnetworks?

How realistic?
Generation?

16

Example = Meshedness [ = relative number of cycles]

Faces 2n-5

MAB

01

3
30.00
0.33

CD

23330.66
1.00
17

How to proceed?
What is on the x-axis?
How to arrange networks
in a meaningful order?

What is on the y-axis?

What Methodology?

Metrics & measuresfrom NetworkScience?

Typically
non-planarno congestion
no demand.

Price of Anarchy?
[Some work exists]

Depends on
demand, which
is anothernetwork. Tricky!

Use real networks?

Range?

Use synthetic
networks?

How realistic?
Generation?

18

Routing in Road Networks

Selfish routing, to minimise individual travel cost = User
Equilibrium (UE).
This is known to be inefficient.
Total Network Travel Cost (TTC) is minimised by System
Optimal (SO) routing

19

Routing in Road Networks

Selfish routing, to minimise individual travel cost = User
Equilibrium (UE).
This is known to be inefficient.
Total Network Travel Cost (TTC) is minimised by System
Optimal (SO) routing

20

The Price of Anarchy

and for linear link cost functions
A (not tight) upper bound is given by:

21

How to proceed?
What is on the x-axis?
How to arrange networks
in a meaningful order?

What is on the y-axis?

What Methodology?
Theoretical analysis? How?
Empirically test networks.

Metrics & measuresfrom NetworkScience?

Typically
non-planarno congestion
no demand.

Price of Anarchy?
[Some work exists]

Depends ondemand, which
is anothernetwork. Tricky!

Use real networks?

Range?

Use syntheticnetworks?

How realistic?
Generation?

22

“Performance” vs “Structure”

Performance

Real Networks?

Tokyo
Kiev
Baghdad
Seoul
Santiago
Kuala Lumpur

Structure/Topology

Illustrative example from Network Science24Price of Anarchy & Network Topology

Source: Youn et al. 2008. PhysicalReview Letters, 101.

25

Price of Anarchy & Network Topology

Regular Lattice

Erdos-Renyi (Random)

Small world

Barabasi-Albert (Scale-free)• CanonicalNetwork ScienceTopologies• Single OD pair[or 2,5,10 ODs]
Source: Youn et al. 2008.
Physical Rev Letters 101.

26

PoA In Real Networks
Price of Anarchy does vary with demand and supply structure in
real networks:

A single OD in each of 3 cities.

No explanation of what is going on.
Source: Youn et al. 2008.
Phys Rev Letters, 101.

27

Structure vs Performance28

Network Science Examples

29

What we want...a spectrum of networks

30

How to proceed?
What is on the x-axis?
How to arrange networks
in a meaningful order?

What is on the y-axis?

What Methodology?
Theoretical analysis? How?
Empirically test networks.

Metrics & measuresfrom NetworkScience?

Typically
non-planarno congestion
no demand.

Price of Anarchy?
[Some work exists]

Depends on
demand, which
is anothernetwork. Tricky!

Use real networks?

Range?

Use synthetic
networks?

How realistic?
Generation?

31

What did we do?

1. We examined performance (PoA) across a “spectrum”
of synthetic road-like networks.

2. We tried to understand the “mountain peaks”
structure of PoA as a function of demand.

32

The Generation of a Spectrum of Road Network Topologies –Node Generation

Step 1: Scatter n nodes randomly• Area = A km2• Avoid very short links, ensure minimum node
separation = dmin

The Generation of a Spectrum of Road Network Topologies –Node Generation

Delaunay Triangulation

Step 2:Meshedness:
Construct the Minimum Spanning Tree (MST)and Delaunay Triangulation (DT)Minimum Spanning Tree

Aside: MST is always asubgraph of the DT

The Generation of a Spectrum of Road Network Topologies –Generation of the Spectrum

Step 3: Construct spectrum

Start with MST and add links from the DT(add links randomly to get total links = m)

37

Spectrum of Networks

38

Link cost functions

OD demand = qr between each pair of nodes
Define demand density39• Not totally “realistic” as road networks• More plausible than most (all?) existing studies of thissort• Controllable. We can generate a spectrum as desired• = first try. Lots of ways to improve details but generalexperimental method is the key.
(admission: not quite first try!!)40

Experiments
Experiment
1. Demand
Density

Domain Size

6.25

N. Nodes6.25

4. Network
Connectivity

6.25

N. Links

Meshdness

DemandDensity

16

158

0.3

1250, 1300,…, 7900, 7950

1630, 46, …,782, 798

0.3

4350

20, 25, …, 3.2, 4, …, 30, 38, …,295, 300 47.2, 48 470, 478

0.3

4350

0, 0.03, …,0.95, 0.97

4350

100

2. Network 1.25, 1.875, …, 20, 30, …,
Size
30.625, 31.25 490, 500
3. Network
Density

NodeDensity

100

1699, 104, …,284, 289= Total of 28,000 Networks solved for both UE and SO

41

Demand Density

n = 100, A = 6.25, dmin = 0.05,=16
meshedness = 0.3
100 networks generated for each parameter settingMean V/C Ratio (UE)

Demand Density

Distribution over 100 realisations

43

PoA

Demand Density

44

Network Size [& number of nodes & links increasing]

n=500
A=31.25

n=20
A=1.25dmin = 0.05,
meshedness = 0.3=16

Mean V/C Ratio (UE)Network Size

Number of Nodes [20,...,500]

46

PoA

Network Size

Number of Nodes [20,...,500]

47

Network Connectivity [MST -> Delaunay]

M=0

M = 0.97

dmin = 0.05, A = 6.25
n = 100= 1648

Mean V/C Ratio (UE)Network Size

Meshedness [0,..., 0.97]

49

PoANetwork Size

Meshedness [0,..., 0.97]

50

Network Density [node density increasing]

= 3.2

= 48

dmin = 0.05, A = 6.25
Meshedness = 0.3

51

Mean V/C Ratio (UE)Network Size

Nodes Density [3.2,...,48.0]

52

PoA

Network Size

Nodes Density [3.2,...,48.0]

53

Conclusions/Questions• Proposed ensemble analysis as an experimental
approach (~ transport network science)• Based on synthetic networks• Needs thought on what “realistic” means• Needs work on network generation• Look at other performance measures (not just PoA).
• See systematic relationship between PoA and the quantityof demand & quantity of supply.
• Have not yet clearly extracted the (relative) importance ofthe configuration of demand & supply.
• Interesting complication that the (active) network changeswith demand.

54

How does PoA depend on demand?

55

PoA In Real Networks
Price of Anarchy does vary with demand and supply structure in
real networks:

A single OD in each of 3 cities.

No explanation of what is going on.
Source: Youn et al. 2008.
Phys Rev Letters, 101.

56

Parallel Routes Network with Linear Costs
𝑐1 = 1 + 𝑥1
DO

𝑐2 = 2 + 𝑥2

Initially, small demand, will only get flow on link 1
At some level of demand link 2 will “activate”.
57The Price of Anarchy against Demand for the ‘Two Parallel Links’
Network
DemandRegimes

UE Active
Links

SO Active
Links

The Effects of UE and SO Route Activations
Under both UE and SO, the activation of a route leads to aslower rate of increase of 𝑇𝑇𝐶.
The effect of this on 𝑃𝑜𝐴 differs depending on whether theactivation occurs under UE or SO:UE Activation ⇒ Numerator ↓ ⇒ 𝑃𝑜𝐴 ↓𝑇𝑇𝐶 𝑈𝐸
𝑃𝑜𝐴 ==𝑆𝑂𝑇𝑇𝐶𝑈𝐸𝑈𝐸𝑥𝑐𝑥𝑖 𝑖𝑖
𝑆𝑂𝑆𝑂𝑥𝑐𝑥𝑖 𝑖𝑖

SO Activation ⇒ Denominator ↓ ⇒ 𝑃𝑜𝐴 ↑59

Ten Parallel Routes Network with Linear Costs
𝑐1 = 1 + 𝑥1

10𝑞𝑂𝐷 =DO

𝑐2 = 2 + 𝑥2𝑥𝑖
𝑖=1𝑎𝑖 = 𝑖 ∀𝑖𝑏𝑖 = 1 ∀𝑖𝑐3 = 3 + 𝑥3…
𝑐10 = 10 + 𝑥1060

The Variation of the Price of Anarchy with Demand62

Route DE-activation

63

64

Sioux Falls network for a Single OD Pair𝑐𝑖 = 𝑎𝑖 + 𝑏𝑖 𝑥𝑖4

D0
⋮
0⋯

𝑞20,3
⋯

0⋮
0O65

The Variation of the Price of Anarchy with DemandExpansions and Contractions

Activations/Deactivations occur when the set of minimum
OD cost routes changes (or minimum marginal total costroutes for SO).
Call activation/transition points

andIncreasing demand can induce activation &/ordeactivation of routes. [Note off, on, off, on]

PoA is differentiable except at UE transition points

67

Special Case

If all cost functions are
And link flow solutions areThenAnd hence
68Summary• The variation of PoA with travel demand is due to activationof routes at different levels of demand under UE and SO.
• We have analysis of the types and nature of the “peaks”
and “troughs”.

69Planar Networks
Questions?

Can we define canonical/reference networks?
Can we compare real network performance with a‘reference’ network?
What are the limits of such ‘ideal’ transport systems?
properties of “1 sq km of network”
lattices and symmetric networks?
demand and supply conditions
vulnerability, resilience, redundancy
Connection to aggregation and network-free models.

70

Thank you.
Questions?

71