<jupyter_start><jupyter_text>Random networks This notebook contains additional material about random graphs. The aim is to introduce a few simple random realisations of graphs that can serve as null model for comparison against measures of the network observed in the data. We will use previously introduced libraries: *igraph* (to generate and analyze networks) and *ggplot2* (to visualize results).<jupyter_code>library(igraph)
library(ggplot2)<jupyter_output><empty_output><jupyter_text>Set the seed to make sure the results below are reproducible:<jupyter_code>seed <- 612<jupyter_output><empty_output><jupyter_text>To illustrate the usefulness of random networks, we will focus on a single previously analyzed network - friendship network. We first load it and remind ourselves of its size using ```summary```:<jupyter_code>data_dir = "output/lab1/"
krack_friendship <- readRDS(paste0(data_dir, "krack_friendship.RData"))
summary(krack_friendship)<jupyter_output>IGRAPH 6f85218 DN-- 21 102 -- 
+ attr: AGE (v/n), TENURE (v/n), LEVEL (v/n), DEPT (v/n), name (v/n)<jupyter_text>Discussed ideas can be applied to directed networks as well, but it is more illustrative and clear if we work with undirected networks first, so let's create an undirected friendship network:<jupyter_code>krack_friendship_undirect <- as.undirected(krack_friendship, 
                                           mode = "collapse") #try also with mode = 'mutual' that will create even less links
summary(krack_friendship_undirect)<jupyter_output>IGRAPH fc2f4d3 UN-- 21 79 -- 
+ attr: AGE (v/n), TENURE (v/n), LEVEL (v/n), DEPT (v/n), name (v/n)<jupyter_text>As noted in our previous analysis, this reduces the number of links (as links from A to B and from B to A will be collapsed into a single undirected link between A and B). We will plot networks a few times below, so let's make a simple plotting function for those purposes:<jupyter_code>plot_graph <- function(g, title) {
  plot(g, 
       layout=layout_nicely(g),
       vertex.size = 1.5 * degree(g),
       vertex.label.cex	= 0.15 * degree(g),
       main=title)
}<jupyter_output><empty_output><jupyter_text>Let's try the function and plot the undirected friendship network:<jupyter_code>plot_graph(krack_friendship_undirect,'Friendship network')<jupyter_output><empty_output><jupyter_text>No surprises here, we've seen this network previously. Now, we want to see how this network compares to a randomly generated network.   Random graphs with the preserved average degree *igraph* has a few network generative functions and among them Erdos Renyi random graphs that we will use first. As usual, you can first inspect documentation of the function:<jupyter_code>?erdos.renyi.game<jupyter_output><empty_output><jupyter_text>Besides the number of nodes, the key arguments are either the exact number of links we expect (in which case besides the number of links, we should pass the argument *type = 'gnm'* to the function) or the probability that the link is created between two randomly samples nodes (in which case besides probability, we pass arg *type = 'gnp'*). Let's try first 'gnm' type of random network:<jupyter_code>random_net_gnm = erdos.renyi.game(vcount(krack_friendship_undirect), ecount(krack_friendship_undirect),type='gnm')
summary(random_net_gnm)<jupyter_output>IGRAPH 13c8ceb U--- 21 79 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)<jupyter_text>As we wanted, it has the same number of nodes and edges as the friendship network (that we enforced passing vcount and ecount values as arguments of the ```erdos.renyi.game``` function. Let's plot it to see if we can observe some differences:<jupyter_code>plot_graph(random_net_gnm,'Random network GNM type')<jupyter_output><empty_output><jupyter_text>Already visually we can note that the node with the most neighbours changed, and its number of neighbours is different than max degree before (compare the largest node circles above and here).We can repeat the process and create a few more realisation of this network:<jupyter_code>set.seed(seed)
random_net_gnm = erdos.renyi.game(vcount(krack_friendship_undirect), ecount(krack_friendship_undirect),type='gnm')
plot_graph(random_net_gnm,'Random network GNM type')<jupyter_output><empty_output><jupyter_text>Note: even after a few reruns, we see that a node that has only 2 friends (that exist in our original network) occurs rarely in the random realisations. The average degree is exactly the same between *krack_friendship_undirect* and *random_net_gnm* networks (by construction), but other summary statistics such as median, standard deviation, etc, are not (check this out for yourselves):<jupyter_code>mean(degree(krack_friendship_undirect))
#sd(degree(krack_friendship_undirect))
mean(degree(random_net_gnm))
#sd(degree(random_net_gnm))<jupyter_output><empty_output><jupyter_text>Another possible random network realisation assumes that we relax requirement on the number of links. Instead of requiring a network with exactly N nodes and L links, we create a random network whose expected value of links is L, but in any single random network realisation, it can be slightly above or below L. We can do this using the 'gnp' option of ```erdos.renyi.game``` and using parameter p, or probability that there is a link between two nodes whose value is the density of the original graph:<jupyter_code>n = vcount(krack_friendship_undirect)
l = ecount(krack_friendship_undirect)
p = l/(0.5*n*(n-1))<jupyter_output><empty_output><jupyter_text>Let's create this new random network and visualize it:<jupyter_code>set.seed(seed)
random_net_gnp = erdos.renyi.game(n, p, type='gnp')
summary(random_net_gnp)
plot_graph(random_net_gnp,'Random network GNP type')<jupyter_output>IGRAPH 3878cb8 U--- 21 75 -- Erdos renyi (gnp) graph
+ attr: name (g/c), type (g/c), loops (g/l), p (g/n)<jupyter_text>Running the previous block of code several times (comment seed command), you can note the variability in the number of links and visually note graph differences. Now, as the number of links is often smaller than in the original graph, there are situations where some nodes have only two connections (the situation we've observed in the original network), but still, nodes with most connections have fewer connections than the most popular node in the original network.Let's have a look at the degree distributions. We first create a dataframe containing the data, and then we plot the distributions using histograms as before.<jupyter_code>network_data <- data.frame(
  network_type = c( rep("friendship", n), rep("random_gnm", n), rep("random_gnp", n) ),
  degree_values = c( degree(krack_friendship_undirect), degree(random_net_gnm), degree(random_net_gnp) )
)
head(network_data)<jupyter_output><empty_output><jupyter_text>Similarly to the codes in previous labs, we now proceed to plot a histogram where we display degree distributions for all networks.<jupyter_code>max_degree <- max(network_data$degree_values)
min_degree <- min(network_data$degree_values)

ggplot(network_data, 
       mapping = aes(x = degree_values, fill = network_type)) +
  geom_histogram(binwidth = 1, 
                 position = position_identity(),
                 #position = position_dodge(),
                 alpha=0.5) +
  scale_x_continuous(breaks = seq(min_degree,max_degree,2)) +
  theme_minimal() +
  labs(x = "Degree value", title = "Degree distributions for the Friendship network and random controls")<jupyter_output><empty_output><jupyter_text>In this plot we have a confirmation of our previous observation - original friendship network has nodes with the greater and fewer degree. Similarly, we can calculate clustering coefficient (using ```transitivity``` function) of each node and look at histograms those values.<jupyter_code>network_data$clustering_values = c( transitivity(krack_friendship_undirect,type='local'), 
                                   transitivity(random_net_gnm,type='local'), 
                                   transitivity(random_net_gnp,type='local'))
tail(network_data)<jupyter_output><empty_output><jupyter_text>And this we can also plot using histograms to compare among three random variations:<jupyter_code>ggplot(network_data, 
       mapping = aes(x = clustering_values, fill = network_type)) +
  geom_histogram(binwidth = 0.05, 
                 position = position_identity(), 
                 alpha=0.5) +
  theme_minimal()<jupyter_output><empty_output><jupyter_text>We observe that in the real friendship network there is a node with maximal clustering coefficient and that in general, clustering coefficient in the real friendship network is higher than in its random realisations. Let's see if that is visible in the summary statistics such as mean:<jupyter_code>mean(transitivity(krack_friendship_undirect,type='local'))
mean(transitivity(random_net_gnm,type='local'))
mean(transitivity(random_net_gnp,type='local'))<jupyter_output><empty_output><jupyter_text>We see that mean local transitivity is higher in real than in the two random networks. Maybe, that is due to just this random realisation we've created and we analyse?To check if that is the case, we can repeat the previous process multiple times and see if we can obtain the clustering coefficient observed in the friendship network.1. we create a random network2. calculate local transitivity for every node3. calculate the mean value within the network4. repeat 1-3 We will write this as a function to make it easily applicable for the different network (and easily adaptable if you choose to investigate other properties besides clustering coefficient):<jupyter_code>transitivity_random_graphs <- function(g, number_repetitions) {
    n = vcount(g)
    l = ecount(g)
    p = l/(0.5*n*(n-1)) 
    
    random_data = array(0,dim=number_repetitions) #empty array to store data from random realisation calculations
    
    for (i in 1:number_repetitions) {
        
        # choose one of random network realisation types:
        random_net = erdos.renyi.game(n, l,type='gnm')
        #random_net = erdos.renyi.game(n, p,type='gnp')
        
        # here we store mean transitivity data for every generated network, you can calculate any other random network value by changing this line (eg. sd of degrees, mean shortest path,...)
        random_data[i] = mean(transitivity(random_net,type='local'))
    }
    return(random_data)
}<jupyter_output><empty_output><jupyter_text>Let's run this function and calculate local transitivity for 100 different random networks. We will store the function return value in variable *random_clustering*:<jupyter_code>set.seed(seed)
random_clustering = transitivity_random_graphs(krack_friendship_undirect,100)<jupyter_output><empty_output><jupyter_text>Now, we compare the mean local transitivity found in the friendship network to different mean local transitivities found in the random networks:<jupyter_code>hist(random_clustering,xlim = (0:1))
abline(v= mean(transitivity(krack_friendship_undirect,type='local')), col="red")<jupyter_output><empty_output><jupyter_text>We see that the mean local transitivity is higher in friendship network than in any of the 100 random realisations of networks with the same number of links and nodes (it's similar when L is not fixed but when 'gnp' random nets are used - try!).  Random graphs with preserved degree sequence What if we don't preserve only the average degree in a network but the full sequence of node degrees? This way we take into account node variability (e.g. not everyone is equally friendly) but we still aim to investigate if other network properties (such as other node's centrality measures or transitivity, or paths) are special in our observed network compared to random controls.To create a random graph that preserves degree sequence, we use another built-in functions ```sample_degseq```:<jupyter_code>?sample_degseq
set.seed(seed)
rewired_net = sample_degseq(degree(krack_friendship_undirect), method="vl")
summary(rewired_net)<jupyter_output>IGRAPH 4f57472 U--- 21 79 -- Degree sequence random graph
+ attr: name (g/c), method (g/c)<jupyter_text>As we fixed the degrees for each node, the total number of edges matches the original network. Let's see how this network looks like:<jupyter_code>plot_graph(rewired_net,'Rewired network preserving degree sequence')<jupyter_output><empty_output><jupyter_text>As we preserved degree sequence, all node sizes match the original network plot, but some edges are rewired (can you find some?). For this network, we can calculate degree and local transitivity and compare them to previously discussed networks. We add these values in their own data frame:<jupyter_code>rewired_data <- data.frame(
    network_type = c( rep("rewired_degseq_preserved", n)),
    degree_values = c(degree(rewired_net)),
    clustering_values = c(transitivity(rewired_net,type='local'))
)
head(rewired_data)<jupyter_output><empty_output><jupyter_text>And add this dataframe as extra rows to the *network_data* that already contains data for previously discussed networks:<jupyter_code>network_data <- rbind(network_data,rewired_data)
tail(network_data)<jupyter_output><empty_output><jupyter_text>We can plot degree distributions:<jupyter_code>max_degree <- max(network_data$degree_values)
min_degree <- min(network_data$degree_values)

ggplot(network_data, 
       mapping = aes(x = degree_values, fill = network_type)) +
  geom_histogram(binwidth = 1, 
                 position = position_identity(), 
                 #position = position_dodge(),
                 alpha=0.5) +
  scale_x_continuous(breaks = seq(min_degree,max_degree,2)) +
  theme_minimal()<jupyter_output><empty_output><jupyter_text>But as expected, that doesn't reveal anything special as degree sequence is preserved, so the plots of rewired network and original network fully overlap. Let's see if the situation is the same when we plot the clustering coefficient:<jupyter_code>ggplot(network_data, 
       mapping = aes(x = clustering_values, fill = network_type)) +
  geom_histogram(binwidth = 0.05, 
                 position = position_identity(), 
                 #position = position_dodge(),
                 alpha=0.5) +
  theme_minimal()<jupyter_output><empty_output><jupyter_text>Now, we see that local transitivities in the rewired network are more similar to those in the original friendship network, but there is still some variability. Let's repeat the process multiple times and see if transitivity can be explained by local variability in degrees:<jupyter_code>set.seed(seed)
number_repetitions = 100
degseq = degree(krack_friendship_undirect)

random_clustering_rewired = array(0,dim=number_repetitions)
for (i in 1:number_repetitions) {
    rewired_net = sample_degseq(degseq, method="vl")
    random_clustering_rewired[i] = mean(transitivity(rewired_net,type='local'))
}
hist(random_clustering_rewired,xlim = (0:1))
abline(v= mean(transitivity(krack_friendship_undirect,type='local')), col="red")
sum(random_clustering_rewired < mean(transitivity(krack_friendship_undirect,type='local')))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08035714285714286, 'fraction_numerical': 0.007076719576719577, 'mean_word_length': 5.434468085106383, 'pattern_counts': {'":': 0, '<': 121, '<?xml version=': 0, '>': 108, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '28', 'dir': 'jupyter-structured-clean-dedup', 'id': '287310', 'license': 'MIT', 'n_tokens_mistral': 4547, 'n_tokens_neox': 4300, 'n_words': 1567, 'path': 'SNA_Labs/lab_random_nets_R_jupyter_notebook.ipynb', 'repo_name': 'SaskaAloric/SNA2020', 'size': '15120'}