2 Measuring modularity

Alessandro Vindigni and Daniel Wechsler
session 17/03/2023

2.1 Plotting networks

For this exercise we will be using the igraph library.

# Import the required libraries
library(igraph)
library(dplyr)
library(rjson) 
library(bipartite)
library(formattable)

Now we will download a network from Web of life and create a bipartite igraph object from it (see session Toolkit for network analysis):

# download the M_PA_002 network from the web-of-life API 
json_url <- paste0("https://www.web-of-life.es/get_networks.php?network_name=M_PA_002")
M_PA_002_nw <- jsonlite::fromJSON(json_url)

# select the 3 relevant columns and create the igraph object 
M_PA_002_graph <- M_PA_002_nw %>% select(species1, species2, connection_strength) %>% 
  graph_from_data_frame(directed = FALSE)
# get info about species 
my_info <- read.csv(paste0(base_url,"get_species_info.php?network_name=M_PA_002"))

isResource <- my_info$is.resource %>% as.logical() # 0/1 converted to FALSE/TRUE

# Add the "type" attribute to the vertices of the graph 
V(M_PA_002_graph)$type <- !(isResource)

You can access object information using $:

V(M_PA_002_graph) # to see the vertices (nodes) names = species

## + 10/10 vertices, named, from f8168d5:
##  [1] Cecropia ficifolia    Cecropia membranacea  Cecropia engleriana  
##  [4] Cecropia polystachya  Cecropia tessmannii   Cecropia sp1 M_PA_002
##  [7] Azteca xanthochroa    Camponotus balzani    Azteca ovaticeps     
## [10] Pachycondyla luteola

E(M_PA_002_graph) # to see the edges (pairwise interactions)

## + 13/13 edges from f8168d5 (vertex names):
##  [1] Cecropia ficifolia   --Azteca xanthochroa  
##  [2] Cecropia ficifolia   --Camponotus balzani  
##  [3] Cecropia membranacea --Azteca ovaticeps    
##  [4] Cecropia membranacea --Azteca xanthochroa  
##  [5] Cecropia membranacea --Camponotus balzani  
##  [6] Cecropia engleriana  --Azteca ovaticeps    
##  [7] Cecropia engleriana  --Azteca xanthochroa  
##  [8] Cecropia polystachya --Azteca ovaticeps    
##  [9] Cecropia polystachya --Azteca xanthochroa  
## [10] Cecropia polystachya --Camponotus balzani  
## + ... omitted several edges

Since this is a bipartite network, let’s create the incidence matrix and use the bipartite() package to plot it

# convert the igraph object into incidence matrix 
inc_matrix <- as_incidence_matrix(
  M_PA_002_graph,
  attr = "connection_strength",
  names = TRUE,
  sparse = FALSE
)
# convert elements into numeric values and remove NA
class(inc_matrix) <-"numeric"
inc_matrix[which(is.na(inc_matrix) == T)]<-0
# plot using bipartite
plotweb(inc_matrix, 
        method="normal", text.rot=90, 
        bor.col.interaction="gray40",plot.axes=F, col.high="blue", labsize=1, 
        col.low="darkgreen", y.lim=c(-1,3), low.lablength=40, high.lablength=40)

2.2 Computing Modularity

Now that we have the igraph object let’s compute modularity. Sometimes the user may have a pre-defined node partitioning. If that is the case, we can manually define the modules if you already know which module which species belongs to.

# Manually define partitioning
membership = c(1,2,2,2,3,2,1,3,2,2)
# Compute modularity of partitioning
Q <- modularity(M_PA_002_graph, membership)
Q

## [1] 0.00887574

We can also color the nodes according to the modules and plot the graph

# Color the nodes according to the modules
colbar <- rainbow(max(membership))
V(M_PA_002_graph)$color <- colbar[membership]

# Plot the graph
plot(M_PA_002_graph, layout=layout_with_fr, margin=0.0)

2.3 Computing Detection

Some community detection algorithms available in igraph are:

cluster_label_prop
cluster_edge_betweenness
cluster_fast_greedy
cluster_leading_eigen
cluster_optimal (SLOW!!)

Instead of having a predetermined idea of to which module each species belongs to, it is much more common to find the best partitioning of the nodes using one of the available community detection algorithms. Let us use the fast greedy algorithm:

modules <- cluster_fast_greedy(M_PA_002_graph)
modules$membership # looking at the result

##  [1] 2 1 1 1 2 1 1 2 1 2

Let’s get the modularity of the best partitioning.

M <- modularity(modules)
M

## [1] 0.2218935

Again, we can now color the nodes of our graph according the module they belong to.

colbar <- rainbow(max(modules$membership))
V(M_PA_002_graph)$color <- colbar[modules$membership]

plot(M_PA_002_graph, 
     layout=layout_with_fr, 
     vertex.size=12, 
    #vertex.label=NA,
     margin=0.0)

This layout makes much more sense!

2.4 Exercises

To submit the assignment you can use a similar template as the one provided during the first exercise session. For the exercises on paper, please take a picture of your work and upload it to OLAT along with your submission.

Exercise 1

For the graph drawn below do the following:

Write down the degree of each node.
Compute the adjacency matrix.

Hint: You can either solve this exercise on paper or use the following template to fill the matrix and copy it into your R script in the workspace.

$$
\\A = \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix}
$$

which is rendered in RMarkdown as \[ \\A = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ \end{bmatrix} \]

adj_matrix <- matrix(c(0,0,1,0,1,0,0,0,0,1,1,0,1,0,0,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,0,0,1,1,1,0),nrow=6,ncol=6)
graph <- graph_from_adjacency_matrix(adj_matrix,mode="undirected")

# PLot network using bipartite layout
plot(graph,
     vertex.size = 8,
     vertex.label.color = 'black',
     vertex.color = 'orange',
     margin = 0.0,
     asp = 0.5)

Exercise 2

Draw the graph represented by the following adjacency matrix (on paper):

\[ \\A = \begin{bmatrix} 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ \end{bmatrix} \]

Exercise 3

The node colors of the graph below represent a partitioning of the nodes into three modules.

Use the formula given in the lecture on foodwebs to compute the modularity Q associated with the partition (on paper).
Check your answer using R (on the R script in the workspace).
Do you think the given node partitioning is the best, i.e. it optimizes Q (argue)?

HINT:

adj_matrix <- matrix(c(0, ... ,0),nrow=7,ncol=7)
graph <- graph_from_adjacency_matrix(adj_matrix,mode="undirected")

plot(graph, 
     layout=layout_with_fr, 
     vertex.size=12, 
     vertex.label=NA,
     margin=0.0)

Exercise 4

Download the network named M_SD_001 from Web of life using the usual sequence of commands, create an igraph object, and:

Use the community detection algorithm cluster_louvain() to compute the optimal partitioning of nodes (modules) for that network.
Compute the modularity M.
Plot the network coloring the nodes according to the modules they belong to and try to find the layout that better highlights communities.

Hint: To obtain a cleaner result, we recommend to remove the vertices names

plot(M_SD_001_graph, 
     layout = layout_on_sphere, 
     vertex.size = 10, 
     vertex.label = NA,
     margin=0.0)

You can then play with the size of nodes and with the layouts; a partial list of the last few is: layout_nicely, layout_with_kk, layout_randomly, layout_in_circle, layout_with_fr,layout_as_tree, layout_on_grid, layout_with_dh, layout_with_graphopt, layout_with_lgl, layout_with_mds, layout_with_sugiyama.