Lab 4 :
DKCH
2020-05-05
1 Q5a: Robustness of Networks
1.1 network_removal_vertex_or_edge_by_random_only
1.1.1 Random Vertex Removal
removal_N = 20
removal_out = network_removal_vertex_or_edge_by_random_only(fblog_igraph, option = "vertex",
method = "random", removal_N = 20)
removal_out method option max.component.orig max.component.removed
1: random Vertex removal 192 192.00
2: random Vertex removal 192 191.00
3: random Vertex removal 192 190.00
4: random Vertex removal 192 189.00
5: random Vertex removal 192 188.00
---
189: random Vertex removal 192 1.45
190: random Vertex removal 192 1.30
191: random Vertex removal 192 1.05
192: random Vertex removal 192 1.00
193: random Vertex removal 192 192.00
component.proportion removed.proportion
1: 1.000000000 0.000000000
2: 0.994791667 0.005208333
3: 0.989583333 0.010416667
4: 0.984375000 0.015625000
5: 0.979166667 0.020833333
---
189: 0.007552083 0.979166667
190: 0.006770833 0.984375000
191: 0.005468750 0.989583333
192: 0.005208333 0.994791667
193: 0.000000000 1.000000000plot(removal_out$max.component.removed, xlab = "vertex", ylab = "average of max.component.removal",
main = paste("Random Vertex Removal: N =", removal_N))
1.1.2 Random Edge Removal
removal_N = 20
removal_out = network_removal_vertex_or_edge_by_random_only(fblog_igraph, option = "edge",
method = "random", removal_N = 20)
removal_out method option max.component.orig max.component.removed
1: random Edge removal 192 192.0
2: random Edge removal 192 192.0
3: random Edge removal 192 192.0
4: random Edge removal 192 192.0
5: random Edge removal 192 192.0
---
1428: random Edge removal 192 2.1
1429: random Edge removal 192 2.0
1430: random Edge removal 192 2.0
1431: random Edge removal 192 2.0
1432: random Edge removal 192 192.0
component.proportion removed.proportion
1: 1.00000000 0.000000000
2: 1.00000000 0.000698812
3: 1.00000000 0.001397624
4: 1.00000000 0.002096436
5: 1.00000000 0.002795248
---
1428: 0.01093750 0.997204752
1429: 0.01041667 0.997903564
1430: 0.01041667 0.998602376
1431: 0.01041667 0.999301188
1432: 0.00000000 1.000000000plot(removal_out$component.proportion, xlab = "edge", ylab = "average of max.component.removal",
main = paste("Random Edge Removal: N =", removal_N))
1.2 network_removal_vertex_or_edge_by_degree_only
1.2.1 Degree Vertex Removal
out_vertex_degree = network_removal_vertex_or_edge_by_degree_only(fblog_igraph, option = "vertex",
method = "degree")
out_vertex_degree method option max.component.orig max.component.removed
1: degree Vertex Removal 192 192
2: degree Vertex Removal 192 191
3: degree Vertex Removal 192 190
4: degree Vertex Removal 192 189
5: degree Vertex Removal 192 188
---
189: degree Vertex Removal 192 1
190: degree Vertex Removal 192 1
191: degree Vertex Removal 192 1
192: degree Vertex Removal 192 1
193: degree Vertex Removal 192 192
component.proportion removed.proportion
1: 1.000000000 0.000000000
2: 0.994791667 0.005208333
3: 0.989583333 0.010416667
4: 0.984375000 0.015625000
5: 0.979166667 0.020833333
---
189: 0.005208333 0.979166667
190: 0.005208333 0.984375000
191: 0.005208333 0.989583333
192: 0.005208333 0.994791667
193: 0.000000000 1.000000000plot(out_vertex_degree$max.component.removed, xlab = "vertex", ylab = "max.component.removal",
main = "Degree Vertex Removal")
1.2.2 Degree Edge Removal
- Problem of breaking ties too serious in Degree Edge Removal
out_edge_degree = network_removal_vertex_or_edge_by_degree_only(fblog_igraph, option = "edge",
method = "degree")
plot(out_edge_degree$max.component.removed, , xlab = "edge", ylab = "max.component.removal",
main = "Degree Edge Removal: Problem of breaking ties too serious ", col = "red")
2 5b. Random graphs as null models for networks
2.1 Q5b1
2.1.1 Basic statistics of igraph net
The “macaque” dataset entails a network of established functional connections between brain areas understood to be involved with the tactile function of the visual cortex in macaque monkeys that published by Négyessy et al. (2006)
IGRAPH f7130f3 DN-- 45 463 --
+ attr: Citation (g/c), Author (g/c), shape (v/c), name (v/c)
+ edges from f7130f3 (vertex names):
[1] V1 ->V2 V1 ->V3 V1 ->V3A V1 ->V4 V1 ->V4t V1 ->MT
[7] V1 ->PO V1 ->PIP V2 ->V1 V2 ->V3 V2 ->V3A V2 ->V4
[13] V2 ->V4t V2 ->VOT V2 ->VP V2 ->MT V2 ->MSTd/p V2 ->MSTl
[19] V2 ->PO V2 ->PIP V2 ->VIP V2 ->FST V2 ->FEF V3 ->V1
[25] V3 ->V2 V3 ->V3A V3 ->V4 V3 ->V4t V3 ->MT V3 ->MSTd/p
[31] V3 ->PO V3 ->LIP V3 ->PIP V3 ->VIP V3 ->FST V3 ->TF
[37] V3 ->FEF V3A->V1 V3A->V2 V3A->V3 V3A->V4 V3A->VP
[43] V3A->MT V3A->MSTd/p V3A->MSTl V3A->PO V3A->LIP V3A->DP
+ ... omitted several edges[1] 463[1] 45 V1 V2 V3 V3A V4 V4t VOT VP MT MSTd/p MSTl
16 28 28 25 40 17 10 27 32 33 19
PO LIP PIP VIP DP 7a FST PITd PITv CITd CITv
28 38 16 40 20 24 35 13 20 9 16
AITd AITv STPp STPa TF TH FEF 46 3a 3b 1
14 12 20 9 29 21 38 36 12 8 15
2 5 Ri SII 7b 4 6 SMA Ig Id 35
20 20 8 23 22 17 20 16 11 7 6
36
8 [1] 20.57778 [1] 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
[7] 0.02222222 0.02222222 0.06666667 0.04444444 0.02222222 0.02222222
[13] 0.04444444 0.02222222 0.02222222 0.02222222 0.08888889 0.04444444
[19] 0.00000000 0.02222222 0.13333333 0.02222222 0.02222222 0.02222222
[25] 0.02222222 0.02222222 0.00000000 0.02222222 0.06666667 0.02222222
[31] 0.00000000 0.00000000 0.02222222 0.02222222 0.00000000 0.02222222
[37] 0.02222222 0.00000000 0.04444444 0.00000000 0.04444444
2.1.2 Directed graphs of the clustering coefficient
- The following formaulate is directly copied and pasted from the paper of Fagiolo (2007)
clustering_coeff_directed <- function(graph) {
A <- as.matrix(get.adjacency(graph))
S <- A + t(A)
deg <- degree(graph, mode = c("total"))
num <- diag(S %*% S %*% S)
denom <- diag(A %*% A)
denom <- 2 * (deg * (deg - 1) - 2 * denom)
ccd <- mean(num/denom)
return(ccd)
}[1] 0.55010732.1.3 Maximum Modularity wit heuristic Louvain algorithm
- The following computation is based on the paper of Blondel et al. (2008)
ig = macaque
ig_undirected = as.undirected(ig, mode = "collapse")
ig_undirected_community = cluster_louvain(ig_undirected)
sizes(ig_undirected_community)Community sizes
1 2 3
16 14 15 
2.1.4 Summary Statistics of Real_Net_Macaque
ig = macaque
a_01 = vcount(ig)
a_02 = ecount(ig)
a_03 = mean(degree(ig))
a_04 = graph.density(ig)
a_05 = average.path.length(ig)
a_06 = transitivity(ig)
a_07 = clustering_coeff_directed(ig)
a_08 = sizes(cluster_louvain(as.undirected(ig, mode = "collapse")))
a_09 = cluster_louvain(as.undirected(ig, mode = "collapse"))$modularity[1]
statistics_macaque = c(a_01, a_02, a_03, a_04, a_05, a_06, a_07, length(a_08), a_09)
statistics_macaque_df = data.frame(statistics_macaque)
rownames(statistics_macaque_df) = c("vertex", "edge", "mean_degree", "density", "avg_path_length",
"transitivity", "cluster_coeff", "louvain_max_size", "louvain_modularity")
statistics_macaque_df statistics_macaque
vertex 45.0000000
edge 463.0000000
mean_degree 20.5777778
density 0.2338384
avg_path_length 2.1484848
transitivity 0.5187266
cluster_coeff 0.5501073
louvain_max_size 3.0000000
louvain_modularity 0.37504042.1.5 Create a Random Graph with Erdős-Rényi Model
+ 45/45 vertices, from cd82c73:
[1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
[26] 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45+ 463/463 edges from cd82c73:
[1] 1-> 2 1-> 6 1->15 1->17 1->19 1->22 1->31 1->32 1->39 1->43
[11] 2-> 1 2-> 5 2-> 6 2-> 7 2-> 9 2->13 2->20 2->37 2->38 2->39
[21] 3-> 2 3-> 4 3-> 6 3->20 3->21 3->23 3->29 3->37 3->43 4-> 7
[31] 4-> 8 4->10 4->16 4->20 4->24 4->28 4->42 5-> 2 5-> 4 5->11
[41] 5->13 5->16 5->24 5->26 5->31 5->34 5->39 5->41 5->44 6-> 3
[51] 6-> 7 6->21 6->29 6->31 6->38 7-> 1 7-> 2 7-> 3 7-> 6 7->11
[61] 7->13 7->15 7->16 7->20 7->24 7->25 7->31 7->34 7->35 7->41
[71] 8-> 4 8-> 5 8->14 8->16 8->25 8->30 8->33 8->34 8->35 8->38
[81] 9-> 4 9->11 9->12 9->19 9->27 9->28 9->35 9->38 9->43 9->44
[91] 10-> 3 10-> 4 10->45 10->13 10->15 10->17 10->18 10->21 10->22 10->23
+ ... omitted several edgesplot(ERM_sim_net, vertex.label = NA, edge.arrow.size = 0.2, vertex.size = 3.5, main = "Random Graph with Erdos-Rényi Model",
cex.main = 4.5)
2.1.6 Summary of basic statistics for a Random Graph with Erdős-Rényi Model
- Simulation for N = 500
stored_01 = matrix(c(1:4500), ncol = 9) * (-1)
for (kk in 1:500) {
ERM_sim_net = erdos.renyi.game(vcount(ig), ecount(ig), type = "gnm", directed = T)
ig_sim = ERM_sim_net
a_01 = vcount(ig_sim)
a_02 = ecount(ig_sim)
a_03 = mean(degree(ig_sim))
a_04 = graph.density(ig_sim)
a_05 = average.path.length(ig_sim)
a_06 = transitivity(ig_sim)
a_07 = clustering_coeff_directed(ig_sim)
a_08 = sizes(cluster_louvain(as.undirected(ig_sim, mode = "collapse")))
a_09 = cluster_louvain(as.undirected(ig_sim, mode = "collapse"))$modularity[1]
stored_01[kk, ] = c(a_01, a_02, a_03, a_04, a_05, a_06, a_07, length(a_08), a_09)
}
ERM_sim_net_df = data.frame(stored_01)
colnames(ERM_sim_net_df) = c("vertex", "edge", "mean_degree", "density", "avg_path_length",
"transitivity", "cluster_coeff_directed", "louvain_max_size", "louvain_modularity")2.1.7 BoxPlot of the simulation
2.1.8 Conclusion:
para_erm_sim = colMeans(ERM_sim_net_df)
statistic_real_net_against_ERM_sim_net = 100 * (statistics_macaque - para_erm_sim)/statistics_macaque
statistic_real_net_against_ERM_sim_net vertex edge mean_degree
0.00000 0.00000 0.00000
density avg_path_length transitivity
0.00000 14.69083 20.68250
cluster_coeff_directed louvain_max_size louvain_modularity
57.51690 -44.00000 67.13985 - The simulation runs of Random Erdős-Rényi Graph are 500
- The above boxplot is to show the summary statistics of real_net_macaque against sim_net_Erdős_Rényi model
- Since the sim_net_Erdős_Rényi model are generated with fixed vertex and fixed edge , therefore the sim_net_Erdős_Rényi model of mean averages of vertex , edge , mean_degree and graph_density are same as the real_net_macaque. These four statistics(vertex , edge , mean_degree and graph_density) perserves the same degree of distribution of both real_net_macaque and sim_net_Erdős_Rényi model.
- The avg_path_length and transitivity in sim_net_Erdős_Rényi model have very little different from real_net_macaque.
- However, the main differences between the real_net and sim_net are indicated in cluster_coeff, louvain_max_size and louvain_modularity.
2.2 Q5b2
2.2.1 Confguration Model as a null model with degree sequence
stored_02 = matrix(c(1:4500), ncol = 9) * (-1)
for (kk in 1:500) {
sim_degseq_net = sample_degseq(degree(ig))
a_01 = vcount(ig_sim)
a_02 = ecount(ig_sim)
a_03 = mean(degree(ig_sim))
a_04 = graph.density(ig_sim)
a_05 = average.path.length(ig_sim)
a_06 = transitivity(ig_sim)
a_07 = clustering_coeff_directed(ig_sim)
a_08 = sizes(cluster_louvain(as.undirected(ig_sim, mode = "collapse")))
a_09 = cluster_louvain(as.undirected(ig_sim, mode = "collapse"))$modularity[1]
stored_02[kk, ] = c(a_01, a_02, a_03, a_04, a_05, a_06, a_07, length(a_08), a_09)
}
sim_degseq_net_df = data.frame(stored_02)
colnames(sim_degseq_net_df) = c("vertex", "edge", "mean_degree", "density", "avg_path_length",
"transitivity", "cluster_coeff", "louvain_max_size", "louvain_modularity")2.2.2 BoxPlot of the simulation
2.2.3 Conclusion
para_sim_degseq_net = colMeans(sim_degseq_net_df)
statistic_real_net_against_sim_degseq_net = 100 * (statistics_macaque - para_sim_degseq_net)/statistics_macaque
statistic_real_net_against_sim_degseq_net vertex edge mean_degree density
0.00000 0.00000 0.00000 0.00000
avg_path_length transitivity cluster_coeff louvain_max_size
14.40997 18.45235 57.06069 -66.66667
louvain_modularity
69.16865 - The simulation runs of sim_degseq_net are 500
- The above boxplot is to show the summary statistics of real_net_macaque against sim_degseq_net model
- Since the sim_degseq_net are generated with fixed vertex and fixed edge , therefore the sim_degseq_net model of mean averages of vertex , edge , mean_degree and graph_density are same as the real_net_macaque. These four statistics(vertex , edge , mean_degree and graph_density) perserves the same degree of distribution of both real_net_macaque and sim_degseq_net model.
- The avg_path_length and transitivity in sim_degseq_net model have very little different from real_net_macaque.
- However, the main differences between the real_net and sim_net are indicated in cluster_coeff, louvain_max_size and louvain_modularity.
Reference
Blondel, Vincent D, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. “Fast Unfolding of Communities in Large Networks.” Journal of Statistical Mechanics: Theory and Experiment 2008 (10): P10008.
Fagiolo, Giorgio. 2007. “Clustering in Complex Directed Networks.” PRE 76 (2): 026107. https://link.aps.org/doi/10.1103/PhysRevE.76.026107.
Négyessy, László, Tamás Nepusz, László Kocsis, and Fülöp Bazsó. 2006. “Prediction of the Main Cortical Areas and Connections Involved in the Tactile Function of the Visual Cortex by Network Analysis.” European Journal of Neuroscience 23 (7): 1919–30.