---
title: "Agrupamento em grafos"
output: html_notebook
---

O modelo de Erdos-Renyi gera aleatoriamente um grafo cujas arestas entre dois vértices tem probabilidade constante de existir. É um grafo denso com pouco agrupamento local (transitividade).

```{r}
require(igraph)

grafo_erdos <- erdos.renyi.game(40,.5,type="gnp",directed = FALSE)
plot(grafo_erdos)
average.path.length(grafo_erdos)
transitivity(grafo_erdos, "average")
```

O modelo de Watts-Strogatz gera aleatoriamente um grafo que representa ``mundos pequenos``, ou seja, alto agrupamento e caminhos com comprimento médio pequeno.

```{r}
require(igraph)

grafo_mundo_pequeno <- watts.strogatz.game(dim=2,size=10,nei=5,0.4)
plot(grafo_mundo_pequeno)
average.path.length(grafo_mundo_pequeno)
transitivity(grafo_mundo_pequeno,"average")
```

O modelo de Barabasi-Albert gera aleatoriamente um grafo que representa redes comuns do comportamento humano, por exemplo, a Internet e redes sociais. Nesses grafos, vértices com grau maior tem maior probabilidade de se conectar a outros vértices. Além disso, a distribuição de probabilidade dos graus dos vértices é exponencial, ou seja a probabilidade de um vértice ter grau $k$ decai exponencialmente com um parâmetro $\gamma$ da seguinte forma $P(k) ~  k ^{-\gamma}$.
O comprimento médio de caminhos tende a ser baixo.

```{r}
require(igraph)

grafo_barabasi <- barabasi.game(n=100, power =.8)
plot(grafo_barabasi)
average.path.length(grafo_barabasi)
transitivity(grafo_barabasi,"average")
degree_distribution(grafo_barabasi)
```

É possível agrupar grafos distintos e buscar grupo dentro de grafos.

Por exemplo, a seguir fazemos uma hierarquia de agrupamento de grafos.

```{r}
require(statGraph)

g <- list()
for (i in 1:5) {
    g[[i]] <- as.matrix(get.adjacency(
                        erdos.renyi.game(50, 0.5, type="gnp",
                                         directed = FALSE)))
}
for (i in 6:10) {
    g[[i]] <- as.matrix(get.adjacency(
                        watts.strogatz.game(1, 50, 8, 0.2)))
}
for (i in 11:15) {
    g[[i]] <- as.matrix(get.adjacency(
                        barabasi.game(50, power = 1,
                                      directed = FALSE)))
}
graph.cluster(g, 3)

     
```


Um grupo social pode ser uma "panelinha" ou, em inglês, um clique:

```{r}
cliques(grafo_erdos, min=8)
```



Também é possível agrupar nós de um grafo usando agrupamento espectral:

```{r}
library(anocva)

arvore = igraph::make_tree(80, children = 4, mode = "undirected")

plot(arvore, vertex.size = 10, vertex.label = NA)

adjacencias = as.matrix(igraph::get.adjacency(treeGraph))

grupos = spectralClustering(adj, 4)

plot(arvore, vertex.size=10, vertex.color = grupos, vertex.label = NA)

```

