Simulation of Complex Network Models

Akrati Saxena
Outline
● Introduction
● Time and Space Complexity Analysis
● Graph Data Structures
● Graph Models:
○ Efficient Erdős Rényi Graph Simulation
○ Watts-Strogatz Model
○ Configuration Model Simulation
■ Link Stub Reconnection
■ Repeated Link Stub Reconnection
■ Local Rewiring Algorithm
● Summary and Outlook
Bubble Sort
bubbleSort(arr) {
int n = arr.size();
bool swapped;

for (int i = 0; i < n - 1; i++) {

swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// If no two elements were swapped, then break
if (!swapped)
break;
}
}
Selection Sort
procedure selectionSort(A : list of sortable items)
n = length(A)
for i = 1 to n do
{
// Find the least element in A[i … n]
min = i
for j = i+1 to n do
{
if (A[j] < A[min]) then min = j
}
swap(A[i] and A[min])
}
end procedure
Graph Model Simulation
● Various aspects required when implementing a graph model simulation :
○ Which data structure to choose ?
○ How to reach a good time and space efficiency ?
○ How to guarantee that the graph has the desired properties ?
○ How to achieve uniform sampling ?

Roadmap : Time and space complexity → data-structures for graphs → graph model
simulators.
Time and Space Complexity
● Computational complexity theory deals with the time and space required to solve
problems. E.g.
○ how much memory is required to store information (e.g. a graph) of size n using
a given data structure (space complexity of a data-structure).
○ solve a well defined problem (e.g. sorting) with input size n, by means of a given
algorithm A. Typically the worst case over all instances is considered.

● Space complexity is typically measured in the number of bits or of (integer)numbers

required to store information.
● Time complexity is typically measured in the number of basic operations (additions,
multiplications, elementary function computations, comparisons) required to solve a
computational problem
Big ‘O’ notation
Big ‘O’ notation
Algorithmic Complexity
● Worst-case or upper bound: Big-O: O(n)
-Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the worst
case complexity of an algorithm. It is widely used to analyze an algorithm as we are always interested in
the worst case scenario. For any value of n, the running time of an algorithm does not cross time
provided by O(f(n)).
● Best-case or lower bound: Big-Omega: Ω(n)
-Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the
best case complexity of an algorithm.
● Average-case: Big-Theta: Θ(n)
-Theta notation encloses the function from above and below. Since it represents the upper and the lower
bound of the running time of an algorithm, it is used for analyzing the average case complexity of an
algorithm.
● Non-tight upper bound: o(n)
● Non-tight lower bound: ω(n)
Big ‘O’ notation
Examples
Examples
Algorithmic complexity
Graph Data Structures
Graph Data Structures
There are three common data structures used to store graphs :
● Edge list : The graph is stored as a set of vertices V, and a set of edges (pairs of
vertices) E ⊆ V ×V.

● Adjacency list : The graph is stored as an adjacency list, that is an array of vertices,
and for each vertex a list of nodes that are adjacent to it.
● Adjacency matrix : The graph is stored in a double indexed array a[i][j], i ∈ {1, ...,n}, j ∈
{1, ...,n} and n = |V|, where a[i][j] = 1 if node i is connected to node j and a[i][j] = 0
otherwise.
Space complexity of graph data structures
The space complexity of these graph data structures is as follows :
● Edge list : Θ(|V|+|E|). (Assuming a list of nodes is provided besides the list of edges)

● Adjacency list : Θ(|V|+|E|). (Every node requires one storage cell and every edge is
represented once by a node, in the list of the predecessor.)

● Adjacency matrix : Θ(|V|2). (Every pair is represented by means of a boolean variable,

even if there is no edge.)

In practise, lists can be augmented by auxiliary data structures, such as

(1) balanced search tree index, used to locate and/or update elements in a list in O(logn)
time, or
(2) they can be kept in a sorted list on the node index.
Alternative graph data structures
Think about other graph representations: visibility graphs, interval graphs, disc graphs
Time complexity of basic graph operations
Querying the existence of an edge
● Adjacency matrix : O(1).
● Edge list :
○ O(|E|). If tree index is used or sorting is maintained :
○ O(log(|E|)). (Binary search can be used to find the edge).
● Adjacency lists : O(|V|). (The first node needs to be found in the outer list, and then the
second node in the list connected to this node).
Using a tree index or sorting, this can be further reduced to O(log(|V|)).
Time complexity of basic graph operations
Inserting and deleting edges
● Adjacency matrix : O(1)
● Edge list :
○ insertion in O(1), deletion in O(|E|) (insertion at the end of the list, deletion
requires to move all subsequent edges in the list |E|−1
○ If a tree index is used the time complexity of insertion will be in O(log(|E|)) and
that of deletion in O(log(|E|)). (Rebalancing the tree is required). Keeping sorted
lists will yield a time complexity in O(|E|) for both insertion and deletion.
● Adjacency list : replace |E| by |V| in formula for edge list.
Complexity of Network Generators
Two variants of Erdős Rényi graph
1. G(n,p) : An instance of the Erdős-Rényi Graph G(n,p) is a graph with n nodes and it is
decided with equal probability p for each pair i and j , with i ≠ j , whether there is an
edge from i to j .
2. G(n,m): An instance of the Erdős-Rényi Graph Gm(n,m) is a graph with m edges. The
edges are assigned randomly and without repetition among the pairs i to j with i ≠ j .
Simulation of G(n,m)
Analysis of Fisher Yates Shuffle
The Fisher Yates shuffle is shuffling a list of size N uniformly randomly, i.e. every sequence
has the same probability :
1: input : List (or array) of size N
2: for i = 1 : (N −1) do ▷ Fisher Yates Shuffle
3: z ← uniform random integer between i (i is included) and N (N is included)
4: Swap value of e[i] and e[z]
5: return first

Uses Fisher Yates shuffle to generate random permutation. The time complexity is O(N),
since a swap operation and generating a uniform random integer can be considered as of
time complexity O(1).
Since the output size is Θ(N) this algorithm is asymptotically (in big Oh notation) optimal.
Simulation of G(n, p)
Discuss the space and time complexity of G(n,p)

**For the reference, you can use the implementation that we used in the last lecture.
Watts-Strogatz Model
The model works as follows:
1. Lattice Structure: Start with a ring lattice of n nodes where each node is connected to
its k neighbors within a certain range.
2. Rewiring: Randomly rewire some of the edges with a probability p, introducing
randomness to the network. This rewiring decreases the average path length while
maintaining a high clustering coefficient.
Watts-Strogatz Model - Activity
1. Write down the algorithm to implement Watts-Strogatz model.
2. Implement this algorithm in Python. (You can do it Later)
3. Discuss the time and space complexity of your algorithm.

4. Check if your algorithm might lead to disconnected network. If yes, update your
algorithm so that it always returns a connected graph.
Simulation of configuration model
Simulation of CM : Link stub reconnection
Vertices with link stubs – simulation snapshot

http://mathinsight.org/generating_networks_desired_degree_distribution
Repeated Link Stub Reconnection
● The ‘link stub’ reconnection algorithm can create self-loops and multiedges
● Removing them would introduce a bias
● We can run it repeatedly, until for the first time these are not occuring
Local Rewiring Algorithm
⃗
Idea Maslov, Sneppen and Zaliznyak : Start from a graph with degree distribution k
⃗ .
and perform swap operations, preserving the degree distribution k
Local Rewiring Algorithm
● Edges are randomly swapped in such a way that the degree sequence is preserved
● However, it has shown to be biased (non uniform sampling) - depending on time and
starting point
● This occurs even if, by construction, it never generates self-loops or multi-edges.
● To restore uniform sampling, one should introduce an acceptance probability for the
random moves which is however computationally very costly.
● This is shown in these two papers (for directed and undirected graphs), which are
cited in the lecture notes (and in our paper above):
○ A.C.C Coolen, A. De Martino, A. Annibale, J. Stat. Phys. B 136, 103567 (2009).
○ E.S. Roberts, A.C.C. Coolen, Phys. Rev. E 85, 046103 (2012).
Barabási-Albert (BA) Model
● The Barabási-Albert (BA) model is a preferential attachment model.
● In the simulation a new node is introduced in each connection and it connects with
preference to a node with a high degree.
● It serves as a contrast to the Erdős-Rényi model, focusing on the generation of
scale-free networks in which the degree distribution is not concentrated around a
mean value, but the degree distribution follows a power law d(k) ∼ k−τ.
Simulation of the BA Model
In the BA model, a graph starts with m0 initial nodes. New nodes are then sequentially
added to the graph, each establishing m≤m0 edges to existing nodes. The probability Pr(k)
of connecting to a node with degree k is given by :

where the sum is taken over all degrees kj of existing nodes, and q is a constant, that is in
the canonical BA model set to q = 1.
● For an implementation of the model see the lecture notes.
● Observe, that opposed to the previously discussed graph models, the BA model
always produces fully connected graphs.
● For q >= 1 they have the small world property, that is the shortest path between any
two nodes, tends to be smaller than log (n).
Simulation of the BA Model
Discuss the Complexity of your algorithm

- We can start with the algorithm from lecture notes.

- Any other implementation method?

Learning Goals
✓ What is the time and space complexity?

✓ Different Graph Data Structures

✓ Compute the complexity of basic algorithms

✓ Complexity of Random Networks

✓ Watts-Strogatz model and its complexity Analysis

✓ Configuration Model and its variations

✓ Barabasi Albert Model and its different simulation methods

Homework Discussion
Some Important Links to Explore
- Introduction to Algorithmic Complexity: https://discrete.gr/complexity/ (before
logarithms)

- Watch this video to understand Big-O, Omega and Theta Notation:

https://www.youtube.com/watch?v=pe250F4ttmE

- For further understanding of Big-O, you can watch this:

https://www.youtube.com/watch?v=ei-A_wy5Yxw (optional)

- L’Hospital Rule: https://www.cs.ubc.ca/wccce/Program03/papers/Obi2.pdf