ECE 841 Network Theory
Project 2
Junyao Kuang
2019.03.24
1. Regular network
To create the network with 100 nodes, I create 10*10 numbers, for nodes in i-th (0 < i < 10) row, for each node j in i-th row, I
create edges between node j and j+10. For nodes in i-th (0 < i <10) column, for each node j in i-th column, I create edges
between j and j+1. The network with 100 nodes are shown below:
Fig.1 10*10 regular network (left) and 32*32 regular network (right)
Network Average node degree Path length Clustering
10*10 3.6 6.67 0
32*32 3.88 21.3 0
2. Gilbert model
a. Average node degree
Here I assume the four probabilities are as following:
P1=1/100/(N-1), P2 =1/10/(N-1), P3=5/4/(N-1), P4=5/2/(N-1)
Consider N=10, 100 and 1000, we will have 12 cases. To get a more precise result, I calculate the node degree distribution by
averaging over 100 networks. e.g. for the case of 10 nodes with P1, I generate 100 networks, and calculate the node degree
distribution of each network and calculate the mean node degree over the 100 networks. It can be seen, the average node degrees
are close to the theoretical values. (the theoretical values are calculated by the formula <K>=Np)
N 10 10 10 10 100 100 100 100 1000 1000 1000 1000
P P1 P2 P3 P4 P1 P2 P3 P4 P1 P2 P3 P4
Node degree 0.012 0.09 1.22 2.49 0.0096 0.1 1.25 2.56 0.0094 0.1 1.26 2.49
Theoretical 0.01 0.1 1.25 2.5 0.01 0.1 1.25 2.5 0.01 0.1 1.25 2.5
b. Largest connected component
The results are also averaged over 100 networks as in part a, although the results are averaged over 100 networks, I find the
final results vary in different runs.
N 10 10 10 10 100 100 100 100 1000 1000 1000 1000
P P1 P2 P3 P4 P1 P2 P3 P4 P1 P2 P3 P4
Largest CC 1.03 1.44 5.8 9.18 1.45 2.41 34.23 90.16 2.03 3.41 341.5 894.4
c. Clustering coefficient
The results are also average over 100 networks, although there are differences between the calculated and theoretical values,
but they are acceptable, since when I did the calculation, there are differences between each run. (the theoretical values are
calculated from formula <C>=p)
N 10 10 10 10 100 100 100 100 1000 1000 1000 1000
P P1 P2 P3 P4 P1 P2 P3 P4 P1 P2 P3 P4
clustering 0.0 0.0 0.055 0.23 0.0 0.0 0.005 0.02 0.0 0.0 0.0005 0.002
Theoretical 0.001 0.01 0.14 0.28 0.0001 0.001 0.12 0.025 1e-5 0.0001 0.0012 0.0025
d. Node degree distribution
In this part, I also calculate the averaged node degree distribution. For each case (e.g. N=10, P=P1), I create 100 networks,
and save the node degree distribution of the 100 networks to a list, and find the final degree distribution over 100 samples.
So the values of stem plot is decimal values as shown in fig.2. For example, the node degree in top left panel are 9.91,
0.088, 0.002 for degree 0, 1, 2. Similarly, the degree distribution for N=100 nodes and N=1000 nodes are shown in fig.3
and fig.4.
Observing the node degree distributions of N=10, 100, 1000, I find for same P, the distribution values are exact the same
(the number of nodes does not affect the node degree distribution). In order to save time, here I only compare the cases of
N=10 as shown in fig.5 (the values are normalized to 1). In lecture, we know the node degree distribution follows Poisson
distribution. In fig.5, the red star points represent theoretical values, and the blue points with stems are the experimental
distribution, and they are almost overlapped in all the panels. Therefore, we can conclude that the node degree distribution
of Gilbert model follows Poisson distribution.
P=P1 P=P2
P=P3 P=P4
Fig.2 Node degree distribution of 10 nodes with P =P1, P2, P3, P4
P=P1 P=P2
P=P3 P=P4
Fig.3 Node degree distribution of 100 nodes with P =P1, P2, P3, P4
P=P1 P=P2
P=P3
P=P4
Fig.4 Node degree distribution of 1000 nodes with P =P1, P2, P3, P4
P=P1 P=P2
P=P3 P=P4
Fig.5 Node degree distribution comparison with P =P1, P2, P3, P4
e. Average shortest path length
Here, for N=10, the result is averaged over 100 networks. For N=100 and 1000, the result is averaged over 10 networks.
N 10 100 1000
P P4 P4 P4
Path length 2.04 4.82 7.23
f. An example network with N=100, and P=P3
Fig.6 example network (only nodes with edges are shown)
3. stochastic block model
Off diagonal 0.002 0.004 0.006 0.008 0.014 0.016
Clustering 0.0105 0.0102 0.01 0.0104 0.0143 0.016
Modularity 0.42 0.31 0.21 0.14 0.013 -0.02
Fig. 7 example network with N=100, P=0.008 (nodes with edges are shown)
4. Watts-Strogatz model
Here I assume the four probabilities are as following:
P1=0.01, P2 =0.25, P3=0.75, P4=0.98
m=2
1. The average node degree
The average node degree is 4 for all networks and the theoretical average node degree is also 4.
2. Clustering coefficient
Here, the values in the table are also averaged over 100 networks. From the table, it can be seen that when P is very small, the
clustering coefficients are close to the theoretical values, when p increases, there is a gap between the experiments and the
theoretical value. (theoretical value is from the formula in lecture notes).
For the Gilbert models to be compared, I generate networks with average node degree of 4, that is p=4/N for all of the cases.
N 10 10 10 10 100 100 100 100 1000 1000 1000 1000
P P1 P2 P3 P4 P1 P2 P3 P4 P1 P2 P3 P4
clustering 0.485 0.37 0.28 0.27 0.49 0.235 0.037 0.034 0.49 0.23 0.012 0.004
Theoretical 0.485 0.21 0.008 4e-6 0.485 0.21 0.008 4e-6 0.485 0.21 0.008 4e-6
Gnp model 0.36 0.038 0.0037
Gnp Theo 0.4 0.04 0.004
3. Degree distribution
The node degree distribution for all of the 12 cases are shown in fig. 8, 9 and 10. For each case (e.g. N=10, P=P1), I create 100
networks, and save the node degree distribution of the 100 networks to a list, and find the final degree distribution over the 100
samples. Therefore, the values of stem plot are decimal values as shown in fig. 8, 9 and 10.
P=P1 P=P2
P=P3 P=P4
Fig.8 Node degree distribution of 10 nodes with P =P1, P2, P3, P4
P=P1 P=P2
P=P3 P=P4
Fig.9 Node degree distribution of 10 nodes with P =P1, P2, P3, P4
P=P1
P=P2
P=P3
P=P4
Fig.10 Node degree distribution of 1000 nodes with P =P1, P2, P3, P4
In fig.8, 9 and 10, for same P, I find the node degree distributions are almost the same. So here I only compare the cases of
N=100 with theoretical values. According to lecture notes, when p increases and approaches 1, the degree distribution is almost
like a Poisson distribution. In fig.11, the experimental results are accord with the theoretical results (where red star points are
theoretical results and blue points with stems are experimental results). Also in fig 12. I compare the cases of N=10, 100 and
1000 with p=0.98. And from the fig 12, we can conclude they fit well with Poisson distribution.
P=P1
P=P2
P=P3 P=P4
Fig.11 Node degree distribution comparison with N=100 and P =P1, P2, P3, P4
N=10 N=100 N=1000
Fig.12 comparison between experimental results and theoretical results with P= P4
4. Average shortest path length
From the results below, it can be seen that the average shortest path length is very small. For the Gilbert model, I set the average
node degree as m=4, and with p=4/N. from the results, it can be concluded that when p increases, the average shortest path of
WS model converges to Gnp model, and the WS model becomes a random model.
N 10 10 10 10 100 100 100 100 1000 1000 1000 1000
P P1 P2 P3 P4 P1 P2 P3 P4 P1 P2 P3 P4
Path length 1.67 1.73 1.77 1.77 10.76 4.10 3.50 3.48 25.02 6.44 5.41 5.33
Gnp model 1.70 3.36 5.15
5. An example of a WS model with 100 nodes and p=0.25
5. Barabasi-Albert model
1. Random graph
Here, I started with a Gilbert model with N=10, p=0.5.
N=1000
N=100
Fig.13 Random graph generated from Barabasi model
2. Node degree distribution
For the node degree distribution, since generating the network is too time consuming, I only calculate the results over one
network. And there are differences in node degree distribution between each run. Fig.14 is the node degree distribution for the
2 networks. Fig.15 shows the comparison between normalized experimental results and theoretical results (the formula is from
the lecture nodes). It can be seen that the experimental results are accord with theoretical results.
N=100 N=1000
Fig.14 node degree distribution
N=100 N=1000
Fig.15 comparison between experimental results and theoretical results
3. Average clustering coefficient
The experimental results are close to the theoretical values, but there are still gaps. When I did the experiments, the results are
different although the experimental results are averaged over 100 networks.
N 100 1000
Clustering 0.139 0.026
Theoretical 0.106 0.024
4. Average path length
The experimental results are close to the theoretical values, but there are still gaps. When I did the experiments, the results are
different although the experimental results are averaged over 100 networks.
N 100 1000
Path length 1.73 3.19
Theoretical 3.01 3.57
