---
title: 'SOCI 424/624: Clusters and community detection'
author: '(anonymous for peer evaluation)'
output: html_document
---

```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
# load the 'igraph' package
library(igraph)
```

## Part 1: Working with vertex and edge attributes

### Food webs in the Arctic

The data for this lab represents a [food web](https://en.wikipedia.org/wiki/Food_web)—a description of who eats whom in a particular environment. We'll be looking at a small subset of the data from a 2014 paper by Legagneux et al that studied Arctic ecosystems. Specifically, ours is data from [Nenets Autonomous Okrug in Russia](https://goo.gl/maps/NLuTSV9FJ8rSd8Y37) collected between 1997 and 1999. It's available to download from two files:

* The file `foodweb_vertices.csv` (<https://soci424.netlify.app/data/Nenetsky/foodweb_vertices.csv>) contains information about the different species and genuses in the data .
* The file `foodweb_edges.csv` (<https://soci424.netlify.app/data/Nenetsky/foodweb_edges.csv>) contains information about relation of consumption between the vertices.

### Task 1A: Loading the data

-   *Use R's `read.csv()` function to download the relational data directly from the URLs above. You should name the vertex data frame `vdata` and the edge data frame `edata`.*

```{r 1a_1}
# (your code here)
```

-   *Inspect these data frames visually (either in the console or in RSudio's table viewer). In the space below, write R code to calculate how many types of animals and plants are represented in the data, and how many consumer-resource relations are represented. (In a food web, a consumer is the animal or plant that does the eating, and a resource is the plant or animal that is eaten)*

```{r 1a_2}
# (your code here)
```

Look at the documentation for the `graph_from_data_frame()` function (either by searching for it in the Help panel on the right-hand side of Rstudio or by typing `?graph_from_data_frame` into the console). You will notice that `graph_from_data_frame` takes three "arguments" (inputs): `d` (a data frame of edge information), `directed` (indicating if it should build a directed or an undirected network), and `vertices` (a data frame of vertex information). However, both `directed` and `vertices` have "default" values (`TRUE` and `NULL`), which means that if you don't supply those arguments R will use a default value.

-   *Use `graph_from_data_frame()` to build a single network from these two data frames named `foodnet`. You will need to supply `edata` as the first argument, and you will need to override the default value of `vertices=NULL` with the vertex data (`vertices=vdata`). Use `vcount()` and `ecount()` to calculate the number of vertices and edges in the resulting network.*

```{r 1a_3}
# (your code here)
```

-   *Use the `plot()` function to visualize the network.*

```{r 1a_4}
# (your code here)
```


### Task 1B: Vertex and edge attributes

In the last worksheet we looked a bit at vertex and edge values in igraph, but here we will go more in depth. There are two main categories of data associated with networks: data that describes the individual nodes in a network, and data that describes the relations between nodes in a network. In igraph, these are called _vertex attributes_ and _edge attributes_, respectively.

-   *Use the functions `vertex_attr_names()` and `edge_attr_names()` to list the names of the vertex and edge attributes. How do these compare with the columns (variables) in `vdata` and `edata`?*

```{r 1b_1}
# your code here
```

The `V()` and `E()` functions from igraph are used to access lists of the vertices and of the edges in a network. E.g. `V(foodnet)` returns a list of all of the vertices in the network. But these functions also allow access to the values of the vertex and edge _attributes_ by using a special `$` syntax (similar to using `$` to access variables in a data frame). As an example, to access the values of the `name` vertex attribute you would use `V(foodnet)$name`.

-   *Calculate how many of the species in the food net move around by flying. Calculate how many of the consumer-resource relationships are predacious (rather than herbivorous).*

```{r 1b_2}
# your code here
```

igraph also uses vertex an edge attributes for visualization of the networks. There are a great many of these, affecting the look and style of the vertices and edges. Some useful vertex attributes for plotting are `label`, `color`, and `size`. For edges, the attributes `width`, `color`, and `arrow.size` are often useful.

-   *Set the vertex labels to use the animals' and plants' common names (the `common` attribute). Change the color of the edges so that predacious relations are drawn in `'purple'` and herbivorous relations are drawn in `'dark green'`. Plot the resulting graph.*

```{r 1b_3}
# your code here
```



## Part 2: Community detection
igraph provides a suite of functions that implement different community detection algorithms. As a rule, these functions all have names that start with `cluster_`, and the objects they generate have a common structure. In the next few tasks, you will get familiar with using these functions.

### Task 2A: Maximizing modularity

The `cluster_optimal()` function will find the community structure that maximizes the modularity of a given network. This means it tries out every possible partitioning scheme of the network, and is quite computationally intensive. (Note: since our network is relatively small this will only take a few seconds, but if you have a network with more than a hundred or so vertices this function will be virtually impossible to use).

-   *Run the `cluster_optimal()` function on the `foodnet` network, and store the result in a variable called `clu`. This `clu` object is complex, storing various information about the resulting community structure. Use `clu$modularity` to find the modularity of the partitioning. Use `clu$membership` to list the cluster membership. Looking at the results, how many communities did the function identify?*

```{r 2a_1}
# your code here
```

-   *Set the `color` vertex attribute of `foodnet` to be the numerical cluster listed in `clu`. (Note: if R sees a number where it expects to see a color name, it will use the numbers to choose from a default 'palette'). Plot the results.*

```{r 2a_2}
# your code here
```



### Task 2B: Comparing clustering algorithms

The "Louvain" clustering algorithm tries to approximate the modularity optimization in a more computationally efficient way that can be used on very large networks. However it only works on undirected networks.

-   *Use `cluster_louvain()` to calculate communities using this algorithm, and save the results to a new object called `clu2`. You'll need to create a copy of the `foodnet` network that converts the directed edges into undirected edges using the `as.undirected()` function.*

```{r 2b_1}
# your code here
```

-   *How many communities does `clu2` identify? What is the maximum modularity it achieves? (Note, `clu2$modularity` will return a vector of multiple modularities that the algorithm tried along the way. You can use the `max()` function to find the largest of these.*

```{r 2b_2}
# your code here
```

-   *Create a new plot of the network, this time colored by the Louvain-identified communities. How does this image differ from the fully optimized version from task 2A?*

```{r 2b_3}
# your code here
```


-   ***Bonus question for more experienced R users**: Not every community detection algorithm is concerned with maximizing the modularity measure. Experiment with other algorithms (e.g. `cluster_walktrap()`, which bases communities on random walks through a directed network, or `cluster_infomap()`, which uses information theory to find clusters that 'summarize' the network structure well).*

```{r 2b_4}
# your code here
```



# Discussion:

-   Look at the images you produced in part 2 above. What do they tell you about the ecosystem described by the food web? Do the 'optimal' and Louvain images tell different stories about the ecological structure? Do you think that the clusters we identified here have any significance within the ecosystem (e.g. what does it mean to the red fox that the arctic hare and the shorebirds are in different network clusters)?

  - (your response)

-   Recall that modularity measures the degree to which edges in a network stay within groups and avoid crossing between groups. In the context of a food web like this, what kind of relation do edges represent, and what does a high modularity score indicate? How would an ecological system with a high maximal modularity look different from one with a low maximal modularity?

  - (your response)

-   The food web in this worksheet mirrors the citation network in Shwed and Bearman (2010) in many ways: it is a directed network that tends to have no reciprocated ties and no cycles. Moreover, food webs describe a relation of dependence that could be mapped onto citation relations (papers presumably cite other papers whose findings and methods they rely on). Shwed and Bearman use modularity to describe the level of 'epistemic rivalry' within a scientific community. Do the clusters in the food web describe some sort of 'ecological rivalry'? What characteristics of citation networks and food webs make the interpretation of community structure different in the two cases?

  - (your response)

# References

Legagneux, P., G. Gauthier, N. Lecomte, N. M. Schmidt, D. Reid, M.-C. Cadieux, D. Berteaux, et al. “Arctic Ecosystem Structure and Functioning Shaped by Climate and Herbivore Body Size.” _Nature Climate Change_ 4, no. 5 (May 2014): 379–83. <https://doi.org/10.1038/nclimate2168>.

Shwed, Uri, and Peter S. Bearman. “The Temporal Structure of Scientific Consensus Formation.” _American Sociological Review_ 75, no. 6 (December 2010): 817–40. https://doi.org/10.1177/0003122410388488.

