Danilo Martinez Network Science HW #1
- (10 points) Write a program (in any language, including matlab) to construct a random network with 100 nodes. Each node makes a link with any other node with probability p=0.1. Using the program, find:
library("network")
library(igraph)
n<-100
p.<-.1
g<-erdos.renyi.game(n,p.,type = c("gnp"),directed = FALSE,loops = FALSE)
plot.igraph(g)
- How many links does the random network you generated have?
length(get.edgelist(g))/2## [1] 519- What fraction of nodes have a degree of 0?
x<-numeric(100)
for (i in 1:100)
{
x<-c(degree(g,v=V(g), mode = c("total"),loops = FALSE, normalized = FALSE))
}
length(x[x==0])/100## [1] 0- What fraction of nodes have a degree of 1, 2, 3, . 99? Degree Value,
y<-numeric(100)
for (i in 1:100)
{
y[i]<-c(length(x[x==i-1])/100)
}
for (i in 2:100)
{
cat(i-1)
cat("\t\t")
cat("\t\t")
cat(y[i])
cat(",\n")
}## 1 0,
## 2 0,
## 3 0,
## 4 0.02,
## 5 0.01,
## 6 0.04,
## 7 0.08,
## 8 0.12,
## 9 0.12,
## 10 0.16,
## 11 0.11,
## 12 0.12,
## 13 0.11,
## 14 0.03,
## 15 0.02,
## 16 0.04,
## 17 0.01,
## 18 0,
## 19 0,
## 20 0.01,
## 21 0,
## 22 0,
## 23 0,
## 24 0,
## 25 0,
## 26 0,
## 27 0,
## 28 0,
## 29 0,
## 30 0,
## 31 0,
## 32 0,
## 33 0,
## 34 0,
## 35 0,
## 36 0,
## 37 0,
## 38 0,
## 39 0,
## 40 0,
## 41 0,
## 42 0,
## 43 0,
## 44 0,
## 45 0,
## 46 0,
## 47 0,
## 48 0,
## 49 0,
## 50 0,
## 51 0,
## 52 0,
## 53 0,
## 54 0,
## 55 0,
## 56 0,
## 57 0,
## 58 0,
## 59 0,
## 60 0,
## 61 0,
## 62 0,
## 63 0,
## 64 0,
## 65 0,
## 66 0,
## 67 0,
## 68 0,
## 69 0,
## 70 0,
## 71 0,
## 72 0,
## 73 0,
## 74 0,
## 75 0,
## 76 0,
## 77 0,
## 78 0,
## 79 0,
## 80 0,
## 81 0,
## 82 0,
## 83 0,
## 84 0,
## 85 0,
## 86 0,
## 87 0,
## 88 0,
## 89 0,
## 90 0,
## 91 0,
## 92 0,
## 93 0,
## 94 0,
## 95 0,
## 96 0,
## 97 0,
## 98 0,
## 99 0,- Plot the degree distribution (Fractions on the y-axis and degrees on the x-axis).
dd<-numeric(100)
dd<-c(degree.distribution(g,cumulative = FALSE,loops=FALSE,mode=c("total")))
plot(dd,main = "Degree Disribution for p=.10",xlab = "Degrees",ylab = "Fractions")
rm(list=ls())- Repeat (a), (b), (c), and (d) for p=0.3. Instructions: For this question, do NOT submit the code. I will ask for it, if needed. Make sure you save your code till the end of the semester. You will need the code for later HWs.
n<-100
p.<-.3
g<-erdos.renyi.game(n,p.,type = c("gnp"),directed = FALSE,loops = FALSE)
plot.igraph(g)
- How many links does the random network you generated have?
length(get.edgelist(g))/2## [1] 1410- What fraction of nodes have a degree of 0?
x<-numeric(100)
for (i in 1:100)
{
x<-c(degree(g,v=V(g), mode = c("total"),loops = FALSE, normalized = FALSE))
}
length(x[x==0])/100## [1] 0- What fraction of nodes have a degree of 1, 2, 3, . 99?
y<-numeric(100)
for (i in 1:100)
{
y[i]<-c(length(x[x==i-1])/100)
}
for (i in 2:100)
{
cat(i-1)
cat("\t\t")
cat("\t\t")
cat(y[i])
cat(",\n")
}## 1 0,
## 2 0,
## 3 0,
## 4 0,
## 5 0,
## 6 0,
## 7 0,
## 8 0,
## 9 0,
## 10 0,
## 11 0,
## 12 0,
## 13 0,
## 14 0,
## 15 0,
## 16 0,
## 17 0.01,
## 18 0,
## 19 0,
## 20 0.04,
## 21 0.03,
## 22 0.03,
## 23 0.06,
## 24 0.03,
## 25 0.05,
## 26 0.11,
## 27 0.11,
## 28 0.05,
## 29 0.05,
## 30 0.15,
## 31 0.05,
## 32 0.08,
## 33 0.03,
## 34 0.04,
## 35 0.02,
## 36 0.05,
## 37 0,
## 38 0,
## 39 0,
## 40 0,
## 41 0,
## 42 0,
## 43 0,
## 44 0,
## 45 0.01,
## 46 0,
## 47 0,
## 48 0,
## 49 0,
## 50 0,
## 51 0,
## 52 0,
## 53 0,
## 54 0,
## 55 0,
## 56 0,
## 57 0,
## 58 0,
## 59 0,
## 60 0,
## 61 0,
## 62 0,
## 63 0,
## 64 0,
## 65 0,
## 66 0,
## 67 0,
## 68 0,
## 69 0,
## 70 0,
## 71 0,
## 72 0,
## 73 0,
## 74 0,
## 75 0,
## 76 0,
## 77 0,
## 78 0,
## 79 0,
## 80 0,
## 81 0,
## 82 0,
## 83 0,
## 84 0,
## 85 0,
## 86 0,
## 87 0,
## 88 0,
## 89 0,
## 90 0,
## 91 0,
## 92 0,
## 93 0,
## 94 0,
## 95 0,
## 96 0,
## 97 0,
## 98 0,
## 99 0,- Plot the degree distribution (Fractions on the y-axis and degrees on the x-axis). Degree Value,
dd<-numeric(100)
dd<-c(degree.distribution(g,cumulative = FALSE,loops=FALSE,mode=c("total")))
plot(dd,main = "Degree Disribution for p=.30",xlab = "Degrees",ylab = "Fractions")
rm(list=ls())- (8 points) Consider a random network with 100 nodes. A link exists between any pair with probability p=0.1. Find analytically:
- What is the expected number of links in the network? G(N,P) ((N 2) / 2) * P Number of possible pairs (N 2) = N (N-1) / 2 Probability of link = .1
((100 * 99) / 2) * .1 ## [1] 495- What is the probability that a randomly chosen nodes has no links? P(L): Probability of having L links in a Network with N nodes and probability P P(L) = ((N 2) / L) * P^L * (1 -P)^((N(N-1))/2)-L N = 0 We can use binomial distribution
dbinom(0,99,.10)## [1] 2.951267e-05- What is the probability that a a randomly chosen nodes has 1, 2, 3, .. 99 links? Probability of links 1 through 99 P(L) = ((N 2) / L) * P^L * (1 -P)^((N(N-1))/2)-L N = 1-99 We can use binomial distribution Link Probability,
y<-numeric(100)
for (i in 1:100)
{
y[i]<-c(dbinom(i-1,99,.10))
}
for (i in 2:99)
{
cat(i-1)
cat("\t\t")
cat("\t\t")
cat(y[i])
cat("\n")
}## 1 0.0003246393
## 2 0.001767481
## 3 0.006349838
## 4 0.0169329
## 5 0.03574724
## 6 0.06222667
## 7 0.09185842
## 8 0.1173746
## 9 0.1318653
## 10 0.1318653
## 11 0.1185456
## 12 0.09659272
## 13 0.07182536
## 14 0.04902366
## 15 0.03086675
## 16 0.0180056
## 17 0.009767745
## 18 0.004944167
## 19 0.002341974
## 20 0.001040877
## 21 0.0004350757
## 22 0.0001713935
## 23 6.375506e-05
## 24 2.243233e-05
## 25 7.477445e-06
## 26 2.364662e-06
## 27 7.103717e-07
## 28 2.029633e-07
## 29 5.521225e-08
## 30 1.431429e-08
## 31 3.540093e-09
## 32 8.358552e-10
## 33 1.885599e-10
## 34 4.066979e-11
## 35 8.392179e-12
## 36 1.657714e-12
## 37 3.136216e-13
## 38 5.685538e-14
## 39 9.88085e-15
## 40 1.646808e-15
## 41 2.633108e-16
## 42 4.040219e-17
## 43 5.95071e-18
## 44 8.415145e-19
## 45 1.142798e-19
## 46 1.490605e-20
## 47 1.867662e-21
## 48 2.248111e-22
## 49 2.599857e-23
## 50 2.88873e-24
## 51 3.083829e-25
## 52 3.162901e-26
## 53 3.116486e-27
## 54 2.94976e-28
## 55 2.6816e-29
## 56 2.341079e-30
## 57 1.962308e-31
## 58 1.578869e-32
## 59 1.219089e-33
## 60 9.030288e-35
## 61 6.414959e-36
## 62 4.36861e-37
## 63 2.850768e-38
## 64 1.78173e-39
## 65 1.065992e-40
## 66 6.10164e-42
## 67 3.339206e-43
## 68 1.74599e-44
## 69 8.715893e-46
## 70 4.150425e-47
## 71 1.883604e-48
## 72 8.139032e-50
## 73 3.344808e-51
## 74 1.305781e-52
## 75 4.836225e-54
## 76 1.696921e-55
## 77 5.631917e-57
## 78 1.764988e-58
## 79 5.213045e-60
## 80 1.448068e-61
## 81 3.774114e-63
## 82 9.205157e-65
## 83 2.094882e-66
## 84 4.433612e-68
## 85 8.693357e-70
## 86 1.572442e-71
## 87 2.610695e-73
## 88 3.955599e-75
## 89 5.432159e-77
## 90 6.706369e-79
## 91 7.369636e-81
## 92 7.120421e-83
## 93 5.954952e-85
## 94 4.22337e-87
## 95 2.469807e-89
## 96 1.143429e-91
## 97 3.92931e-94
## 98 8.91e-97- Plot the degree distribution (The probabilities on the y-axis and degrees on the x-axis). Degree Distribution formula is: P(k) = (N-1 k) * P^k * (1-p)^((N-1)-k)
plot(y,main = "Degree Disribution for p=.10",xlab = "Degrees",ylab = "Fractions")
rm(list=ls())- Repeat (a), (b), (c), and (d) for p=0.3. Instructions: For Q2, show all the steps you used to compute the probabilities.
- What is the expected number of links in the network? G(N,P) ((N 2) / 2) * P Number of possible pairs (N 2) = N (N-1) / 2 Probability of link = .3
((100 * 99) / 2) * .3 ## [1] 1485- What is the probability that a randomly chosen nodes has no links? P(L): Probability of having L links in a Network with N nodes and probability P P(L) = ((N 2) / L) * P^L * (1 -P)^((N(N-1))/2)-L N = 0 We can use binomial distribution
dbinom(0,99,.3)## [1] 4.620681e-16- What is the probability that a a randomly chosen nodes has 1, 2, 3, .. 99 links? Probability of links 1 through 99 P(L) = ((N 2) / L) * P^L * (1 -P)^((N(N-1))/2)-L N = 1-99 We can use binomial distribution
y<-numeric(100)
for (i in 1:100)
{
y[i]<-c(dbinom(i-1,99,.3))
}
for (i in 2:100)
{
cat(i-1)
cat("\t\t")
cat("\t\t")
cat(y[i])
cat(",\n")
}## 1 1.960489e-14,
## 2 4.117027e-13,
## 3 5.705022e-12,
## 4 5.868023e-11,
## 5 4.778247e-10,
## 6 3.208252e-09,
## 7 1.826739e-08,
## 8 9.003215e-08,
## 9 3.901393e-07,
## 10 1.504823e-06,
## 11 5.218023e-06,
## 12 1.63995e-05,
## 13 4.703593e-05,
## 14 0.0001238293,
## 15 0.0003007283,
## 16 0.0006766386,
## 17 0.001415824,
## 18 0.002764227,
## 19 0.00505043,
## 20 0.00865788,
## 21 0.01395862,
## 22 0.02120986,
## 23 0.03043153,
## 24 0.04129994,
## 25 0.05309992,
## 26 0.06477023,
## 27 0.07505122,
## 28 0.0827095,
## 29 0.08678386,
## 30 0.08678386,
## 31 0.08278461,
## 32 0.07539313,
## 33 0.06560181,
## 34 0.0545763,
## 35 0.04343828,
## 36 0.03309583,
## 37 0.02415101,
## 38 0.01688755,
## 39 0.01132023,
## 40 0.007277288,
## 41 0.004488083,
## 42 0.002656213,
## 43 0.001509011,
## 44 0.000823097,
## 45 0.000431146,
## 46 0.000216912,
## 47 0.0001048298,
## 48 4.867098e-05,
## 49 2.171038e-05,
## 50 9.304448e-06,
## 51 3.831243e-06,
## 52 1.515657e-06,
## 53 5.760312e-07,
## 54 2.102971e-07,
## 55 7.374055e-08,
## 56 2.4831e-08,
## 57 8.028068e-09,
## 58 2.491469e-09,
## 59 7.420115e-10,
## 60 2.120033e-10,
## 61 5.808989e-11,
## 62 1.525863e-11,
## 63 3.840609e-12,
## 64 9.25861e-13,
## 65 2.136602e-13,
## 66 4.717174e-14,
## 67 9.957361e-15,
## 68 2.008207e-15,
## 69 3.866735e-16,
## 70 7.102166e-17,
## 71 1.243236e-17,
## 72 2.07206e-18,
## 73 3.284479e-19,
## 74 4.945741e-20,
## 75 7.065344e-21,
## 76 9.56212e-22,
## 77 1.224093e-22,
## 78 1.479673e-23,
## 79 1.685704e-24,
## 80 1.806111e-25,
## 81 1.815667e-26,
## 82 1.708119e-27,
## 83 1.499382e-28,
## 84 1.223985e-29,
## 85 9.257029e-31,
## 86 6.458392e-32,
## 87 4.135916e-33,
## 88 2.417094e-34,
## 89 1.280323e-35,
## 90 6.096774e-37,
## 91 2.58419e-38,
## 92 9.630522e-40,
## 93 3.10662e-41,
## 94 8.498352e-43,
## 95 1.916922e-44,
## 96 3.423074e-46,
## 97 4.537212e-48,
## 98 3.968407e-50,
## 99 1.717925e-52,- Plot the degree distribution (The probabilities on the y-axis and degrees on the x-axis). Degree Distribution formula is: P(k) = (N-1 k) * P^k * (1-p)^((N-1)-k)
plot(y,main = "Degree Disribution for p=.30",xlab = "Degrees",ylab = "Fractions")
rm(list=ls())- (4 points) Consider a random network with 10 nodes where a link between any two nodes exists with probability 0.2. +Find the probability that the network will have 30 links. How many realizations of 30 links are possible? Lmin = 0 Lmax = 45 (N(N-1))/2 Therefore, a network with 10 nodes can have anywhere from 0 to 45 links. P(L): Probability to have exactly L links in a network having N nodes with a probability P = ((N 2) L)) * P^L * (1-P)^(N * N-1)-L Replacing variables N and L N = 45 L = 30 Using binomial distribution
dbinom(30,45,.20)## [1] 1.302872e-11How many different realizations of 30 links is equivalent to Combination (45 30):
factorial(45)/(factorial(30) * factorial(15))## [1] 344867425584rm(list=ls())4.(4 points) Show that the local clustering coefficient of a node is independent of the node’s degree in a random (ER) network. We will use a random network of 100 nodes, having a probability of .3
n<-100
p.<-.3
g<-erdos.renyi.game(n,p.,type = c("gnp"),directed = FALSE,loops = FALSE)
plot.igraph(g)
Local clustering coefficient for each node of the random network quantifies how close the node’s neighbors are to becoming a complete graph. Node LocalCLust.Coeff.,
z<-numeric(100)
for (i in 1:100)
{
z<-c(transitivity(g,type = c("localundirected")))
}
for (i in 1:100)
{
cat(i)
cat("\t\t")
cat("\t\t")
cat(z[i])
cat(",\n")
}## 1 0.3075269,
## 2 0.2820513,
## 3 0.2905526,
## 4 0.3593074,
## 5 0.3048433,
## 6 0.282197,
## 7 0.3138138,
## 8 0.2946237,
## 9 0.315873,
## 10 0.2727273,
## 11 0.2333333,
## 12 0.3133333,
## 13 0.2933333,
## 14 0.3201058,
## 15 0.292437,
## 16 0.2413793,
## 17 0.2942529,
## 18 0.3201581,
## 19 0.2905983,
## 20 0.3029557,
## 21 0.3042328,
## 22 0.2655462,
## 23 0.2943548,
## 24 0.2597403,
## 25 0.2608696,
## 26 0.3126984,
## 27 0.2967742,
## 28 0.3139785,
## 29 0.3030303,
## 30 0.3066667,
## 31 0.2966667,
## 32 0.3019943,
## 33 0.2910053,
## 34 0.273399,
## 35 0.3227513,
## 36 0.2738462,
## 37 0.2862319,
## 38 0.282197,
## 39 0.2952381,
## 40 0.2820513,
## 41 0.3438735,
## 42 0.2857143,
## 43 0.2936508,
## 44 0.2883598,
## 45 0.2887701,
## 46 0.3253968,
## 47 0.2758621,
## 48 0.3034483,
## 49 0.2866667,
## 50 0.3304843,
## 51 0.3078818,
## 52 0.2802419,
## 53 0.3103448,
## 54 0.2860215,
## 55 0.2678063,
## 56 0.3208556,
## 57 0.2646154,
## 58 0.291954,
## 59 0.3030303,
## 60 0.2782258,
## 61 0.2769231,
## 62 0.3203463,
## 63 0.3004032,
## 64 0.2651515,
## 65 0.2666667,
## 66 0.2769231,
## 67 0.3044097,
## 68 0.3075269,
## 69 0.3012478,
## 70 0.3275862,
## 71 0.3032258,
## 72 0.2982456,
## 73 0.2887701,
## 74 0.27,
## 75 0.317734,
## 76 0.2763533,
## 77 0.3185484,
## 78 0.3015873,
## 79 0.3193277,
## 80 0.2900433,
## 81 0.2930299,
## 82 0.2804233,
## 83 0.3247863,
## 84 0.3108108,
## 85 0.3349754,
## 86 0.3015873,
## 87 0.2877493,
## 88 0.3546798,
## 89 0.2907563,
## 90 0.2962963,
## 91 0.3012195,
## 92 0.2655971,
## 93 0.3290043,
## 94 0.3166667,
## 95 0.3185484,
## 96 0.2510823,
## 97 0.3428571,
## 98 0.3133333,
## 99 0.3042328,
## 100 0.3185484,The degree for each node in the random network shows now many connections a node has to other nodes. Node Degree,
x<-numeric(100)
for (i in 1:100)
{
x<-c(degree(g,v=V(g), mode = c("total"),loops = FALSE, normalized = FALSE))
}
for (i in 1:100)
{
cat(i)
cat("\t\t")
cat("\t\t")
cat(x[i])
cat(",\n")
}## 1 31,
## 2 27,
## 3 34,
## 4 22,
## 5 27,
## 6 33,
## 7 37,
## 8 31,
## 9 36,
## 10 34,
## 11 21,
## 12 25,
## 13 25,
## 14 28,
## 15 35,
## 16 29,
## 17 30,
## 18 23,
## 19 27,
## 20 29,
## 21 28,
## 22 35,
## 23 32,
## 24 22,
## 25 23,
## 26 36,
## 27 31,
## 28 31,
## 29 33,
## 30 25,
## 31 25,
## 32 27,
## 33 28,
## 34 29,
## 35 28,
## 36 26,
## 37 24,
## 38 33,
## 39 36,
## 40 27,
## 41 23,
## 42 22,
## 43 28,
## 44 28,
## 45 34,
## 46 28,
## 47 29,
## 48 30,
## 49 25,
## 50 27,
## 51 29,
## 52 32,
## 53 30,
## 54 31,
## 55 27,
## 56 34,
## 57 26,
## 58 30,
## 59 34,
## 60 32,
## 61 26,
## 62 22,
## 63 32,
## 64 33,
## 65 25,
## 66 26,
## 67 38,
## 68 31,
## 69 34,
## 70 29,
## 71 31,
## 72 19,
## 73 34,
## 74 25,
## 75 29,
## 76 27,
## 77 32,
## 78 28,
## 79 35,
## 80 22,
## 81 38,
## 82 28,
## 83 27,
## 84 37,
## 85 29,
## 86 28,
## 87 27,
## 88 29,
## 89 35,
## 90 28,
## 91 41,
## 92 34,
## 93 22,
## 94 25,
## 95 32,
## 96 22,
## 97 21,
## 98 25,
## 99 28,
## 100 32,We can now use a technique in statistics to calculate the correlation coefficient of the clustering coefficient and the degree distribution, and then plotting it. The correlation coefficient value has to be between -1 and 1. The more negative, the more independent. The more positive, the more dependent.
cor(x,z)## [1] 0.03168245plot(x,z,main = "Correlation Plot",xlab = "Node Degrees",ylab = "Local Clust. Coeff.")
lines(lowess(x,z))
rm(list=ls())The correlation line is horizontal, which indicates no correlation or dependence between the two factors.