#### Measuring node importance

What are the most important nodes in a network? What is the propensity of two nodes that are connected to be both connected to a third node? What are the different hidden communities in a network? These are some of the descriptive questions that we will adress now.

This time, we will analyze a network from a different book -- ``A Storm of Words'', the third book in the Song of Ice and Fire series by George R.R. Martin. The source of this dataset is this [blog post](https://www.macalester.edu/~abeverid/thrones.html). Each character in the book will be a different nodes. Each edge between two characters indicates their names appeared within 15 words of one another in the text of the book.

```{r, echo=FALSE, message=FALSE}
library(igraph)
edges <- read.csv("../data/GOT-edges.csv", stringsAsFactors=F)
g <- graph_from_data_frame(d=edges, directed=FALSE)
```

#### Node properties

We'll start with descriptive statistics at the node level. All of these are in some way measures of importance or __centrality__.

The most basic measure is __degree__, the number of adjacent edges to each node. It is often considered a measure of direct influence. In this network, it will be the total number of times each user co-appears with someone else.

```{r}
sort(degree(g))
```

In directed graphs, there are three types of degree: indegree (incoming edges), outdegree (outgoing edges), and total degree. You can compute these using `mode="in"` or `mode="out"` or `mode="total"`. 

```{r}
tail(sort(degree(g, mode="in")))
tail(sort(degree(g, mode="out")))
```

Here they will be identical because the network is undirected.

__Closeness__ measures how many steps are required to access every other node from a given node. It's a measure of how long information takes to arrive (who hears news first?), or how easily a node can reach other nodes. Higher values mean less centrality.

```{r}
head(sort(closeness(g, normalized=TRUE)))
```

__Betweenness__ measures brokerage or gatekeeping potential. It is (approximately) the number of shortest paths between nodes that pass through a particular node. It defines the importance of a node is in terms of how frequently it connects other nodes.

```{r}
tail(sort(betweenness(g)))
```

#### Network properties

Let's now try to describe what a network looks like as a whole. An important measure is `edge_density` -- the proportion of edges in the network over all possible edges that could exist.

```{r}
edge_density(g)
```

`reciprocity` measures the propensity of each edge to be a mutual edge; that is, the probability that if `i` is connected to `j`, `j` is also connected to `i`.

```{r}
reciprocity(g)
```

Why is it 1?

`transitivity`, also known as clustering coefficient, measures that probability that adjacent nodes of a network are connected. In other words, if `i` is connected to `j`, and `j` is connected to `k`, what is the probability that `i` is also connected to `k`?

```{r}
transitivity(g)
```

#### Network communities

Networks often have different clusters or communities of nodes that are more densely connected to each other than to the rest of the network. The goal of __community detection algorithms__ is to identify these subsets.

There are a few different algorithms, each following a different logic: walktrap algorith, infomap, fast and greedy, edge-betweenness, label propagation... Exploring each of these goes beyond the scope of this course, but you can read the documentation for more details.

My experience is that infomap tends to work better in most social science examples (websites, social media, classrooms, etc), so we'll go along with it just to take a look at the output

```{r}
comm <- cluster_infomap(g)
# let's look at some of the small ones first...
comm[[4]]
comm[[5]]
comm[[6]]
comm[[7]]
# now back to the large ones
comm[[1]]
comm[[2]]
comm[[3]]

```

The final way in which we can think about network communities is in terms of hierarchy or structure. We'll discuss one of these methods.

__K-core decomposition__ allows us to identify the core and the periphery of the network. A k-core is a maximal subnet of a network such that all nodes have at least degree K.

```{r, fig.height=5, figh.width=6}
coreness(g)
table(coreness(g))
which(coreness(g)==7) # what is the core of the network?

# let's plot the core of the network...
core <- induced_subgraph(g, v=which(coreness(g)==7))
plot(core)
```
