Network concepts

CE 367R
INTRODUCTION
A network is a mathematical object consisting of nodes connected by links.

1 4

The set of nodes is N, the set of links is A, and the network is denoted
G = (N, A)

Network concepts Introduction

Networks are used to represent many types of systems:
Transportation infrastructure
Telecommunications and computer networks
Power grids
Project structure and task dependencies
Social connections among people

Since there is a common structure among all of these systems, it is worth

studying optimization problems on abstract networks.

Network concepts Introduction

Network links and nodes can represent different things in the real world:

Park-and-ride Park-and-ride

Bus stop Bus stop

Roadway link
Bus route Bus route link
Transfer link

Physical infrastructure Network representation

Network concepts Introduction

Networks can be very large.

Tens (or even hundreds) of thousands of links and nodes are not
uncommon. We need systematic methods for working with networks.
Network concepts Introduction
NETWORK TERMINOLOGY
Nodes are typically denoted i, j, etc.

Links are typically denoted (i, j), where i is the upstream node (the tail)
and j is the downstream node (the head).

The total number of nodes in the network is denoted n, and the total
number of links is m.

The forward star of a node i is the set of links whose tail is i. This is
denoted A(i)

The reverse star of a node i is the set of links whose head is i. This is
denoted B(i).

We will assume that there are no “self-loops” (i, i), and no “parallel links,”
so (i, j) only refers to one link.

Network concepts Network terminology

In a directed network, the links are “one way” and (i, j) and (j, i) refer
to different links.

If travel in both directions is allowed, we need to create a different link in

each direction. In an undirected network, links can be traversed in either
direction, and (i, j) and (j, i) refer to the same link.

We will mostly be working with directed networks, but sometimes an undi-

rected network is a simpler way to describe the real-world system. Unless
stated otherwise, we assume the network is directed.

Network concepts Network terminology

A path is a sequence of nodes, denoted [i, j, k, · · · , z], where there is a
link connecting each consecutive pair of nodes – (i, j) is a link, (j, k) is a
link, etc.

An undirected path is a path which ignores the direction of links (either

(i, j) or (j, i) is a link, either (j, k) or (k, j) is a link, etc.)

A cycle is a path which starts and ends at the same node.

An undirected cycle is an undirected path which starts and ends at the

same node, but does not use the same link more than once.

In an undirected network, “path” and “undirected path” are the same thing,
as are “cycle” and “undirected cycle.”

Network concepts Network terminology

A network is connected if there is an undirected path between any two
nodes, and strongly connected if there is a path between any two nodes.

An acyclic network has no cycles.

A tree is a connected network with no undirected cycles.

Network concepts Network terminology

In many network problems, we introduce additional information for nodes
and links. (Not all problems use all of these.)

A link (i, j) may have a flow xij , a cost cij per unit of flow, and a capacity
uij . (Rarely, a link may have a lower bound `ij on its flow.)

A node i may have a supply or demand bi . (Positive for supply, negative

for demand.)

A node with supply is a source, a node with demand is a sink.

Network concepts Network terminology

SOME NETWORK
OPTIMIZATION
PROBLEMS
Shortest Path Problem

Identify a path connecting a given origin and destination, where the total
cost of the links in the path is minimized.

Network concepts Some network optimization problems

Applications

Vehicle routing
Critical path analysis in project management
Six degrees of Kevin Bacon

Network concepts Some network optimization problems

Maximum Flow Problem

What is the greatest amount of flow that can be shipped between a given
source and sink without exceeding link capacities?

Network concepts Some network optimization problems

Applications

Determining the capacity of a network

Identifying critical links in a network
Rounding a matrix

Network concepts Some network optimization problems

Minimum Cost Flow Problem

Respecting capacities, find link flows which balance supply and demand
among sources and sinks, with minimum total cost.

Network concepts Some network optimization problems

Applications

Logistics and shipping

Earthwork in roadway construction
Passenger selection in ridesharing

Network concepts Some network optimization problems

Minimum Spanning Tree

In an undirected network, identify a subset of links which form a connected

network, where the total cost of the links in the tree is minimized.
Network concepts Some network optimization problems
Applications

Building roads in rural areas

Providing utilities and other infrastructure
Espionage networks, passing messages between spies

Network concepts Some network optimization problems

Traveling Salesperson Problem

Find a path which passes through all nodes and returns to the origin with
minimum total cost.

Network concepts Some network optimization problems

A FIRST ALGORITHM
Basic search

Given a network G = (N, A) and an origin node s, find all of the nodes in
N which can be reached from s by a path. Furthermore, for each node
which is reachable, identify a path from s to that node.

(This can help determine if the network is strongly connected — every

node should be reachable from every other.)

How might we solve this problem in a systematic way?

Network concepts A first algorithm

Search algorithm

Each node will either be marked or unmarked. Marked nodes are reachable
from s, unmarked nodes may or may not be (we do not know).

Each marked node has a predecessor pred, indicating the last node on a
path from the origin to that node. This turns out to be enough to
represent the requested paths.

(The origin takes a special predecessor, pred(s) = −1.)

We also maintain a scan eligible list SEL, a set of nodes that we still need
to check before we are done.

An algorithm is a sequence of well-defined steps to follow. Algorithms are

best learned by following an example simultaneously.

Network concepts A first algorithm

Algorithm

1 Unmark all nodes in N.

2 Mark the origin s and set pred(s) = −1.
3 Set SEL = {s}.
4 Choose a node i from SEL and remove it.
5 For each link (i, j) ∈ A(i) where j is unmarked, do the following steps:

1 Mark node j
2 Set pred(j) = i
3 Add j to SEL.
6 If SEL is empty, then stop. Otherwise return to step 4.

Upon termination, all marked nodes are reachable from s and all unmarked
nodes are unreachable.

Network concepts A first algorithm

How should we choose which node to remove from SEL if there are
multiple?

The algorithm is correct no matter how we make this choice. Two

common choices are:
Choose the oldest node in SEL. This results in breadth-first search,
and the paths represented by pred connect each node to the origin
with the least number of links.
Choose the newest node in SEL. This is depth-first search. (Go as
far as we can, then backtrack. You can solve mazes this way.)

Network concepts A first algorithm

STORING NETWORKS IN
COMPUTERS
So far we have been “representing” networks by drawing a picture.

1 4

This is good for visualization, but not very convenient when working with
large networks, if you want to communicate them to others, or for
computers.

Network concepts Storing networks in computers

A network representation is a way to store a network using mathematical
structures like a vectors or matrices. There are several ways to do this.

 
−1 −1 0 0 0
1
 0 −1 −1 0 

0 1 1 0 −1
0 0 0 1 1

The node-link incidence matrix has a row for each node, and a column
for each link. In each column, there is a −1 in the row for the tail, a +1 in
the row for the head, and 0 everywhere else.

Network concepts Storing networks in computers

The node-link incidence matrix can store the network topology. How
would you store information such as link flows, link costs, or node supplies
and demands?

c = [3,2,1,5,4]

b = [1,0,-2,1]

Answer: Use vectors with m components to store link data, and vectors
with n components to store node data.

Network concepts Storing networks in computers

Another way to store the network topology is the node-node adjacency
matrix.

 
0 1 1 0
0 0 1 1
 
0 0 0 1
0 0 0 0

This matrix has a row for each node, and a column for each node. The
entry in row i and column j is 1 if (i, j) is a link, and zero otherwise.

Network concepts Storing networks in computers

Which representation is “better”? If there are n nodes and m links, how
many entries do we have to store for the node-link and node-node
adjacency matrices?

The node-node matrix requires n2 entries, while the node-link matrix

requires nm.

How does m compare to n? What is a typical ratio of m to n? Can we put

upper and lower bounds on this ratio?

Network concepts Storing networks in computers

If the network is connected, m ≥ n − 1. (Why?)

No matter what, m ≤ n(n − 1). (Why?)

So, it seems that usually m ≥ n, suggesting that the node-node matrix uses
less memory to store the same information.

Network concepts Storing networks in computers

ASYMPTOTIC NOTATION
In optimization and other large-scale systems, it is helpful to have a simple
way to roughly compare how much space is required to represent the
system.

Last slide, we said m ≤ n(n − 1) = n2 − n. When n is large, the n2

term dominates the equation.
When n is large, n3 + 3n2 − 400n + 1000 is close to n3
When n is large, 2n + n2 is close to 2n .

Network concepts Asymptotic Notation

Big-O notation

Formally, we say that a function f (n) is O(g (n)) if there is a constant C

such that f (n) ≤ Cg (n) for all values of n.

n2 − n is O(n2 ) because n2 − n ≤ 1n2 for all n (C = 1)

n3 + 3n2 − 400n + 1000 is O(n3 ). What value of C works?
2n + n2 is O(2n ). What value of C works?

A useful fact: if limn→∞ f (n)/g (n) < ∞, then f (n) is O(g (n)). This is a
faster way to do these examples.

Network concepts Asymptotic Notation

Can we say that 2n + n100 is O(2n )?

Can we say that n2 − n is O(n3 )?

The lessons: the approximation may only work when n is very large; and it
may not be the tightest bound possible.

Network concepts Asymptotic Notation

Applying this concept to network representations, we see that the
node-node matrix requires O(n2 ) space, and the node-link matrix requires
O(nm) space. Furthermore m is O(n2 ), so in the end the node-link matrix
can potentially use O(n3 ) entries to store the network structure.

We say that the space required by the node-node matrix grows

quadratically with n, but the space required by the node-link matrix can
grow as the cube of n.

Also note that we are talking about the worst case! In many networks m
grows at roughly the same rate as n, in which case the node-link matrix
grows as n2 .

Network concepts Asymptotic Notation

The big-O notation avoids a lot of complications:
What if my computer uses 2 bytes of information to store each
number? (The node-node matrix still requires O(n2 ) space, just with
a different constant.)
What if I am also storing the flows and costs of each node?
(n(n − 1) + 2n is still O(n2 )).

Network concepts Asymptotic Notation

The big-O notation can also be used to reflect the number of steps needed
to perform some procedure.

How could you find a link’s forward star using the node-node adjacency
matrix? How many steps are required?

What about using the node-link adjacency matrix?

Network concepts Asymptotic Notation

BACK TO NETWORK
REPRESENTATIONS...
Is there a way to store a network structure with O(m) entries? In
transportation networks m is usually much smaller than the worst-case of
n2 .

The forward star representation orders the links based on their tail
node. We then have vectors tail and head, where link a connects
tail(a) to head(a).

How would you find a link’s forward star using this representation? How
many steps are required in the worst case?

What about the reverse star?

Network concepts Back to network representations...

We can add another vector called point which makes it even easier to
find the forward star: point(i) is the lowest number a for which tail(a)
= i.

It would be nice to say that the forward star of i is always the links
between point(i) and point(i + 1) - 1, inclusive.

We can do that with the following clarifications and “corner case”

definitions:
The point vector has n + 1 components.
We automatically set point(n+1) = m + 1.
If node i has no outgoing links, point(i) = point(i+1).

Network concepts Back to network representations...

There is also a reverse star representation, which is similar. In this
representation, it is easy to find the reverse star, but a bit more work to
find the forward star.

Network concepts Back to network representations...

For next time...
The Königsberg bridge problem... cross each bridge once and return home.

Represent this as a network problem. Can you solve this puzzle? Can you
think of a systematic way to solve this kind of puzzle?
Network concepts Back to network representations...