SWEN90004
Modelling Complex Software Systems
Lecture Cx.09 Networks I: Theory and Models
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
1 / 36
Objectives
To understand how the structure of complex systems can be described in terms of the pattern of interaction between their components, and represented as a network.
To describe the structure of a network in terms of it’s basic properties.
To use algorithms to generate particular classes of networks (small world and scale-free)
To recognise how the structural characteristics of a system can influence its functional characteristics.
2 / 36
Outline
Introduction to networks
Network properties
Types of networks
3 / 36
A brief history of network research
Leonard Euler and the Seven Bridges of Konigsberg (1735)
4 / 36
A brief history of network research
Leonard Euler and the Seven Bridges of Konigsberg (1735)
5 / 36
Milgram’s “small world” experiments (1960s)
6 / 36
Milgram’s “small world” experiments (1960s)
Social psychologist Stanley Milgram conducted a series of experiments in the 1960s to measure the degree to which modern populations were interconnected.
His experimental procedure was:
1. Individuals in various midwest cities were chosen at random and sent a package with basic information about a target person in Boston.
2. If they knew the target person, they were to send the package directly to them.
3. If (as was more likely) they didn’t know the target person, they were to send the package to someone who they did know, who they thought was more likely to know the target person.
4. When (and if!) the parcel reached the target person, the researchers could count how many times it had been forwarded between origin and destination.
The average number path lengths of the chains of forwarding was between five and six, a phenomenon that has since been popularly referred to as six degrees of separation.
7 / 36
A brief history of network research
Operations Research (1900s—)
logistics, shortest paths, optimisation Social networks (1960s—)
shift in sociology from individuals to groups to relationships
development of abstract models and patterns: cliques, clusters,
power brokers, . . .
Modern network science (1990s—)
more abstract models: seeking insights into systems on the basis of shared structural properties
application in a wide range of domains
8 / 36
Example networks—biology
http://www.nature.com/nbt/journal/v30/n10/full/nbt.2356.html
9 / 36
Example networks—biology
http://www.biomedcentral.com/1752-0509/2/101/
10 / 36
Example networks—sociology
http://www.fmsasg.com/SocialNetworkAnalysis/
11 / 36
Example networks—epidemiology
http://www.freerepublic.com/focus/news/1327834/posts
12 / 36
Example networks—computing
http://en.wikipedia.org/wiki/Opte_Project
13 / 36
Why study networks?
More and more data on patterns of interaction is becoming available.
Network science offers tools to help make sense of this data.
We can learn something about the functional properties of
these systems by studying their structural properties.
Insights developed in one domain may generalise to other
domains.
Networks are everywhere: gene networks, protein networks, many types of social networks (influence, encounter, friendship, etc), food webs, transport networks (roads, bus routes, flight paths), electricity distribution networks, telecommunication networks, supply and distribution networks, company networks, political support networks, . . .
14 / 36
Outline
Introduction to networks
Network properties
Types of networks
15 / 36
What is a network?
A network consists of:
A set of nodes or vertices
A set of edges or links
Data about nodes and edges
Formally, a graph G = (N,E) is an ordered pair of finite sets. Elements of N are called nodes or vertices. Elements of E ⊂ N × N are called edges or links.
16 / 36
Network properties
The structural properties of networks often have functional consequences. Structural properties are often used to compare and contrast network models of different systems.
Networks may be unipartite (all nodes of the same type) or bipartite (nodes of two different types), or k-partite (nodes of k different types).
Edges may be directed or undirected.
bipartite networks: directors and the companies whose boards
they site on; actors and the movies they have appeared in, . . .
directed networks: web pages and the (directed) links between them; food webs with directed edges indicating predation, . . .
17 / 36
Network properties
To start, we will consider properties of networks that are unipartite, with undirected edges—these are the most studied, although bipartite networks and directed networks are also very common.
Other common assumptions are that there are:
no parallel edges (ie, there can only be one edge between two
nodes)
no self-connections (ie, there are no edges between a vertex and
itself )
18 / 36
Network properties—density
The density D of a network is the ratio of the number of edges in the network to the number of possible edges.
FigureN = 20;E = 30 FigureN = 20;E = 100
A network with N nodes and E edges could have up to N(N−1)
possible edges, therefore:
D= 2E N(N − 1)
2
19 / 36
Network properties—degree
The degree ki of node i is the number of edges between node i and other nodes in the network. Nodes with high degree are often considered to be more “important”.
The average degree < k > of a network, where < k >= 2E/N.
The degree distribution P(k) of a network is the probability distribu- tion of degrees over all nodes in the network; P(k) = Nk/N where Nk is the number of nodes of degree k.
The degree distributions of many real world networks are strongly skewed.
20 / 36
Network properties—degree
FigureYeast protein interaction network FigureWestern US power grid
http://konect.uni-koblenz.de/networks/
21 / 36
Network properties—distance
The distance dij between nodes i and j is the length of the shortest path between those two nodes.
FigureA “path” network FigureA “star” network
The characteristic path length L is the average distance (ie, shortest path) between all pairs of nodes in the network:
L = 1 dij N(N − 1) i̸=j
The diameter of a network is the longest shortest path between
any two nodes; ie, it is the largest number of nodes that must be traversed to move from one node to another without backtracking22 / 36
Network properties—clustering
The clustering coefficient C is a measure of “cliquishness” in a network; ie, the extent to which, if Alice is friends with Bob and Carol, Bob and Carol are likely to be friends with each other.
Another way of thinking about the clustering coefficient of a node i is in terms of the proportion of possible triangles containing i that exist:
23 / 36
Network properties—clustering
The clustering coefficient is defined as: C= Tc
Tc +To
where:
Tc is the number of closed triplets—sets of three nodes each of
which is connected to the other two
To is the number of open triplets—sets of three nodes in which
exactly one node links the other two
Formally, the clustering coefficient Ci of node i is defined as the ratio between the number of edges Ei that actually do exist between these ki nodes and the total number ki (ki − 1)/2 possible:
Ci= 2Ei ki(ki −1)
The clustering coefficient of a network is often calculated as the average clustering coefficient over all the nodes in the network
24 / 36
Network properties—centrality and assortativity
Centrality is another approach to measuring which are the most important nodes or edges in a network. There are many different definitions including:
the number of shortest paths that pass through a particular node or edge
the extent to which a node is connected to other “important” nodes
Assortativity measures the extent to which similar nodes tend to be connected to each other. With respect to degree, a highly assortative network is one in which the high degree nodes are all connected to each other, while a dissasortative network is one in which high degree nodes tend to be connected to low degree nodes.
25 / 36
Outline
Introduction to networks
Network properties
Types of networks
26 / 36
Regular lattices
Every node in a regular lattice has exactly m edges; ie, the degree distribution is given by:
1 if k = m pk = 0 otherwise
FigureA regular 2D lattice
FigureA circular lattice
(Can have) high clustering coefficient, long characteristic path length
27 / 36
Random networks
Specifically, Erdos-Renyi random graphs, which starts with a set of N nodes and then adds edges between pairs of nodes at random (eg, sampling each edge with a given probability).
Low clustering coefficient, short characteristic path length
28 / 36
Small world networks
1. Start with a regular lattice of even degree m 2. Randomly rewire a proportion p of the edges 3. (alternatively, add new edges at random)
29 / 36
Small world networks
Consider the rewiring option:
when p = 0, the network is a regular lattice
when p = 1, the network is completely random
As p approaches 1:
clustering coefficient: C ≈ 3(m/2−1) (1 − p)3
2(m−1)
characteristic path length approaches logN
logm
For some range of value of p between 0 and 1, we observe:
High clustering coefficient and low characteristic path length
30 / 36
Small world networks
31 / 36
Scale free networks
A scale free network is one whose degree distribution follows a power law distribution; ie, pk ∼ k−γ, where γ is usually between 2 and 3.
One straightforward way of constructing a scale free network is via a process of growth and preferential attachment:
1. Start with a small number of nodes, connected at random.
2. Add a new node to the network.
3. Connect the new node to m existing nodes with a probability proportional to the current degree of those nodes.
Repeat steps 2 and 3. As the network grows, positive feedback (“the rich get richer”) will lead to a small number of nodes gaining a disproportionate number of edges.
(Relatively) high clustering coefficient and short average path length
32 / 36
Scale free networks
33 / 36
Scale free networks
34 / 36
Scale free networks—error and attack tolerance
An interesting property of scale free networks is that they are highly robust to random error.
ie, if a random node “fails” the connectivity of the overall network is not likely to be affected.
However, a trade-off is that they are highly sensitive to targeted attack.
ie, if a specific, high degree node is targeted and “incapacitated”, the connectivity of the overall network can be
affected dramatically.
35 / 36
Summary
A broad variety of systems can be described in terms of their network structure.
Doing so allows us to quantify and analyse system structure in terms of relatively simple properties.
These properties can have functional consequences, that may generalise across different systems.
Next lecture:
network dynamics
networks and agent-based models
36 / 36