1 Introdução

Este tutorial tem como objetivo demonstrar como criar grafos a partir de uma matriz de similaridade no contexto da classificação multirrótulo. Neste tutorial, a matriz de similaridade usada foi calculada usando apenas o espaço de rótulos do dataset multirrótulo. Isto significa que foi calculada a similaridade entre os pares de rotulos.

Se um dataset tem 4 rótulos, então obtém-se 16 pares de rótulos. Como consequência a matriz de similariade terá tamanho 4 x 4 e em cada uma das 16 posições da matriz estarão os valores calculados para cada par.

Um grafo é composto por um conjunto de vértices e arestas. Transpondo isto para o contexto deste tutorial, temos que os vértices são os rótulos do espaço de rótulos, e as arestas são as similaridades calculadas entre cada par de rótulos, algo como o exemplo abaixo:

v_origem = c("rotulo1", "rotulo1", "rotulo2", "rotulo2")
v_destino = c("rotulo1", "rotulo2","rotulo1", "rotulo2")
aresta = c(1.0, 0.5, 0.6, 1.0)
peso = c(0.2, 1.0, 0.3, 0.8)
df_grafo = data.frame(v_origem, v_destino, aresta, peso)
df_grafo
##   v_origem v_destino aresta peso
## 1  rotulo1   rotulo1    1.0  0.2
## 2  rotulo1   rotulo2    0.5  1.0
## 3  rotulo2   rotulo1    0.6  0.3
## 4  rotulo2   rotulo2    1.0  0.8

1.1 Pacotes necessários

# workspace directory
setwd("~/Hands-On-Igraph-R")

library(igraph)
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
library(tidyr)
## 
## Attaching package: 'tidyr'
## The following object is masked from 'package:igraph':
## 
##     crossing
library(plyr)
library(dplyr)
## 
## Attaching package: 'dplyr'
## The following objects are masked from 'package:plyr':
## 
##     arrange, count, desc, failwith, id, mutate, rename, summarise,
##     summarize
## The following objects are masked from 'package:igraph':
## 
##     as_data_frame, groups, union
## The following objects are masked from 'package:stats':
## 
##     filter, lag
## The following objects are masked from 'package:base':
## 
##     intersect, setdiff, setequal, union

2 Construindo o data frame

Existe uma forma correta de data frame que deve ser usado para construir o grafo. Ele é composto de quatro colunas: vértice de origem, vértice de destino e valor da aresta. É este data frame que vamos aprender construir neste tutorial.

2.1 Obtendo os rótulos originais

Para cada dataset que trabalho, eu separo os rótulos originais em um arquivo “csv”. Desta foram eu uso estes nomes em todas as manipulações de rótulos que preciso fazer no meu código. Esta é uma forma de garantir que outras funções não alterem os nomes das colunas, como por exemplo, substituir pontos por traços, ou algo do tipo. Aqui vou utilizar o dataset BIRDS que possui 19 rótulos.

names_labes = read.csv("~/Hands-On-Igraph-R/data/birds-dataset/NamesLabels/birds-NamesLabels.csv")
names_labes
##     N                    Labels
## 1   1             Brown.Creeper
## 2   2              Pacific.Wren
## 3   3  Pacific.slope.Flycatcher
## 4   4     Red.breasted.Nuthatch
## 5   5           Dark.eyed.Junco
## 6   6    Olive.sided.Flycatcher
## 7   7             Hermit.Thrush
## 8   8 Chestnut.backed.Chickadee
## 9   9             Varied.Thrush
## 10 10            Hermit.Warbler
## 11 11         Swainson.s.Thrush
## 12 12      Hammond.s.Flycatcher
## 13 13           Western.Tanager
## 14 14     Black.headed.Grosbeak
## 15 15    Golden.Crowned.Kinglet
## 16 16            Warbling.Vireo
## 17 17    MacGillivray.s.Warbler
## 18 18             Stellar.s.Jay
## 19 19          Common.Nighthawk

2.2 Obtendo as similaridades

Como as medidas de similaridades já foram calculadas, então, basta abrir os arquivos csvs.

# abrindo o arquivo
df_jaccard = read.csv("~/Hands-On-Igraph-R/data/birds-similarities/Split-1/jaccard-2.csv")
head(df_jaccard)
##                          X Brown.Creeper Pacific.Wren Pacific.slope.Flycatcher
## 1            Brown.Creeper    1.00000000   0.00000000               0.04255319
## 2             Pacific.Wren    0.00000000   1.00000000               0.10752688
## 3 Pacific.slope.Flycatcher    0.04255319   0.10752688               1.00000000
## 4    Red.breasted.Nuthatch    0.00000000   0.00000000               0.04651163
## 5          Dark.eyed.Junco    0.00000000   0.00000000               0.03846154
## 6   Olive.sided.Flycatcher    0.04545455   0.02666667               0.04166667
##   Red.breasted.Nuthatch Dark.eyed.Junco Olive.sided.Flycatcher Hermit.Thrush
## 1            0.00000000      0.00000000             0.04545455   0.000000000
## 2            0.00000000      0.00000000             0.02666667   0.009708738
## 3            0.04651163      0.03846154             0.04166667   0.054794521
## 4            1.00000000      0.00000000             0.05555556   0.000000000
## 5            0.00000000      1.00000000             0.00000000   0.122448980
## 6            0.05555556      0.00000000             1.00000000   0.085106383
##   Chestnut.backed.Chickadee Varied.Thrush Hermit.Warbler Swainson.s.Thrush
## 1                0.07500000    0.05263158     0.05882353        0.00000000
## 2                0.04301075    0.04587156     0.04854369        0.12121212
## 3                0.07692308    0.14473684     0.06578947        0.09009009
## 4                0.05405405    0.03703704     0.00000000        0.00000000
## 5                0.04347826    0.08333333     0.05357143        0.10000000
## 6                0.02325581    0.01666667     0.05769231        0.04395604
##   Hammond.s.Flycatcher Western.Tanager Black.headed.Grosbeak
## 1           0.00000000      0.00000000                     0
## 2           0.17333333      0.10843373                     0
## 3           0.03389831      0.00000000                     0
## 4           0.00000000      0.00000000                     0
## 5           0.02631579      0.02380952                     0
## 6           0.00000000      0.11428571                     0
##   Golden.Crowned.Kinglet Warbling.Vireo MacGillivray.s.Warbler Stellar.s.Jay
## 1             0.02500000     0.00000000                      0    0.00000000
## 2             0.02150538     0.00000000                      0    0.02816901
## 3             0.07936508     0.01960784                      0    0.00000000
## 4             0.00000000     0.00000000                      0    0.00000000
## 5             0.04545455     0.07142857                      0    0.00000000
## 6             0.00000000     0.00000000                      0    0.00000000
##   Common.Nighthawk
## 1       0.00000000
## 2       0.01176471
## 3       0.00000000
## 4       0.00000000
## 5       0.00000000
## 6       0.00000000

Quando abrimos o arquivos, notaremos que a primeira coluna contem os nomes dos rótulos. O ideal é que as linhas do data frame contenham esses nomes e esta primeira coluna seja apagada. Assim, as colunas e linhas do data frame ficam nomeadas corretamente e o conteúdo do data frame será composto apenas pelos valores das similaridades.

# nomeando as linhas
rownames(df_jaccard) = df_jaccard$X   

# apagando a primeira coluna
df_jaccard = df_jaccard[,-1]          
head(df_jaccard)
##                          Brown.Creeper Pacific.Wren Pacific.slope.Flycatcher
## Brown.Creeper               1.00000000   0.00000000               0.04255319
## Pacific.Wren                0.00000000   1.00000000               0.10752688
## Pacific.slope.Flycatcher    0.04255319   0.10752688               1.00000000
## Red.breasted.Nuthatch       0.00000000   0.00000000               0.04651163
## Dark.eyed.Junco             0.00000000   0.00000000               0.03846154
## Olive.sided.Flycatcher      0.04545455   0.02666667               0.04166667
##                          Red.breasted.Nuthatch Dark.eyed.Junco
## Brown.Creeper                       0.00000000      0.00000000
## Pacific.Wren                        0.00000000      0.00000000
## Pacific.slope.Flycatcher            0.04651163      0.03846154
## Red.breasted.Nuthatch               1.00000000      0.00000000
## Dark.eyed.Junco                     0.00000000      1.00000000
## Olive.sided.Flycatcher              0.05555556      0.00000000
##                          Olive.sided.Flycatcher Hermit.Thrush
## Brown.Creeper                        0.04545455   0.000000000
## Pacific.Wren                         0.02666667   0.009708738
## Pacific.slope.Flycatcher             0.04166667   0.054794521
## Red.breasted.Nuthatch                0.05555556   0.000000000
## Dark.eyed.Junco                      0.00000000   0.122448980
## Olive.sided.Flycatcher               1.00000000   0.085106383
##                          Chestnut.backed.Chickadee Varied.Thrush Hermit.Warbler
## Brown.Creeper                           0.07500000    0.05263158     0.05882353
## Pacific.Wren                            0.04301075    0.04587156     0.04854369
## Pacific.slope.Flycatcher                0.07692308    0.14473684     0.06578947
## Red.breasted.Nuthatch                   0.05405405    0.03703704     0.00000000
## Dark.eyed.Junco                         0.04347826    0.08333333     0.05357143
## Olive.sided.Flycatcher                  0.02325581    0.01666667     0.05769231
##                          Swainson.s.Thrush Hammond.s.Flycatcher Western.Tanager
## Brown.Creeper                   0.00000000           0.00000000      0.00000000
## Pacific.Wren                    0.12121212           0.17333333      0.10843373
## Pacific.slope.Flycatcher        0.09009009           0.03389831      0.00000000
## Red.breasted.Nuthatch           0.00000000           0.00000000      0.00000000
## Dark.eyed.Junco                 0.10000000           0.02631579      0.02380952
## Olive.sided.Flycatcher          0.04395604           0.00000000      0.11428571
##                          Black.headed.Grosbeak Golden.Crowned.Kinglet
## Brown.Creeper                                0             0.02500000
## Pacific.Wren                                 0             0.02150538
## Pacific.slope.Flycatcher                     0             0.07936508
## Red.breasted.Nuthatch                        0             0.00000000
## Dark.eyed.Junco                              0             0.04545455
## Olive.sided.Flycatcher                       0             0.00000000
##                          Warbling.Vireo MacGillivray.s.Warbler Stellar.s.Jay
## Brown.Creeper                0.00000000                      0    0.00000000
## Pacific.Wren                 0.00000000                      0    0.02816901
## Pacific.slope.Flycatcher     0.01960784                      0    0.00000000
## Red.breasted.Nuthatch        0.00000000                      0    0.00000000
## Dark.eyed.Junco              0.07142857                      0    0.00000000
## Olive.sided.Flycatcher       0.00000000                      0    0.00000000
##                          Common.Nighthawk
## Brown.Creeper                  0.00000000
## Pacific.Wren                   0.01176471
## Pacific.slope.Flycatcher       0.00000000
## Red.breasted.Nuthatch          0.00000000
## Dark.eyed.Junco                0.00000000
## Olive.sided.Flycatcher         0.00000000

2.3 Obtendo os pesos

Os valores dos pesos que usaremos para construir o grafo ponderado também já foram calculados previamente, portanto, basta abrir o arquivo csv. Aqui também precisaremos nomear as linhas e apagar a primeira coluna.

# abrindo o csv
df_cd = read.csv("~/Hands-On-Igraph-R/data/birds-similarities/Split-1/birds-conditional-probabilities.csv")
head(df_cd)
##                          X Brown.Creeper Pacific.Wren Pacific.slope.Flycatcher
## 1            Brown.Creeper    0.02148438   0.00000000               0.05263158
## 2             Pacific.Wren    0.00000000   0.12695312               0.26315789
## 3 Pacific.slope.Flycatcher    0.18181818   0.15384615               0.07421875
## 4    Red.breasted.Nuthatch    0.00000000   0.00000000               0.05263158
## 5          Dark.eyed.Junco    0.00000000   0.00000000               0.05263158
## 6   Olive.sided.Flycatcher    0.09090909   0.03076923               0.05263158
##   Red.breasted.Nuthatch Dark.eyed.Junco Olive.sided.Flycatcher Hermit.Thrush
## 1            0.00000000         0.00000             0.08333333    0.00000000
## 2            0.00000000         0.00000             0.16666667    0.02564103
## 3            0.28571429         0.12500             0.16666667    0.10256410
## 4            0.01367188         0.00000             0.08333333    0.00000000
## 5            0.00000000         0.03125             0.00000000    0.15384615
## 6            0.14285714         0.00000             0.02343750    0.10256410
##   Chestnut.backed.Chickadee Varied.Thrush Hermit.Warbler Swainson.s.Thrush
## 1                   0.09375    0.06122449     0.06976744        0.00000000
## 2                   0.12500    0.10204082     0.11627907        0.19277108
## 3                   0.15625    0.22448980     0.11627907        0.12048193
## 4                   0.06250    0.04081633     0.00000000        0.00000000
## 5                   0.06250    0.10204082     0.06976744        0.10843373
## 6                   0.03125    0.02040816     0.06976744        0.04819277
##   Hammond.s.Flycatcher Western.Tanager Black.headed.Grosbeak
## 1           0.00000000      0.00000000                     0
## 2           0.56521739      0.33333333                     0
## 3           0.08695652      0.00000000                     0
## 4           0.00000000      0.00000000                     0
## 5           0.04347826      0.03703704                     0
## 6           0.00000000      0.14814815                     0
##   Golden.Crowned.Kinglet Warbling.Vireo MacGillivray.s.Warbler Stellar.s.Jay
## 1             0.03333333     0.00000000                      0          0.00
## 2             0.06666667     0.00000000                      0          0.25
## 3             0.16666667     0.07142857                      0          0.00
## 4             0.00000000     0.00000000                      0          0.00
## 5             0.06666667     0.14285714                      0          0.00
## 6             0.00000000     0.00000000                      0          0.00
##   Common.Nighthawk
## 1       0.00000000
## 2       0.04761905
## 3       0.00000000
## 4       0.00000000
## 5       0.00000000
## 6       0.00000000
# nomeando as linhas
rownames(df_cd) = df_cd$X    

# apagando a primeira coluna
df_cd = df_cd[,-1]

2.4 Obtendo os rótulos adicionais

Precisa mos organizar os rótulos de forma que eles possam ser usados na conversão dos data frames originais para o data frame final (que é composto por apenas 4 colunas). A função a seguir gera os rótulos de que precisamos para preencher o data frame final.

A partir dos nomes dos rótulos originais, a função preenche um vetor com a ordem desses rótulos que serão repetidos em l(número de rótulos) posições, de forma que labels.pivot serão os vértices de origem do data frame final.

Assim, o primeiro rótulo será repetido 19 vezes, em seguida, o segundo rótulo repete-se 19 vezes, e assim por diante, até terminar o último rótulo.

Função

create.pivot.labels <- function(names_labes){
  i = 1 # linha
  j = 1 # coluna
  a = 1 # célula
  labels.pivot = c() # data frame
  for(i in 1:19){
    for(j in 1:19){
      labels.pivot[a] = names_labes$Labels[i]
      a = a + 1
    }
  }
  return(labels.pivot)
}

Usando a função

from = create.pivot.labels(names_labes)
head(from)
## [1] "Brown.Creeper" "Brown.Creeper" "Brown.Creeper" "Brown.Creeper"
## [5] "Brown.Creeper" "Brown.Creeper"

2.5 Convertendo os data frames

Até agora obtivemos matrizes quadradas. O data frame para construir o grafo, no entanto, não é formatado desta maneira. Precisamos converter os data frames das matrizes de similaridade e dos pesos para uma tabela com apenas duas colunas. A primeira coluna conterá os rótulos e a segunda conterá os valores. Para isso, precisaremos usar a função pivot longer passando como parâmetro o data frame e o total de rótulos.

Usando pivot longer no data frame das similaridades

df_graph = data.frame(pivot_longer(df_jaccard, cols = 1:19))
head(df_graph)
##                       name      value
## 1            Brown.Creeper 1.00000000
## 2             Pacific.Wren 0.00000000
## 3 Pacific.slope.Flycatcher 0.04255319
## 4    Red.breasted.Nuthatch 0.00000000
## 5          Dark.eyed.Junco 0.00000000
## 6   Olive.sided.Flycatcher 0.04545455
# renomeia as colunas
colnames(df_graph) = c("to", "jaccard")

Usando pivot longer no data frame dos pesos

weigths_total = data.frame(pivot_longer(df_cd, cols = 1:19))
head(weigths_total)
##                       name      value
## 1            Brown.Creeper 0.02148438
## 2             Pacific.Wren 0.00000000
## 3 Pacific.slope.Flycatcher 0.05263158
## 4    Red.breasted.Nuthatch 0.00000000
## 5          Dark.eyed.Junco 0.00000000
## 6   Olive.sided.Flycatcher 0.08333333
# renomeia a coluna
names(weigths_total)[2] = "weights"

2.6 Juntando tudo

Agora finalmente podemos juntar todas as informações que precisamos para o data frame correto que será utilizado para construir o grafo. cbind é uma função que combina colunas.

df_graph = cbind(from, df_graph, weights = weigths_total$weights)
head(df_graph)
##            from                       to    jaccard    weights
## 1 Brown.Creeper            Brown.Creeper 1.00000000 0.02148438
## 2 Brown.Creeper             Pacific.Wren 0.00000000 0.00000000
## 3 Brown.Creeper Pacific.slope.Flycatcher 0.04255319 0.05263158
## 4 Brown.Creeper    Red.breasted.Nuthatch 0.00000000 0.00000000
## 5 Brown.Creeper          Dark.eyed.Junco 0.00000000 0.00000000
## 6 Brown.Creeper   Olive.sided.Flycatcher 0.04545455 0.08333333

3 Esparsificação

A esparsificação tem como objetivo remover arestas que não agregam valor ao grafo. Esta é a parte da modelagem do grafo propriamente dito. O que for definido aqui se refletirá nos métodos de detecção de comunidades.

3.1 Por Treshold

Esparsificação por threshold significa retirar arestas que estejam acima ou abaixo de um determinado valor.

Ordenando o data frame por valores de jaccard

df_graph_tr = arrange(df_graph, desc(jaccard))
head(df_graph_tr)
##                       from                       to jaccard    weights
## 1            Brown.Creeper            Brown.Creeper       1 0.02148438
## 2             Pacific.Wren             Pacific.Wren       1 0.12695312
## 3 Pacific.slope.Flycatcher Pacific.slope.Flycatcher       1 0.07421875
## 4    Red.breasted.Nuthatch    Red.breasted.Nuthatch       1 0.01367188
## 5          Dark.eyed.Junco          Dark.eyed.Junco       1 0.03125000
## 6   Olive.sided.Flycatcher   Olive.sided.Flycatcher       1 0.02343750

Fazendo uma cópia do data frame

df_graph_2 = df_graph_tr

Removendo self-loops

Neste contexto estou retirando apenas os pares de rótulos consigo mesmos, isto é, rótulo 1 com rótulo 1, rótulo 2 com rótulo 2, assim por diante. Como esses pares de rótulos geram arestas para si mesmos e não conectam com outros, então eles não são muito úteis na criação do grafo, não agregando informação relevante. O meu interesse está nas relações entre um rótulo e os outros e não com ele mesmo.

df_graph_tr = df_graph_tr[c(-1:-19),]
head(df_graph_tr)
##                      from                     to   jaccard   weights
## 20          Varied.Thrush Golden.Crowned.Kinglet 0.1791045 0.4000000
## 21 Golden.Crowned.Kinglet          Varied.Thrush 0.1791045 0.2448980
## 22           Pacific.Wren   Hammond.s.Flycatcher 0.1733333 0.5652174
## 23   Hammond.s.Flycatcher           Pacific.Wren 0.1733333 0.2000000
## 24          Varied.Thrush      Swainson.s.Thrush 0.1578947 0.2168675
## 25      Swainson.s.Thrush          Varied.Thrush 0.1578947 0.3673469

Removendo todos os valores de similaridades de jaccard iguais a zero e menores que 0.01

df_graph_tr = df_graph_tr[!(df_graph_tr$jaccard == 0 | df_graph_tr$jaccard < 0.01),]
head(df_graph_tr)
##                      from                     to   jaccard   weights
## 20          Varied.Thrush Golden.Crowned.Kinglet 0.1791045 0.4000000
## 21 Golden.Crowned.Kinglet          Varied.Thrush 0.1791045 0.2448980
## 22           Pacific.Wren   Hammond.s.Flycatcher 0.1733333 0.5652174
## 23   Hammond.s.Flycatcher           Pacific.Wren 0.1733333 0.2000000
## 24          Varied.Thrush      Swainson.s.Thrush 0.1578947 0.2168675
## 25      Swainson.s.Thrush          Varied.Thrush 0.1578947 0.3673469

3.2 Por Knn

A esparsificação por KNN modifica a importância da aresta. Para cada vértice serão considerados apenas os k maiores pesos. Os pares de vértices correspondentes ficarão intactos, enquanto o restante terá o seu valor alterado para zero. Esta é uma forma simples de escolher os k maiores valores para uma aresta, mas você pode pensar em algo mais elaborado.

Reordenando o data frame pela coluna “from”

df_graph_2 = arrange(df_graph_2, desc(from))
head(df_graph_2)
##              from                        to    jaccard    weights
## 1 Western.Tanager           Western.Tanager 1.00000000 0.05273438
## 2 Western.Tanager    Olive.sided.Flycatcher 0.11428571 0.33333333
## 3 Western.Tanager      Hammond.s.Flycatcher 0.11111111 0.21739130
## 4 Western.Tanager              Pacific.Wren 0.10843373 0.13846154
## 5 Western.Tanager             Hermit.Thrush 0.08196721 0.12820513
## 6 Western.Tanager Chestnut.backed.Chickadee 0.07272727 0.12500000

As arestas com os k maiores pesos mantém o valor de similaridade original. Nas arestas retantes, a similaridade passa a ser zero.

Como são 19 rótulos, precisamos fazer um FOR para poder preencher todo o dataframe corretamente, já que 19 X 19 = 361 pares de rótulos. Precisamos verificar para cada rótulo quais são os outros rótulos com maior peso. Então, primeiro separamos o rótulo que desejamos avaliar. Para facilitar o código, eu ordenei o data frame do maior para o menor peso. Depois basta substituir o valor de jaccard por zero a partir da linha 5 - já que queremos apenas os 4 maiores pesos.

df_graph_knn = data.frame()
i = 1
for(i in 1:19){
  # filtra pelo rótulo específico
  res1 = df_graph_2[df_graph_2$from == toString(names_labes$Labels[i]),]
  
  # ordena os pesos do maior para o menor
  knn = res1[order(res1$weights, decreasing=TRUE), ]
  
  # faz jaccard = 0 a partir da linha 5
  knn[5:19,]$jaccard = 0
  
  # monta o data frame 
  df_graph_knn = rbind(df_graph_knn, knn)
  gc()
}
head(df_graph_knn)
##              from                        to    jaccard    weights
## 325 Brown.Creeper Chestnut.backed.Chickadee 0.07500000 0.09375000
## 328 Brown.Creeper    Olive.sided.Flycatcher 0.04545455 0.08333333
## 326 Brown.Creeper            Hermit.Warbler 0.05882353 0.06976744
## 327 Brown.Creeper             Varied.Thrush 0.05263158 0.06122449
## 329 Brown.Creeper  Pacific.slope.Flycatcher 0.00000000 0.05263158
## 330 Brown.Creeper    Golden.Crowned.Kinglet 0.00000000 0.03333333

Depois disso você também verificar os self-loops e retirá-los, como fizemos no threshold. Neste tutorial não farei isto pois quer ilustrar as diferenças nos grafos quando tratamos ou não esta questão.

4 Construindo os Grafos

Para construir o grafo usamos a função graph_from_data_frame

jaccard_graph_tr = graph_from_data_frame(df_graph_tr, directed=F) 
jaccard_graph_tr
## IGRAPH 27edf4a UN-- 19 184 -- 
## + attr: name (v/c), jaccard (e/n), weights (e/n)
## + edges from 27edf4a (vertex names):
##  [1] Varied.Thrush         --Golden.Crowned.Kinglet  
##  [2] Varied.Thrush         --Golden.Crowned.Kinglet  
##  [3] Pacific.Wren          --Hammond.s.Flycatcher    
##  [4] Pacific.Wren          --Hammond.s.Flycatcher    
##  [5] Varied.Thrush         --Swainson.s.Thrush       
##  [6] Varied.Thrush         --Swainson.s.Thrush       
##  [7] Golden.Crowned.Kinglet--Black.headed.Grosbeak   
##  [8] Golden.Crowned.Kinglet--Black.headed.Grosbeak   
## + ... omitted several edges
V(jaccard_graph_tr) # retorna os vértices
## + 19/19 vertices, named, from 27edf4a:
##  [1] Varied.Thrush             Golden.Crowned.Kinglet   
##  [3] Pacific.Wren              Hammond.s.Flycatcher     
##  [5] Swainson.s.Thrush         Black.headed.Grosbeak    
##  [7] Pacific.slope.Flycatcher  Hermit.Thrush            
##  [9] Dark.eyed.Junco           Olive.sided.Flycatcher   
## [11] Western.Tanager           Chestnut.backed.Chickadee
## [13] MacGillivray.s.Warbler    Warbling.Vireo           
## [15] Brown.Creeper             Hermit.Warbler           
## [17] Common.Nighthawk          Red.breasted.Nuthatch    
## [19] Stellar.s.Jay
E(jaccard_graph_tr) # retorna as arestas
## + 184/184 edges from 27edf4a (vertex names):
##  [1] Varied.Thrush         --Golden.Crowned.Kinglet  
##  [2] Varied.Thrush         --Golden.Crowned.Kinglet  
##  [3] Pacific.Wren          --Hammond.s.Flycatcher    
##  [4] Pacific.Wren          --Hammond.s.Flycatcher    
##  [5] Varied.Thrush         --Swainson.s.Thrush       
##  [6] Varied.Thrush         --Swainson.s.Thrush       
##  [7] Golden.Crowned.Kinglet--Black.headed.Grosbeak   
##  [8] Golden.Crowned.Kinglet--Black.headed.Grosbeak   
##  [9] Varied.Thrush         --Pacific.slope.Flycatcher
## [10] Varied.Thrush         --Pacific.slope.Flycatcher
## + ... omitted several edges
jaccard_graph_knn = graph_from_data_frame(df_graph_knn, directed=F) 
jaccard_graph_knn
## IGRAPH dcd6bb5 UN-- 19 361 -- 
## + attr: name (v/c), jaccard (e/n), weights (e/n)
## + edges from dcd6bb5 (vertex names):
##  [1] Brown.Creeper--Chestnut.backed.Chickadee
##  [2] Brown.Creeper--Olive.sided.Flycatcher   
##  [3] Brown.Creeper--Hermit.Warbler           
##  [4] Brown.Creeper--Varied.Thrush            
##  [5] Brown.Creeper--Pacific.slope.Flycatcher 
##  [6] Brown.Creeper--Golden.Crowned.Kinglet   
##  [7] Brown.Creeper--Brown.Creeper            
##  [8] Brown.Creeper--Pacific.Wren             
## + ... omitted several edges
V(jaccard_graph_knn)
## + 19/19 vertices, named, from dcd6bb5:
##  [1] Brown.Creeper             Pacific.Wren             
##  [3] Pacific.slope.Flycatcher  Red.breasted.Nuthatch    
##  [5] Dark.eyed.Junco           Olive.sided.Flycatcher   
##  [7] Hermit.Thrush             Chestnut.backed.Chickadee
##  [9] Varied.Thrush             Hermit.Warbler           
## [11] Swainson.s.Thrush         Hammond.s.Flycatcher     
## [13] Western.Tanager           Black.headed.Grosbeak    
## [15] Golden.Crowned.Kinglet    Warbling.Vireo           
## [17] MacGillivray.s.Warbler    Stellar.s.Jay            
## [19] Common.Nighthawk
E(jaccard_graph_knn)
## + 361/361 edges from dcd6bb5 (vertex names):
##  [1] Brown.Creeper--Chestnut.backed.Chickadee
##  [2] Brown.Creeper--Olive.sided.Flycatcher   
##  [3] Brown.Creeper--Hermit.Warbler           
##  [4] Brown.Creeper--Varied.Thrush            
##  [5] Brown.Creeper--Pacific.slope.Flycatcher 
##  [6] Brown.Creeper--Golden.Crowned.Kinglet   
##  [7] Brown.Creeper--Brown.Creeper            
##  [8] Brown.Creeper--Pacific.Wren             
##  [9] Brown.Creeper--Red.breasted.Nuthatch    
## [10] Brown.Creeper--Dark.eyed.Junco          
## + ... omitted several edges

5 Plotando Grafos

par(mfrow=c(1,1))
plot(jaccard_graph_tr)
title(cex.main= 0.8, main = "Treshold Graph")

par(mfrow=c(1,1))
plot(jaccard_graph_knn)
title(cex.main= 0.8, main = "Knn Graph")

6 Modularidade

A modularidade mede a qualidade da partição ou quão separados estão os diferentes tipos de vértices uns dos outros. Portanto, quantifica a densidade de links dentro das comunidades comparado com links entre comunidades. Dentro de um grupo, os nós são altamente conectados em comparação com os outros grupos. Quanto maior o valor da modularidade melhor!

\[ Q = \sum_{x}(e_{xy} - a^2) \]

\[ a_{y} = \sum_{y} e_{xy} \]

e_{xy} é a quantidade de links de um grafo que conecta os nós em uma comunidade x para os nós de uma comunidade y.

7 Aplicando Métodos de Detecção de Comunidades

A grosso modo, uma comunidade é um conjunto de vértices com muitas arestas dentro da comunidade e poucas arestas fora da comunidade.

Os grafos associados são em geral globalmente esparsos, mas localmente densos: existem grupos de vértices, chamados de comunidades, altamente conectados entre si, mas com poucos links para outros vértices.

Métodos de detecção de comunidade são basicamente problemas de particionamento de grafos: consiste em dividir os vértices em grupos de tal forma que o número de arestas entre eles é minimizado.

Uma boa divisão da rede em comunidades não é simplesmente uma em que o número de arestas entre os grupos é pequeno, mas uma em que o número de arestas entre os grupos é menor do que o esperado.

7.1 Edge Betweenness

Edge Betweenness significa aresta intermediária. É um método de detecção de estrutura de comunidade baseada em arestas intermediárias. Muitas redes consistem em módulos (grupos/comunidades) densamente conectados, mas escassamente conectados a outros módulos

Edge Beteweenness mede o número de caminhos mais curtos através da aresta. O método usa técnicas de Algoritmos de Agrupamento Hierárquicos Divisivos: descobrir divisões naturais baseadas em métodos de similaridades ou força de conexão entre os vértices.

Passo a passo do algoritmo (simplificado)

  1. Calcular o score edge betweenness para todas as arestas da rede

  2. Encontrar a aresta com o maior score e removê-la da rede

  3. Recalcular o score edge betwenness para as arestas que ficaram

  4. Repetir a partir do passo 2

Ideia do Algoritmo

É provável que as arestas que conectam módulos separados tenham alta intermediação de arestas, já que todos os caminhos mais curtos de um módulo a outro devem passar por elas. Portanto, se removermos gradualmente a aresta com a pontuação de intermediação mais alta, obteremos um dendrograma. As folhas da árvore são os vértices individuais e a raiz da árvore representa o gráfico inteiro.

De acordo com o artigo original:

“[…] Primeiro, usamos uma técnica de “divisão” que remove de forma iterativa as arestas da rede, dividindo-a assim em comunidades. As arestas a serem removidas são identificadas usando uma medida de um conjunto de medidas de intermediação de arestas, das quais a mais simples é uma generalização para as arestas da intermediação de caminho mais curto padrão de Freeman. Em segundo lugar, nossos algoritmos incluem uma etapa de recálculo em que as pontuações de intermediação são reavaliadas após a remoção de cada aresta. Esta etapa, que estava faltando nos algoritmos anteriores, é de fundamental importância para o sucesso dos algortimos. Sem ele, os algoritmos falham miseravelmente até mesmo nas tarefas de clustering mais simples.”

Parâmetros da Função cluster_edge_betweeness

GRAPH: grafo construído

WEIGTHS: pesos das arestas. NULL pode ser usado para omitir os pesos das arestas. Os pesos são usados por padrão se estiverem presentes. Pesos de aresta são usados para calcular as arestas intermediárias ponderadas. Isso significa que as arestas são interpretadas como distâncias, não como pontos fortes de conexão.

MERGES: indica se deve ser retornando os pontos de fusão calculados pelo algoritmo em forma de matriz

BRIDGES: indica se deve retornar as arestas removidas que foram capazes de dividir a rede

MODULARITY: indica se deve ser calculada a pontuação máxima de modularidade, considerando todas as estruturas de comunidades possíveis ao longo do edge betweenness baseado nas aretas removidas.

MEMBERSHIP: indica se deve ser calculado o vetor de membership correspondente à pontuação de modularidade mais alta possível.

Aplicando o método

eb_tr = cluster_edge_betweenness(jaccard_graph_tr, 
                                 weights = jaccard_graph_tr$weights,
                                 edge.betweenness = TRUE,
                                 merges = TRUE, 
                                 bridges = TRUE,
                                 modularity = TRUE, 
                                 membership = TRUE)

eb_knn = cluster_edge_betweenness(jaccard_graph_knn, 
                                  weights = jaccard_graph_tr$weights,
                                  edge.betweenness = TRUE,
                                  merges = TRUE, 
                                  bridges = TRUE,
                                  modularity = TRUE, 
                                  membership = TRUE)

Função para plotar os grafos

plotar <- function(comunidade, grafo, titulo){
  plot(comunidade, grafo, 
       vertex.size=18, 
       vertex.color="gold",
       vertex.shape = "sphere", 
       vertex.frame.color="orange", 
       vertex.label.color="black", 
       vertex.label.cex=0.7, 
       vertex.label.family = "Times", 
       vertex.label.font =0.5, 
       edge.arrow.size=.5, 
       edge.color = "gray", 
       edge.width = 0.5) 
  title(cex.main= 0.8, main = titulo)
}

Plotando os Grafos

As cores circulando alguns nós individuais, ou grupos de nós, representam as comunidades.

par(mfrow=c(1,2))
plotar(eb_tr, jaccard_graph_tr, "Edge Betweenness threshold")
plotar(eb_knn, jaccard_graph_knn, "Edge Betweenness knn")

Informações dos grafos

eb_tr
## IGRAPH clustering edge betweenness, groups: 6, mod: 0.00089
## + groups:
##   $`1`
##    [1] "Varied.Thrush"             "Golden.Crowned.Kinglet"   
##    [3] "Pacific.Wren"              "Hammond.s.Flycatcher"     
##    [5] "Swainson.s.Thrush"         "Pacific.slope.Flycatcher" 
##    [7] "Hermit.Thrush"             "Dark.eyed.Junco"          
##    [9] "Olive.sided.Flycatcher"    "Western.Tanager"          
##   [11] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
##   [13] "Brown.Creeper"             "Hermit.Warbler"           
##   
##   $`2`
##   + ... omitted several groups/vertices
eb_knn
## IGRAPH clustering edge betweenness, groups: 6, mod: 1.1e-16
## + groups:
##   $`1`
##   [1] "Brown.Creeper"
##   
##   $`2`
##   [1] "Pacific.Wren"
##   
##   $`3`
##   [1] "Pacific.slope.Flycatcher"
##   
##   $`4`
##   + ... omitted several groups/vertices

Tamanho de cada comunidade

sizes(eb_tr)
## Community sizes
##  1  2  3  4  5  6 
## 14  1  1  1  1  1
sizes(eb_knn)
## Community sizes
##  1  2  3  4  5  6 
##  1  1  1  1  1 14

Listando as comunidades

communities(eb_tr)
## $`1`
##  [1] "Varied.Thrush"             "Golden.Crowned.Kinglet"   
##  [3] "Pacific.Wren"              "Hammond.s.Flycatcher"     
##  [5] "Swainson.s.Thrush"         "Pacific.slope.Flycatcher" 
##  [7] "Hermit.Thrush"             "Dark.eyed.Junco"          
##  [9] "Olive.sided.Flycatcher"    "Western.Tanager"          
## [11] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
## [13] "Brown.Creeper"             "Hermit.Warbler"           
## 
## $`2`
## [1] "Black.headed.Grosbeak"
## 
## $`3`
## [1] "MacGillivray.s.Warbler"
## 
## $`4`
## [1] "Common.Nighthawk"
## 
## $`5`
## [1] "Red.breasted.Nuthatch"
## 
## $`6`
## [1] "Stellar.s.Jay"
communities(eb_knn) 
## $`1`
## [1] "Brown.Creeper"
## 
## $`2`
## [1] "Pacific.Wren"
## 
## $`3`
## [1] "Pacific.slope.Flycatcher"
## 
## $`4`
## [1] "Red.breasted.Nuthatch"
## 
## $`5`
## [1] "Dark.eyed.Junco"
## 
## $`6`
##  [1] "Olive.sided.Flycatcher"    "Hermit.Thrush"            
##  [3] "Chestnut.backed.Chickadee" "Varied.Thrush"            
##  [5] "Hermit.Warbler"            "Swainson.s.Thrush"        
##  [7] "Hammond.s.Flycatcher"      "Western.Tanager"          
##  [9] "Black.headed.Grosbeak"     "Golden.Crowned.Kinglet"   
## [11] "Warbling.Vireo"            "MacGillivray.s.Warbler"   
## [13] "Stellar.s.Jay"             "Common.Nighthawk"

Grupos

eb_tr$membership
##  [1] 1 1 1 1 1 2 1 1 1 1 1 1 3 1 1 1 4 5 6
eb_knn$membership 
##  [1] 1 2 3 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6
membership(eb_tr)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         1                         1 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         1                         1                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         1                         1 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         1                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         3                         1                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         1                         4                         5 
##             Stellar.s.Jay 
##                         6
membership(eb_knn)
##             Brown.Creeper              Pacific.Wren  Pacific.slope.Flycatcher 
##                         1                         2                         3 
##     Red.breasted.Nuthatch           Dark.eyed.Junco    Olive.sided.Flycatcher 
##                         4                         5                         6 
##             Hermit.Thrush Chestnut.backed.Chickadee             Varied.Thrush 
##                         6                         6                         6 
##            Hermit.Warbler         Swainson.s.Thrush      Hammond.s.Flycatcher 
##                         6                         6                         6 
##           Western.Tanager     Black.headed.Grosbeak    Golden.Crowned.Kinglet 
##                         6                         6                         6 
##            Warbling.Vireo    MacGillivray.s.Warbler             Stellar.s.Jay 
##                         6                         6                         6 
##          Common.Nighthawk 
##                         6

Arestas removidas

head(eb_tr$removed.edges)
## [1] 145 146  97  98  85  86
head(eb_knn$removed.edges)
## [1]   1 135   3 174   2  99

Arestas removidas que realmente dividiram um componente do grafo

eb_tr$bridges
##  [1] 185 183 179 173 165 155 143 131 117 101  85  69  57  45  33  23  13   5
eb_knn$bridges
##  [1] 343 341 337 331 323 313 301 287 271 253 233 211 187 161 133 103  71  37

Valores do cálculo de edge betweenness

head(eb_tr$edge.betweenness)
## [1]  5.838095  9.914719  9.000000 18.000000  3.134804  4.928571
head(eb_knn$edge.betweenness)
## [1] 0.5000000 1.0000000 0.5294118 1.0303030 0.5625000 1.0645161

Pontos de mesclagem do algoritmo divisivo

head(eb_tr$merges)
##      [,1] [,2]
## [1,]   16   11
## [2,]   20    9
## [3,]   21    2
## [4,]   12   22
## [5,]   23    5
## [6,]   24    1
head(eb_knn$merges)
##      [,1] [,2]
## [1,]   19   18
## [2,]   20   17
## [3,]   21   16
## [4,]   22   15
## [5,]   23   14
## [6,]   24   13

Total de vértices do grafo

eb_tr$vcount
## [1] 19
eb_knn$vcount 
## [1] 19

Valor de modularidade da estrutura da comunidade

eb_tr$modularity
##  [1] -6.149575e-02 -6.037335e-02 -5.399338e-02 -4.903119e-02 -5.186673e-02
##  [6] -5.511578e-02 -5.606096e-02 -6.303166e-02 -5.647448e-02 -2.528355e-02
## [11] -2.020321e-02 -1.417769e-02 -1.063327e-03  8.861059e-04 -5.907372e-05
## [16] -4.903119e-03 -1.654064e-03 -2.362949e-04  0.000000e+00
modularity(eb_tr)
## [1] 0.0008861059
head(modularity_matrix(jaccard_graph_tr))
##             [,1]        [,2]       [,3]       [,4]       [,5]       [,6]
## [1,] -2.13043478  0.02173913  0.3260870  0.7826087 -0.2826087 -0.9130435
## [2,]  0.02173913 -1.83695652  0.4456522 -1.1304348 -0.1195652  1.1521739
## [3,]  0.32608696  0.44565217 -1.3152174  1.0434783  0.2065217 -0.7173913
## [4,]  0.78260870 -1.13043478  1.0434783 -0.6956522  0.6956522 -0.5217391
## [5,] -0.28260870 -0.11956522  0.2065217  0.6956522 -2.4456522  1.0217391
## [6,] -0.91304348  1.15217391 -0.7173913 -0.5217391  1.0217391 -0.3913043
##             [,7]       [,8]       [,9]      [,10]      [,11]       [,12]
## [1,]  0.02173913  0.3260870  0.4782609  0.4782609  0.3260870 -0.43478261
## [2,]  0.16304348  0.4456522  0.5869565 -1.4130435  0.4456522 -0.26086957
## [3,]  0.44565217 -1.3152174 -1.1956522  0.8043478  0.6847826  0.08695652
## [4,]  0.86956522 -0.9565217  1.1304348 -0.8695652  1.0434783  0.60869565
## [5,] -0.11956522  0.2065217  0.3695652  0.3695652  0.2065217 -0.60869565
## [6,] -0.84782609  1.2826087 -0.6521739 -0.6521739 -0.7173913 -1.04347826
##           [,13]      [,14]      [,15]      [,16]      [,17]      [,18]
## [1,] -0.7608696  0.9347826  1.0869565 -0.2826087 -1.0652174  1.3913043
## [2,]  1.2934783  1.0108696  1.1521739 -0.1195652 -0.9891304 -0.5652174
## [3,] -0.5978261 -0.8369565 -0.7173913  0.2065217  1.1630435 -0.4782609
## [4,] -0.4347826 -0.6086957 -0.5217391  0.6956522 -0.6086957 -0.3478261
## [5,]  1.1847826  0.8586957 -0.9782609 -0.4456522  0.8586957 -0.6521739
## [6,]  1.6739130 -0.4565217 -0.3913043  1.0217391  1.5434783 -0.2608696
##           [,19]
## [1,] -0.3043478
## [2,] -0.2826087
## [3,]  1.7608696
## [4,] -0.1739130
## [5,] -0.3260870
## [6,] -0.1304348
eb_knn$modularity
##  [1] 8.239937e-18 8.673617e-18 1.040834e-17 1.387779e-17 1.387779e-17
##  [6] 1.387779e-17 2.775558e-17 2.775558e-17 2.775558e-17 5.551115e-17
## [11] 0.000000e+00 5.551115e-17 0.000000e+00 1.110223e-16 0.000000e+00
## [16] 1.110223e-16 0.000000e+00 1.110223e-16 0.000000e+00
modularity(eb_knn)
## [1] 1.110223e-16
head(modularity_matrix(jaccard_graph_knn))
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
## [1,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0
## [2,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0
## [3,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0
## [4,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0
## [5,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0
## [6,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0
##      [,15] [,16] [,17] [,18] [,19]
## [1,]     0     0     0     0     0
## [2,]     0     0     0     0     0
## [3,]     0     0     0     0     0
## [4,]     0     0     0     0     0
## [5,]     0     0     0     0     0
## [6,]     0     0     0     0     0

Compara duas comunidades

Avalia a distância entre duas estruturas da comunidade

compare(eb_tr, eb_knn)
## [1] 1.807556
compare(membership(eb_tr), membership(eb_knn))
## [1] 1.807556

Verificando se é Hierárquico

is_hierarchical(eb_tr)
## [1] TRUE
dend_eb = as.dendrogram(eb_tr)
dend_eb 
## 'dendrogram' with 2 branches and 19 members total, at height 18
hc_eb = as.hclust(eb_tr)
hc_eb 
## 
## Call:
## as.hclust.dendrogram(x = as.dendrogram(x, hang = hang, use.modularity = use.modularity))
## 
## Cluster method   : NA 
## Distance         : NA 
## Number of objects: 19
hc_eb$order
##  [1] 19 18 13 17 14 15 10  8 12 16 11  9  2  5  1  7  3  4  6
is_hierarchical(eb_knn)
## [1] TRUE
dend_eb_knn = as.dendrogram(eb_knn)
dend_eb_knn
## 'dendrogram' with 2 branches and 19 members total, at height 18
hc_eb_knn = as.hclust(eb_knn)
hc_eb_knn
## 
## Call:
## as.hclust.dendrogram(x = as.dendrogram(x, hang = hang, use.modularity = use.modularity))
## 
## Cluster method   : NA 
## Distance         : NA 
## Number of objects: 19
hc_eb_knn$order
##  [1] 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

Plotando os Dendrogramas

par(mfrow=c(1,1))
plot_dendrogram(eb_tr)
title(cex.main= 0.8, main = "Dendrogram threshold")

par(mfrow=c(1,1))
plot_dendrogram(eb_knn)
title(cex.main= 0.8, main = "Dendrogram knn")

7.2 Label Propagation

Do artigo: “[…] em nosso algoritmo, cada nó é inicializado com um rótulo único e, a cada passo, cada nó adota o rótulo que a maioria de seus vizinhos possui. Neste processo iterativo, grupos de nós densamente conectados formam um consenso sobre um rótulo único para formar comunidades […]”

Este algoritmo simula a difusão do fluxo na rede através da difusão de rótulos. No grafo, cada vértice é associado a uma único rótulo. Depois o rótulo de cada vértice é atualizado iterativamente com o rótulo majoritário associado aos vizinhos, sendo a atualização aleatória. O algoritmo pára quando todos os rótulos dos vértices são consistentes com o rótulo mais frequente na vizinhança.

Passo a Passo do Método

  1. Inicialize os rótulos em todos os nós da rede. Para um determinado nó x, C x (0) = x;

  2. Defina t = 1;

  3. Organize os nós da rede em uma ordem aleatória e defina-a como X;

  4. Para cada x ∈ X escolhido nessa ordem específica, seja C x (t) = f (C x i1 (t), …, C x im (t), C xi (m + 1) (t - 1), …, C x ik (t - 1)). f retorna o rótulo que ocorre com a frequência mais alta entre os vizinhos e os laços são quebrados de maneira uniforme e aleatória;

  5. Se cada nó tiver um rótulo que indica o número máximo de seus vizinhos, pare o algoritmo. Caso contrário, defina t = t + 1 e vá para (3).

Parâmetros do Método

GRAPH: grafo. Deve ser não direcionado para fazer sentido.

WEIGTHS: pesos positivos. É um parametro opcional. Se o grafo tem um atribo de pesos de arestas, então eles são usados por padrão. Pesos de arestas maiores correspondem a conexões mais fortes.

INITIAL: é o estado inicial. Se for NULL, cada vértice terá um rótulo diferente no início. Caso contrário, deve ser um vetor com uma entrada para cada vértice. Valores não negativos denotam rótulos diferentes, entradas negativas denotam vértices sem rótulos.

FIXED: é um vetor lógico que denota quais rótulos são fixos. Este parâmetro deve ser usado quando um valor inicial é definido, caso contrário será ignorado. Observe também que vértices sem rótulos não podem ser fixed.

Aplicando o método

lp_tr = cluster_label_prop(jaccard_graph_tr, 
                         weights = jaccard_graph_tr$weights)

lp_knn = cluster_label_prop(jaccard_graph_knn, 
                         weights = jaccard_graph_knn$weights)

Plotando os grafos

par(mfrow=c(1,2))
plotar(lp_tr, jaccard_graph_tr, "Label Propagation threshold")
plotar(lp_knn, jaccard_graph_knn, "Label Propagation knn")

Informações

lp_tr
## IGRAPH clustering label propagation, groups: 1, mod: 0
## + groups:
##   $`1`
##    [1] "Varied.Thrush"             "Golden.Crowned.Kinglet"   
##    [3] "Pacific.Wren"              "Hammond.s.Flycatcher"     
##    [5] "Swainson.s.Thrush"         "Black.headed.Grosbeak"    
##    [7] "Pacific.slope.Flycatcher"  "Hermit.Thrush"            
##    [9] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##   [11] "Western.Tanager"           "Chestnut.backed.Chickadee"
##   [13] "MacGillivray.s.Warbler"    "Warbling.Vireo"           
##   [15] "Brown.Creeper"             "Hermit.Warbler"           
##   [17] "Common.Nighthawk"          "Red.breasted.Nuthatch"    
##   + ... omitted several groups/vertices
lp_knn
## IGRAPH clustering label propagation, groups: 1, mod: 0
## + groups:
##   $`1`
##    [1] "Brown.Creeper"             "Pacific.Wren"             
##    [3] "Pacific.slope.Flycatcher"  "Red.breasted.Nuthatch"    
##    [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##    [7] "Hermit.Thrush"             "Chestnut.backed.Chickadee"
##    [9] "Varied.Thrush"             "Hermit.Warbler"           
##   [11] "Swainson.s.Thrush"         "Hammond.s.Flycatcher"     
##   [13] "Western.Tanager"           "Black.headed.Grosbeak"    
##   [15] "Golden.Crowned.Kinglet"    "Warbling.Vireo"           
##   [17] "MacGillivray.s.Warbler"    "Stellar.s.Jay"            
##   + ... omitted several groups/vertices

Membership

membership(lp_tr)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         1                         1 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         1                         1                         1 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         1                         1 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         1                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         1                         1                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         1                         1                         1 
##             Stellar.s.Jay 
##                         1
membership(lp_knn)
##             Brown.Creeper              Pacific.Wren  Pacific.slope.Flycatcher 
##                         1                         1                         1 
##     Red.breasted.Nuthatch           Dark.eyed.Junco    Olive.sided.Flycatcher 
##                         1                         1                         1 
##             Hermit.Thrush Chestnut.backed.Chickadee             Varied.Thrush 
##                         1                         1                         1 
##            Hermit.Warbler         Swainson.s.Thrush      Hammond.s.Flycatcher 
##                         1                         1                         1 
##           Western.Tanager     Black.headed.Grosbeak    Golden.Crowned.Kinglet 
##                         1                         1                         1 
##            Warbling.Vireo    MacGillivray.s.Warbler             Stellar.s.Jay 
##                         1                         1                         1 
##          Common.Nighthawk 
##                         1

Tamanho

sizes(lp_tr)
## Community sizes
##  1 
## 19
sizes(lp_knn)
## Community sizes
##  1 
## 19

Modularidade

# ambos grafos não possuem estrutura de comunidade
modularity(lp_tr)
## [1] 0
modularity(lp_knn)
## [1] 0

Comunidades

communities(lp_tr)
## $`1`
##  [1] "Varied.Thrush"             "Golden.Crowned.Kinglet"   
##  [3] "Pacific.Wren"              "Hammond.s.Flycatcher"     
##  [5] "Swainson.s.Thrush"         "Black.headed.Grosbeak"    
##  [7] "Pacific.slope.Flycatcher"  "Hermit.Thrush"            
##  [9] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
## [11] "Western.Tanager"           "Chestnut.backed.Chickadee"
## [13] "MacGillivray.s.Warbler"    "Warbling.Vireo"           
## [15] "Brown.Creeper"             "Hermit.Warbler"           
## [17] "Common.Nighthawk"          "Red.breasted.Nuthatch"    
## [19] "Stellar.s.Jay"
communities(lp_knn)
## $`1`
##  [1] "Brown.Creeper"             "Pacific.Wren"             
##  [3] "Pacific.slope.Flycatcher"  "Red.breasted.Nuthatch"    
##  [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##  [7] "Hermit.Thrush"             "Chestnut.backed.Chickadee"
##  [9] "Varied.Thrush"             "Hermit.Warbler"           
## [11] "Swainson.s.Thrush"         "Hammond.s.Flycatcher"     
## [13] "Western.Tanager"           "Black.headed.Grosbeak"    
## [15] "Golden.Crowned.Kinglet"    "Warbling.Vireo"           
## [17] "MacGillivray.s.Warbler"    "Stellar.s.Jay"            
## [19] "Common.Nighthawk"

É hierárquico?

is_hierarchical(lp_tr)
## [1] FALSE
is_hierarchical(lp_knn)
## [1] FALSE

7.3 Walktrap

O algoritmo é baseado em random walks, isto é, numa caminhada aleatória ou passeio aleatório, o qual consiste de uma sucessão de passos aleatórios. Mais informações, por favor, acesse: https://pt.wikipedia.org/wiki/Passeio_aleat%C3%B3rio.

No contexto de grafos, o processo do random walk indica que em cada passo o caminhante está em um vértice e aleatoriamente se move para outro vértice vizinho.

De acordo com os autores do artigo original, passeios aleatórios tendem a ficar presos em partes densamente conectadas do grafo, dai o nome walktrap. Portanto, caminhos aleatórios de curta distância tendem a permanecer na mesma comunidade.

O algoritmo é baseado em algoritmos de agrupamento aglomerativo hierárquico. De acordo com o artigo original, o objetivo foi criar uma nova medida de distância entre vértices que quantificam sua estrutura de similaridade usando random walks a qual pode ser usada no algoritmo de agrupamento hierarquico aglomerativo.

Passo a passo do algoritmo:

  1. Começa com uma partição não agrupada, isto é, uma partição com n comunidades.

  2. Calcula todas as distâncias entre todos os vértices adjacentes

  3. A partição evolui repetindo as operações a seguir em cada passo:

  1. Escolher 2 comunidades de acordo com o critério baseado na distância entre as comunidades

  2. Fundir as 2 comunidades em uma nova e criar uma nova partição

  3. Atualizar as distâncias entre as comunidades

  1. Depois de n-1 passos o algoritmo finaliza

Parametros

GRAPH: grafo propriamente dito

WEIGHTS: pesos das arestas. Pesos de aresta maiores aumentam a probabilidade de que uma aresta seja selecionada pelo random walk, portanto, pesos de aresta maiores correspondem a conexões mais fortes.

STEPS: é o comprimento das caminhadas aleatórias a serem realizadas. Importante: De acordo com o artigo original este é um item aberto de pesquisa pois ainda é dificil dizer qual o número ideal de passos. No entanto, eles recomendam usar de 3 a 8 passos, mas que 4 ou 5 passos parecem ser os melhores.

MERGES: se deseja incluir a matriz de mesclagem no resultado.

MODULARITY: se deve ser incluido o vetor das pontuações de modularidade no resultado. Se o argumento da associação for verdadeiro, ele sempre será calculado.

MEMBERSHIP: se deve ser calculado o vetor de membership para a divisão correspondente ao maior valor de modularidade.

Aplicando o método

wt_tr = cluster_walktrap(jaccard_graph_tr, 
                         weights = jaccard_graph_tr$weights,
                         steps = 3,
                         merges = TRUE,
                         modularity = TRUE, 
                         membership = TRUE)

wt_knn = cluster_walktrap(jaccard_graph_knn, 
                          weights = jaccard_graph_knn$weights,
                          steps = 3,
                          merges = TRUE,
                          modularity = TRUE, 
                          membership = TRUE)

Plot

par(mfrow=c(1,2))
plotar(wt_tr, jaccard_graph_tr, "Walktrap threshold")
plotar(wt_knn, jaccard_graph_knn, "Walktrap knn")

Informações

wt_tr
## IGRAPH clustering walktrap, groups: 3, mod: 0.083
## + groups:
##   $`1`
##    [1] "Varied.Thrush"             "Pacific.Wren"             
##    [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
##    [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##    [7] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
##    [9] "Brown.Creeper"             "Red.breasted.Nuthatch"    
##   
##   $`2`
##   [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
##   [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
##   + ... omitted several groups/vertices
wt_knn
## IGRAPH clustering walktrap, groups: 1, mod: 0.05
## + groups:
##   $`1`
##    [1] "Brown.Creeper"             "Pacific.Wren"             
##    [3] "Pacific.slope.Flycatcher"  "Red.breasted.Nuthatch"    
##    [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##    [7] "Hermit.Thrush"             "Chestnut.backed.Chickadee"
##    [9] "Varied.Thrush"             "Hermit.Warbler"           
##   [11] "Swainson.s.Thrush"         "Hammond.s.Flycatcher"     
##   [13] "Western.Tanager"           "Black.headed.Grosbeak"    
##   [15] "Golden.Crowned.Kinglet"    "Warbling.Vireo"           
##   [17] "MacGillivray.s.Warbler"    "Stellar.s.Jay"            
##   + ... omitted several groups/vertices

Membership

membership(wt_tr)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         2                         1 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         1                         2                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         2                         1 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         2                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         2                         1                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         2                         2                         1 
##             Stellar.s.Jay 
##                         3
membership(wt_knn)
##             Brown.Creeper              Pacific.Wren  Pacific.slope.Flycatcher 
##                         1                         1                         1 
##     Red.breasted.Nuthatch           Dark.eyed.Junco    Olive.sided.Flycatcher 
##                         1                         1                         1 
##             Hermit.Thrush Chestnut.backed.Chickadee             Varied.Thrush 
##                         1                         1                         1 
##            Hermit.Warbler         Swainson.s.Thrush      Hammond.s.Flycatcher 
##                         1                         1                         1 
##           Western.Tanager     Black.headed.Grosbeak    Golden.Crowned.Kinglet 
##                         1                         1                         1 
##            Warbling.Vireo    MacGillivray.s.Warbler             Stellar.s.Jay 
##                         1                         1                         1 
##          Common.Nighthawk 
##                         1

Tamanho

sizes(wt_tr)
## Community sizes
##  1  2  3 
## 10  8  1
sizes(wt_knn)
## Community sizes
##  1 
## 19

Modularidade

# tem modularidade maior que o knn
modularity(wt_tr)
## [1] 0.08299859
modularity(wt_knn)
## [1] 0.04986149

Comunidades

communities(wt_tr)
## $`1`
##  [1] "Varied.Thrush"             "Pacific.Wren"             
##  [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
##  [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##  [7] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
##  [9] "Brown.Creeper"             "Red.breasted.Nuthatch"    
## 
## $`2`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
## [7] "Hermit.Warbler"         "Common.Nighthawk"      
## 
## $`3`
## [1] "Stellar.s.Jay"
communities(wt_knn)
## $`1`
##  [1] "Brown.Creeper"             "Pacific.Wren"             
##  [3] "Pacific.slope.Flycatcher"  "Red.breasted.Nuthatch"    
##  [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##  [7] "Hermit.Thrush"             "Chestnut.backed.Chickadee"
##  [9] "Varied.Thrush"             "Hermit.Warbler"           
## [11] "Swainson.s.Thrush"         "Hammond.s.Flycatcher"     
## [13] "Western.Tanager"           "Black.headed.Grosbeak"    
## [15] "Golden.Crowned.Kinglet"    "Warbling.Vireo"           
## [17] "MacGillivray.s.Warbler"    "Stellar.s.Jay"            
## [19] "Common.Nighthawk"

É hierárquico?

is_hierarchical(wt_tr)
## [1] TRUE
is_hierarchical(wt_knn)
## [1] TRUE

Plot TR

dend_wt = as.dendrogram(wt_tr)
hc_wt = as.hclust(wt_tr)
hc_wt$order
##  [1] 19  6 13 17  2  8 11  5 16 14 18  3 15  4  9 10 12  1  7
par(mfrow=c(1,1))
plot_dendrogram(wt_tr)
title(cex.main= 0.8, main = "Dendrogram Walktrap Threshold")

Plot KNN

dend_wt = as.dendrogram(wt_knn)
hc_wt = as.hclust(wt_knn)
hc_wt$order
##  [1]  8 14  5 15  9 17  3  2  4 11  1  7 19 10 12 13  6 16 18
par(mfrow=c(1,1))
plot_dendrogram(wt_knn)
title(cex.main= 0.8, main = "Dendrogram Walktrap Knn")

7.4 Leading Eigenvector

O método baseado na teoria spectral, o qual constrói uma matriz laplaciana e encontra os autovalores e autovetores. Com base nos valores dos autovalores ele faz as divisões em comunidades. Entretanto, existe um truque no algoritmo que é trocar a matriz laplaciana pela matriz da modularidade e só então obter os autovalores e autovetores.

No spectral clustering existem duas opções:

  • Se exitem tem duas comunidades, é só colocar os vértices cujos autovalores são positivos em uma comunidade e os vértices cujos autovalores são negativos em outra comunidade

  • Se existir k comunidades, você roda um kmeans na matriz de autovetores

Portanto, o grafo é dividido em dois de forma que a modularidade é maximizada baseada no autovetor principal. Calcula-se a contribuição da modularidade em casa passo da subdivisão da rede e o algoritmo pára quando o valor da contribuição da mondularidade é não positivo.

De acordo com os autores originais do método, este pode ser considerado um PCA (principal componente analysis) para redes.

Parâmetros

GRAPH: grafo propriamente dito.

STEPS: é o número de tentativas de uma etapa a serem executadas. Não tem utilidade.

WEIGTHS: pesos

START: é um vetor de associação numérica que fornece a configuração inicial do algoritmo. Também pode ser NULL.

OPTIONS: uma lista nomeada para substituir algumas opções ARPACK.

CALLBACK: este parametro é chamado após cada iteração, após calcular o autovetor líder da matriz de modularidade.

EXTRA: parâmetro adicional a ser fornecido à função de retorno de chamada.

ENV: é o ambiente no qual a função de retorno de chamada é avaliada.

Aplicando o método

le_tr = cluster_leading_eigen(jaccard_graph_tr, 
                              weights = jaccard_graph_tr$weights)

le_knn = cluster_leading_eigen(jaccard_graph_knn, 
                               weights = jaccard_graph_knn$weights)

Plot

par(mfrow=c(1,2))
plotar(le_tr, jaccard_graph_tr, "Leading Eigenvector threshold")
plotar(le_knn, jaccard_graph_knn, "Leading Eigenvector knn")

Informações

le_tr
## IGRAPH clustering leading eigenvector, groups: 2, mod: 0.093
## + groups:
##   $`1`
##    [1] "Varied.Thrush"             "Pacific.Wren"             
##    [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
##    [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##    [7] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
##    [9] "Brown.Creeper"             "Red.breasted.Nuthatch"    
##   [11] "Stellar.s.Jay"            
##   
##   $`2`
##   [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
##   + ... omitted several groups/vertices
le_knn
## IGRAPH clustering leading eigenvector, groups: 1, mod: 0
## + groups:
##   $`1`
##    [1] "Brown.Creeper"             "Pacific.Wren"             
##    [3] "Pacific.slope.Flycatcher"  "Red.breasted.Nuthatch"    
##    [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##    [7] "Hermit.Thrush"             "Chestnut.backed.Chickadee"
##    [9] "Varied.Thrush"             "Hermit.Warbler"           
##   [11] "Swainson.s.Thrush"         "Hammond.s.Flycatcher"     
##   [13] "Western.Tanager"           "Black.headed.Grosbeak"    
##   [15] "Golden.Crowned.Kinglet"    "Warbling.Vireo"           
##   [17] "MacGillivray.s.Warbler"    "Stellar.s.Jay"            
##   + ... omitted several groups/vertices

Membership

membership(le_tr)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         2                         1 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         1                         2                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         2                         1 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         2                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         2                         1                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         2                         2                         1 
##             Stellar.s.Jay 
##                         1
membership(le_knn) 
##             Brown.Creeper              Pacific.Wren  Pacific.slope.Flycatcher 
##                         1                         1                         1 
##     Red.breasted.Nuthatch           Dark.eyed.Junco    Olive.sided.Flycatcher 
##                         1                         1                         1 
##             Hermit.Thrush Chestnut.backed.Chickadee             Varied.Thrush 
##                         1                         1                         1 
##            Hermit.Warbler         Swainson.s.Thrush      Hammond.s.Flycatcher 
##                         1                         1                         1 
##           Western.Tanager     Black.headed.Grosbeak    Golden.Crowned.Kinglet 
##                         1                         1                         1 
##            Warbling.Vireo    MacGillivray.s.Warbler             Stellar.s.Jay 
##                         1                         1                         1 
##          Common.Nighthawk 
##                         1

Tamanho

sizes(le_tr)
## Community sizes
##  1  2 
## 11  8
sizes(le_knn)
## Community sizes
##  1 
## 19

Modularidade

# tem maior modularidade
modularity(le_tr)
## [1] 0.09304112
# não tem estrutura de comunidade
modularity(le_knn)
## [1] 0

Comunidades

communities(le_tr)
## $`1`
##  [1] "Varied.Thrush"             "Pacific.Wren"             
##  [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
##  [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##  [7] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
##  [9] "Brown.Creeper"             "Red.breasted.Nuthatch"    
## [11] "Stellar.s.Jay"            
## 
## $`2`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
## [7] "Hermit.Warbler"         "Common.Nighthawk"
communities(le_knn)
## $`1`
##  [1] "Brown.Creeper"             "Pacific.Wren"             
##  [3] "Pacific.slope.Flycatcher"  "Red.breasted.Nuthatch"    
##  [5] "Dark.eyed.Junco"           "Olive.sided.Flycatcher"   
##  [7] "Hermit.Thrush"             "Chestnut.backed.Chickadee"
##  [9] "Varied.Thrush"             "Hermit.Warbler"           
## [11] "Swainson.s.Thrush"         "Hammond.s.Flycatcher"     
## [13] "Western.Tanager"           "Black.headed.Grosbeak"    
## [15] "Golden.Crowned.Kinglet"    "Warbling.Vireo"           
## [17] "MacGillivray.s.Warbler"    "Stellar.s.Jay"            
## [19] "Common.Nighthawk"

É hierárquico?

is_hierarchical(le_tr)
## [1] TRUE
dend_le = as.dendrogram(le_tr)
hc_le = as.hclust(le_tr)
hc_le$order
##  [1]  7  8  9 10 11 12 13 14 15 16 17 18 19  1  2  3  4  5  6

Plot

par(mfrow=c(1,1))
plot_dendrogram(le_tr)
title(cex.main= 0.8, main = "Dendrogram Leading \n Eigenvector Treshold")

7.5 Optimal

O objetivo do método é encontrar agrupamentos com máxima modularidade produzindo partições ótimas. O método é baseado em conceitos de algoritmo de agrupamento hierárquico: começa com um único grupo e iterativamente mescla dois grupos que tem a maior modularidade. Depois de n-1 fusões, o agrupamento que alcançar a mais alta modularidade é retornada.

Parâmetros

GRAPH: grafo

WEIGTHS: pesos

Aplicando o método

op_tr = cluster_optimal(jaccard_graph_tr, 
                        weights = jaccard_graph_tr$weights)

op_knn = cluster_optimal(jaccard_graph_knn, 
                        weights = jaccard_graph_knn$weights)

Plotando

par(mfrow=c(1,2))
plotar(op_tr, jaccard_graph_tr, "Optimal threshold")
plotar(op_knn, jaccard_graph_knn, "Optimal Eigenvector knn")

Informações

op_tr
## IGRAPH clustering optimal, groups: 3, mod: 0.098
## + groups:
##   $`1`
##   [1] "Varied.Thrush"             "Pacific.Wren"             
##   [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
##   [5] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
##   [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
##   
##   $`2`
##   [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
##   [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
##   [7] "Hermit.Warbler"         "Common.Nighthawk"      
##   + ... omitted several groups/vertices
op_knn
## IGRAPH clustering optimal, groups: 19, mod: 0
## + groups:
##   $`1`
##   [1] "Brown.Creeper"
##   
##   $`2`
##   [1] "Pacific.Wren"
##   
##   $`3`
##   [1] "Pacific.slope.Flycatcher"
##   
##   $`4`
##   + ... omitted several groups/vertices

Membership

membership(op_tr)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         2                         1 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         1                         2                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         2                         3 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         2                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         2                         3                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         2                         2                         1 
##             Stellar.s.Jay 
##                         3
membership(op_knn)
##             Brown.Creeper              Pacific.Wren  Pacific.slope.Flycatcher 
##                         1                         2                         3 
##     Red.breasted.Nuthatch           Dark.eyed.Junco    Olive.sided.Flycatcher 
##                         4                         5                         6 
##             Hermit.Thrush Chestnut.backed.Chickadee             Varied.Thrush 
##                         7                         8                         9 
##            Hermit.Warbler         Swainson.s.Thrush      Hammond.s.Flycatcher 
##                        10                        11                        12 
##           Western.Tanager     Black.headed.Grosbeak    Golden.Crowned.Kinglet 
##                        13                        14                        15 
##            Warbling.Vireo    MacGillivray.s.Warbler             Stellar.s.Jay 
##                        16                        17                        18 
##          Common.Nighthawk 
##                        19

Tamanho

sizes(op_tr)
## Community sizes
## 1 2 3 
## 8 8 3
sizes(op_knn)
## Community sizes
##  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 
##  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

Modularidade

# tem maior modularidade
modularity(op_tr)
## [1] 0.09812146
# não tem estrutura de comunidade
modularity(op_knn)
## [1] 0

Comunidades

communities(op_tr)
## $`1`
## [1] "Varied.Thrush"             "Pacific.Wren"             
## [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
## [5] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
## [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
## 
## $`2`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
## [7] "Hermit.Warbler"         "Common.Nighthawk"      
## 
## $`3`
## [1] "Dark.eyed.Junco" "Warbling.Vireo"  "Stellar.s.Jay"
communities(op_knn)
## $`1`
## [1] "Brown.Creeper"
## 
## $`2`
## [1] "Pacific.Wren"
## 
## $`3`
## [1] "Pacific.slope.Flycatcher"
## 
## $`4`
## [1] "Red.breasted.Nuthatch"
## 
## $`5`
## [1] "Dark.eyed.Junco"
## 
## $`6`
## [1] "Olive.sided.Flycatcher"
## 
## $`7`
## [1] "Hermit.Thrush"
## 
## $`8`
## [1] "Chestnut.backed.Chickadee"
## 
## $`9`
## [1] "Varied.Thrush"
## 
## $`10`
## [1] "Hermit.Warbler"
## 
## $`11`
## [1] "Swainson.s.Thrush"
## 
## $`12`
## [1] "Hammond.s.Flycatcher"
## 
## $`13`
## [1] "Western.Tanager"
## 
## $`14`
## [1] "Black.headed.Grosbeak"
## 
## $`15`
## [1] "Golden.Crowned.Kinglet"
## 
## $`16`
## [1] "Warbling.Vireo"
## 
## $`17`
## [1] "MacGillivray.s.Warbler"
## 
## $`18`
## [1] "Stellar.s.Jay"
## 
## $`19`
## [1] "Common.Nighthawk"

É hierárquico?

is_hierarchical(op_tr)
## [1] FALSE
is_hierarchical(op_knn)
## [1] FALSE

7.6 Louvain

O algoritmo é composto por duas fases que são repetidas iterativamente. O algoritmo encontra comunidades hierarquicas.

Fase 1:

  • Começa com cada vértice em uma comunidade diferente (cada vértice é uma comunidade)

  • Para cada vértice, considere os j vértices vizinhos do vértice i.

  • Avalie o ganho da modularidade quando i é removido de sua comunidade e colocado na comunidade j

  • O vértice i é então fixado na comunidade para a qual o ganho da modularidade é máximo e positivo

  • Se não há ganho positivo, i permance na comunidade original.

  • Esse processo se repete e só pára quando um máximo local da modularidade é alcançado, ou seja, quando nenhum movimento de vértice é capaz de maximizar a modularidade

Fase 2:

  • Consiste em construir a rede cujos nós são as comunidades encontradas na primeira fase

Parâmetros

GRAPH: grafo.

WEIGTHS: pesos

Aplicando o método

lo_tr = cluster_louvain(jaccard_graph_tr, 
                        weights = jaccard_graph_tr$weights)

lo_knn = cluster_louvain(jaccard_graph_knn, 
                        weights = jaccard_graph_knn$weights)

Plol

par(mfrow=c(1,2))
plotar(lo_tr, jaccard_graph_tr, "Louvain threshold")
plotar(lo_knn, jaccard_graph_knn, "Louvain Eigenvector knn")

Informações

lo_tr
## IGRAPH clustering multi level, groups: 3, mod: 0.097
## + groups:
##   $`1`
##   [1] "Varied.Thrush"             "Pacific.Wren"             
##   [3] "Pacific.slope.Flycatcher"  "Olive.sided.Flycatcher"   
##   [5] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
##   [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
##   [9] "Stellar.s.Jay"            
##   
##   $`2`
##   [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
##   [4] "Hermit.Thrush"          "MacGillivray.s.Warbler" "Hermit.Warbler"        
##   + ... omitted several groups/vertices
lo_knn
## IGRAPH clustering multi level, groups: 19, mod: 8.2e-18
## + groups:
##   $`1`
##   [1] "Brown.Creeper"
##   
##   $`2`
##   [1] "Pacific.Wren"
##   
##   $`3`
##   [1] "Pacific.slope.Flycatcher"
##   
##   $`4`
##   + ... omitted several groups/vertices

Membros de cada comunidade

membership(lo_tr)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         2                         1 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         3                         2                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         2                         3 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         3                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         2                         1                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         2                         2                         1 
##             Stellar.s.Jay 
##                         1
membership(lo_knn)
##             Brown.Creeper              Pacific.Wren  Pacific.slope.Flycatcher 
##                         1                         2                         3 
##     Red.breasted.Nuthatch           Dark.eyed.Junco    Olive.sided.Flycatcher 
##                         4                         5                         6 
##             Hermit.Thrush Chestnut.backed.Chickadee             Varied.Thrush 
##                         7                         8                         9 
##            Hermit.Warbler         Swainson.s.Thrush      Hammond.s.Flycatcher 
##                        10                        11                        12 
##           Western.Tanager     Black.headed.Grosbeak    Golden.Crowned.Kinglet 
##                        13                        14                        15 
##            Warbling.Vireo    MacGillivray.s.Warbler             Stellar.s.Jay 
##                        16                        17                        18 
##          Common.Nighthawk 
##                        19

As comunidades tem tamanhos diferentes

sizes(lo_tr)
## Community sizes
## 1 2 3 
## 9 7 3
sizes(lo_knn)
## Community sizes
##  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 
##  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

O primeiro grafo tem maior modularidade

modularity(lo_tr)
## [1] 0.09682183
modularity(lo_knn)
## [1] 8.239937e-18

Grupos

communities(lo_tr)
## $`1`
## [1] "Varied.Thrush"             "Pacific.Wren"             
## [3] "Pacific.slope.Flycatcher"  "Olive.sided.Flycatcher"   
## [5] "Chestnut.backed.Chickadee" "Warbling.Vireo"           
## [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
## [9] "Stellar.s.Jay"            
## 
## $`2`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "MacGillivray.s.Warbler" "Hermit.Warbler"        
## [7] "Common.Nighthawk"      
## 
## $`3`
## [1] "Hammond.s.Flycatcher" "Dark.eyed.Junco"      "Western.Tanager"
communities(lo_knn)
## $`1`
## [1] "Brown.Creeper"
## 
## $`2`
## [1] "Pacific.Wren"
## 
## $`3`
## [1] "Pacific.slope.Flycatcher"
## 
## $`4`
## [1] "Red.breasted.Nuthatch"
## 
## $`5`
## [1] "Dark.eyed.Junco"
## 
## $`6`
## [1] "Olive.sided.Flycatcher"
## 
## $`7`
## [1] "Hermit.Thrush"
## 
## $`8`
## [1] "Chestnut.backed.Chickadee"
## 
## $`9`
## [1] "Varied.Thrush"
## 
## $`10`
## [1] "Hermit.Warbler"
## 
## $`11`
## [1] "Swainson.s.Thrush"
## 
## $`12`
## [1] "Hammond.s.Flycatcher"
## 
## $`13`
## [1] "Western.Tanager"
## 
## $`14`
## [1] "Black.headed.Grosbeak"
## 
## $`15`
## [1] "Golden.Crowned.Kinglet"
## 
## $`16`
## [1] "Warbling.Vireo"
## 
## $`17`
## [1] "MacGillivray.s.Warbler"
## 
## $`18`
## [1] "Stellar.s.Jay"
## 
## $`19`
## [1] "Common.Nighthawk"

Não são hierárquicos

is_hierarchical(lo_tr)
## [1] FALSE
is_hierarchical(lo_knn)
## [1] FALSE

7.7 Spinglass

No artigo original, o autores mostraram que detecção de comunidades podem ser mapeados de forma a encontrar o estado fundamental de um spin glass de Potts de alcance infinito a partir de um ansatz de um parâmetro muito simples e geral, que também é válido para redes ponderadas e redes direcionadas.

Portanto, a estrutura é interpretada como uma nova configuração de glass que minimiza a energia do spin glass com o estado do glass sendo os índices das comunidades. Ao usar modelos de rotação para agrupamento, as medidas de similaridaes são traduzidas em forças e propriedades dinâmicas tais como correlações spin-spin que são medidas ou energias interpretadas como funções de qualidade.

Assim, os métodos de detecção de comunidade podem ser mapeados para encontrar o estado verdadeiro de um spin glass de Potts de faixa infinita via o princípio de anatz e combinando informações ausentes e presentes.

A energia do sistema de rotação é equivalente à função de qualifidade do agrupamento com o estado da rotação sendo o indice do grupo.

Parametros

GRAPH: grafo

WEIGHTS: pesos

VERTEX: se deve ser calculada a comunidade de um determinado vértice sem calcular todas as comunidades. Observe que, se este argumento estiver presente, alguns outros argumentos serão ignorados.

SPINS: é o número de giros a serem usados. Este é o limite máximo para o número de comunidades. Não é um problema fornecer um número (razoavelmente) grande aqui, caso em que alguns estados de spin não serão preenchidos.

PARAUPDATE: indica se os spins dos vértices devem ser atualizados em paralelo de forma síncrona ou não. Este argumento é ignorado se o parâmetro VERTEX estiver presente. Também não é implementado na opção “neg”.

START.TEMP: é a temperatura inicial. Se o parâmetro VERTEX estiver presente então este parametro é ignorado.

STOP.TEMP: é a temperatura de parada. A simulação termina se a temperatura cair abaixo deste nível. Se o parâmetro VERTEX estiver presente então este parametro é ignorado.

COOL.FACT: fator de resfriamento para o recozimento simulado. Se o parâmetro VERTEX estiver presente então este parametro é ignorado.

UPDATE.RULE: tipo de grafo a ser usado dado o modelo nulo da simulação. O valor Simples usa um grafo aleatório com o mesmo número de arestas que a probabilidade da linha de base. O valor Config usa um grafo aleatório com os mesmos graus de vértice do gráfico de entrada.

GAMMA: este parametro numérico especifica o equilíbrio entre a importância das bordas presentes e não presentes em uma comunidade. O valor padrão 1.0 torna os links existentes e não existentes igualmente importantes. Valores menores tornam os links existentes, valores maiores tornam os links ausentes mais importantes.

IMPLEMENTANTION: é o tipo de implementação do algoritmo que se deseja usar. A original é mais rápida e é o padrão sendo indicada por orig. A segunda leva em consideração pesos negativos sendo indicada por neg

GAMMA.MINUS: este parâmetro numérico especifica o equilíbrio entre a importância das arestas ponderadas negativas presentes e não presentes em uma comunidade. Valores menores levam a comunidades com menor intra-conectividade negativa. Se este argumento for definido como zero, o algoritmo se reduz a um algoritmo de coloração de grafo, usando o número de spins como o número de cores. Este argumento é ignorado se a implementação original for escolhida.

Aplicando o método

sc1 = spinglass.community(jaccard_graph_tr,
                          weights = jaccard_graph_tr$weights_cond_prob,
                          implementation = "orig", 
                          update.rule = "config")

sc2 = spinglass.community(jaccard_graph_tr, 
                          weights = jaccard_graph_tr$weights_cond_prob,
                          implementation = "orig", 
                          update.rule = "random")

sc3 = spinglass.community(jaccard_graph_tr,
                          weights = jaccard_graph_tr$weights_cond_prob,
                          implementation = "orig", 
                          update.rule = "simple")

sc4 = spinglass.community(jaccard_graph_tr, 
                          weights = jaccard_graph_tr$weights_cond_prob,
                          implementation = "neg", 
                          update.rule = "config")

sc5  = spinglass.community(jaccard_graph_tr, 
                           weights = jaccard_graph_tr$weights_cond_prob,
                           implementation = "neg", 
                           update.rule = "random")

sc6 = spinglass.community(jaccard_graph_tr, 
                          weights = jaccard_graph_tr$weights_cond_prob,
                          implementation = "neg", 
                          update.rule = "simple")

Plots

par(mfrow=c(1,2))
plotar(sc1, jaccard_graph_tr, "Spinglass TR OR CO")
plotar(sc2, jaccard_graph_tr, "Spinglass TR OR RA")

par(mfrow=c(1,2))
plotar(sc3, jaccard_graph_tr, "Spinglass TR OR SI")
plotar(sc4, jaccard_graph_tr, "Spinglass TR NE CO")

par(mfrow=c(1,2))
plotar(sc5, jaccard_graph_tr, "Spinglass TR NE RA")
plotar(sc6, jaccard_graph_tr, "Spinglass TR NE SI")

Informações das comunidades

sc1
## IGRAPH clustering spinglass, groups: 3, mod: 0.15
## + groups:
##   $`1`
##   [1] "Dark.eyed.Junco" "Warbling.Vireo"  "Stellar.s.Jay"  
##   
##   $`2`
##   [1] "Varied.Thrush"             "Pacific.Wren"             
##   [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
##   [5] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
##   [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
##   
##   $`3`
##   + ... omitted several groups/vertices
sc2
## IGRAPH clustering spinglass, groups: 19, mod: -0.015
## + groups:
##   $`1`
##   [1] "Olive.sided.Flycatcher"
##   
##   $`2`
##   [1] "Common.Nighthawk"
##   
##   $`3`
##   [1] "Black.headed.Grosbeak"
##   
##   $`4`
##   + ... omitted several groups/vertices
sc3
## IGRAPH clustering spinglass, groups: 19, mod: -0.015
## + groups:
##   $`1`
##   [1] "Western.Tanager"
##   
##   $`2`
##   [1] "Stellar.s.Jay"
##   
##   $`3`
##   [1] "Dark.eyed.Junco"
##   
##   $`4`
##   + ... omitted several groups/vertices
sc4
## IGRAPH clustering spinglass, groups: 3, mod: 0.098
## + groups:
##   $`1`
##   [1] "Varied.Thrush"             "Pacific.slope.Flycatcher" 
##   [3] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
##   [5] "Warbling.Vireo"            "Brown.Creeper"            
##   [7] "Red.breasted.Nuthatch"    
##   
##   $`2`
##   [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
##   [4] "Hermit.Thrush"          "Dark.eyed.Junco"        "Western.Tanager"       
##   [7] "MacGillivray.s.Warbler" "Hermit.Warbler"         "Common.Nighthawk"      
##   + ... omitted several groups/vertices
sc5
## IGRAPH clustering spinglass, groups: 3, mod: 0.098
## + groups:
##   $`1`
##   [1] "Varied.Thrush"             "Pacific.slope.Flycatcher" 
##   [3] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
##   [5] "Warbling.Vireo"            "Brown.Creeper"            
##   [7] "Red.breasted.Nuthatch"    
##   
##   $`2`
##   [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
##   [4] "Hermit.Thrush"          "Dark.eyed.Junco"        "Western.Tanager"       
##   [7] "MacGillivray.s.Warbler" "Hermit.Warbler"         "Common.Nighthawk"      
##   + ... omitted several groups/vertices
sc6
## IGRAPH clustering spinglass, groups: 3, mod: 0.098
## + groups:
##   $`1`
##   [1] "Varied.Thrush"             "Pacific.Wren"             
##   [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
##   [5] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
##   [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
##   
##   $`2`
##   [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
##   [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
##   [7] "Hermit.Warbler"         "Common.Nighthawk"      
##   + ... omitted several groups/vertices

Informações de membership

membership(sc1)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         2                         3                         2 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         2                         3                         3 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         2                         3                         1 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         2                         3                         2 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         3                         1                         2 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         3                         3                         2 
##             Stellar.s.Jay 
##                         1
membership(sc2)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                        16                        18                        13 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                        12                         5                         3 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         8                        14                        19 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                        15                         6 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         9                        11                        17 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         7                         2                         4 
##             Stellar.s.Jay 
##                        10
membership(sc3)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                        16                        19                        15 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                        18                        12                        17 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         9                        11                         3 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         7                         1                        13 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                        14                         6                        10 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         5                         8                         4 
##             Stellar.s.Jay 
##                         2
membership(sc4)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         2                         3 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         3                         2                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         2                         2 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         2                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         2                         1                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         2                         2                         1 
##             Stellar.s.Jay 
##                         3
membership(sc5)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         2                         3 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         3                         2                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         2                         2 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         2                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         2                         1                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         2                         2                         1 
##             Stellar.s.Jay 
##                         3
membership(sc6)
##             Varied.Thrush    Golden.Crowned.Kinglet              Pacific.Wren 
##                         1                         2                         1 
##      Hammond.s.Flycatcher         Swainson.s.Thrush     Black.headed.Grosbeak 
##                         1                         2                         2 
##  Pacific.slope.Flycatcher             Hermit.Thrush           Dark.eyed.Junco 
##                         1                         2                         3 
##    Olive.sided.Flycatcher           Western.Tanager Chestnut.backed.Chickadee 
##                         1                         2                         1 
##    MacGillivray.s.Warbler            Warbling.Vireo             Brown.Creeper 
##                         2                         3                         1 
##            Hermit.Warbler          Common.Nighthawk     Red.breasted.Nuthatch 
##                         2                         2                         1 
##             Stellar.s.Jay 
##                         3

Informações de tamanho

sizes(sc1)
## Community sizes
## 1 2 3 
## 3 8 8
sizes(sc2)
## Community sizes
##  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 
##  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
sizes(sc3)
## Community sizes
##  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 
##  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
sizes(sc4)
## Community sizes
## 1 2 3 
## 7 9 3
sizes(sc5)
## Community sizes
## 1 2 3 
## 7 9 3
sizes(sc6)
## Community sizes
## 1 2 3 
## 8 8 3

Informações de modularidade

# entre as 6 comunidades esta obteve a melhor qualidade
modularity(sc1) 
## [1] 0.1522478
# valor negativo: péssima qualidade de particionamento 
modularity(sc2) 
## [1] -0.01537394
# valor negativo: péssima qualidade de particionamento 
modularity(sc3)
## [1] -0.01537394
# no geral, as modularidades foram baixas, muito próximas de zero
# isso indica que a qualidade dos particionamentos não são muito boas
# quanto mais próximo de 1 melhor
# valores normais ficam entre 0.3 e 0.7
modularity(sc4)
## [1] 0.09764887
modularity(sc5)
## [1] 0.09764887
modularity(sc6)
## [1] 0.09812146

Grupos

communities(sc1)
## $`1`
## [1] "Dark.eyed.Junco" "Warbling.Vireo"  "Stellar.s.Jay"  
## 
## $`2`
## [1] "Varied.Thrush"             "Pacific.Wren"             
## [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
## [5] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
## [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
## 
## $`3`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
## [7] "Hermit.Warbler"         "Common.Nighthawk"
communities(sc2)
## $`1`
## [1] "Olive.sided.Flycatcher"
## 
## $`2`
## [1] "Common.Nighthawk"
## 
## $`3`
## [1] "Black.headed.Grosbeak"
## 
## $`4`
## [1] "Red.breasted.Nuthatch"
## 
## $`5`
## [1] "Swainson.s.Thrush"
## 
## $`6`
## [1] "Chestnut.backed.Chickadee"
## 
## $`7`
## [1] "Hermit.Warbler"
## 
## $`8`
## [1] "Pacific.slope.Flycatcher"
## 
## $`9`
## [1] "MacGillivray.s.Warbler"
## 
## $`10`
## [1] "Stellar.s.Jay"
## 
## $`11`
## [1] "Warbling.Vireo"
## 
## $`12`
## [1] "Hammond.s.Flycatcher"
## 
## $`13`
## [1] "Pacific.Wren"
## 
## $`14`
## [1] "Hermit.Thrush"
## 
## $`15`
## [1] "Western.Tanager"
## 
## $`16`
## [1] "Varied.Thrush"
## 
## $`17`
## [1] "Brown.Creeper"
## 
## $`18`
## [1] "Golden.Crowned.Kinglet"
## 
## $`19`
## [1] "Dark.eyed.Junco"
communities(sc3)
## $`1`
## [1] "Western.Tanager"
## 
## $`2`
## [1] "Stellar.s.Jay"
## 
## $`3`
## [1] "Dark.eyed.Junco"
## 
## $`4`
## [1] "Red.breasted.Nuthatch"
## 
## $`5`
## [1] "Hermit.Warbler"
## 
## $`6`
## [1] "Warbling.Vireo"
## 
## $`7`
## [1] "Olive.sided.Flycatcher"
## 
## $`8`
## [1] "Common.Nighthawk"
## 
## $`9`
## [1] "Pacific.slope.Flycatcher"
## 
## $`10`
## [1] "Brown.Creeper"
## 
## $`11`
## [1] "Hermit.Thrush"
## 
## $`12`
## [1] "Swainson.s.Thrush"
## 
## $`13`
## [1] "Chestnut.backed.Chickadee"
## 
## $`14`
## [1] "MacGillivray.s.Warbler"
## 
## $`15`
## [1] "Pacific.Wren"
## 
## $`16`
## [1] "Varied.Thrush"
## 
## $`17`
## [1] "Black.headed.Grosbeak"
## 
## $`18`
## [1] "Hammond.s.Flycatcher"
## 
## $`19`
## [1] "Golden.Crowned.Kinglet"
communities(sc4)
## $`1`
## [1] "Varied.Thrush"             "Pacific.slope.Flycatcher" 
## [3] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
## [5] "Warbling.Vireo"            "Brown.Creeper"            
## [7] "Red.breasted.Nuthatch"    
## 
## $`2`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "Dark.eyed.Junco"        "Western.Tanager"       
## [7] "MacGillivray.s.Warbler" "Hermit.Warbler"         "Common.Nighthawk"      
## 
## $`3`
## [1] "Pacific.Wren"         "Hammond.s.Flycatcher" "Stellar.s.Jay"
communities(sc5)
## $`1`
## [1] "Varied.Thrush"             "Pacific.slope.Flycatcher" 
## [3] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
## [5] "Warbling.Vireo"            "Brown.Creeper"            
## [7] "Red.breasted.Nuthatch"    
## 
## $`2`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "Dark.eyed.Junco"        "Western.Tanager"       
## [7] "MacGillivray.s.Warbler" "Hermit.Warbler"         "Common.Nighthawk"      
## 
## $`3`
## [1] "Pacific.Wren"         "Hammond.s.Flycatcher" "Stellar.s.Jay"
communities(sc6)
## $`1`
## [1] "Varied.Thrush"             "Pacific.Wren"             
## [3] "Hammond.s.Flycatcher"      "Pacific.slope.Flycatcher" 
## [5] "Olive.sided.Flycatcher"    "Chestnut.backed.Chickadee"
## [7] "Brown.Creeper"             "Red.breasted.Nuthatch"    
## 
## $`2`
## [1] "Golden.Crowned.Kinglet" "Swainson.s.Thrush"      "Black.headed.Grosbeak" 
## [4] "Hermit.Thrush"          "Western.Tanager"        "MacGillivray.s.Warbler"
## [7] "Hermit.Warbler"         "Common.Nighthawk"      
## 
## $`3`
## [1] "Dark.eyed.Junco" "Warbling.Vireo"  "Stellar.s.Jay"

É hierárquico

is_hierarchical(sc1)
## [1] FALSE
is_hierarchical(sc2)
## [1] FALSE
is_hierarchical(sc3)
## [1] FALSE
is_hierarchical(sc4)
## [1] FALSE
is_hierarchical(sc5)
## [1] FALSE
is_hierarchical(sc6)
## [1] FALSE

7.8 Fast Greedy

8 Tutoriais e Códigos Fonte

  1. Tutorial sobre como calcular medidas de similaridades no espaço de rótulos na Classificação Multirrótulo
  1. Tutorial sobre como calcular as medidas de avaliação da Classificação Multirrótulo
  1. Código para gerar X-Fold Cross Validation para Classificação Multirrótulo:
  1. Código deste Tutorial:
  1. Meu site com informações de outras publicações técnicas e cienticas:

9 Referências

Silva, T. C.; Zhao, L. Machine Learning in Complex Networks (1st. ed.). Springer Publishing Company, Incorporated. 2016. https://dl.acm.org/doi/book/10.5555/2898937

Freeman, L.C. (1979). Centrality in Social Networks I: Conceptual Clarification. Social Networks, 1, 215-239. https://www.sciencedirect.com/science/article/abs/pii/0378873378900217

Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001. https://www.tandfonline.com/doi/abs/10.1080/0022250X.2001.9990249

Bonacich, P. (1987). Power and Centrality: A Family of Measures. American Journal of Sociology, 92, 1170-1182. https://www.jstor.org/stable/2780000

Clauset, A.; Newman, M. E. J. & Moore, C. Finding community structure in very large networks, Physical Review E 2004, 70, 066111. https://arxiv.org/abs/cond-mat/0408187

Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre: Fast unfolding of communities in large networks. J. Stat. Mech. (2008) P10008. https://arxiv.org/abs/0803.0476

J. Reichardt and S. Bornholdt: Statistical Mechanics of Community Detection, Phys. Rev. E, 74, 016110 (2006), https://arxiv.org/abs/cond-mat/0603718

M. E. J. Newman and M. Girvan: Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004) https://arxiv.org/abs/cond-mat/0308217

V.A. Traag and Jeroen Bruggeman: Community detection in networks with positive and negative links, https://arxiv.org/abs/0811.2329 (2008).

Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner: On Modularity Clustering, IEEE Transactions on Knowledge and Data Engineering 20(2):172-188, 2008. https://ieeexplore.ieee.org/document/4358966

MEJ Newman: Finding community structure using the eigenvectors of matrices, Physical Review E 74 036104, 2006. https://arxiv.org/abs/physics/0605087

Javed, M. A., Younis, M. S., Latif, S., Qadir, J., & Baig, A. (2018). Community detection in networks: A multidisciplinary review. Journal of Network and Computer Applications, 108(January), 87–111. https://doi.org/10.1016/j.jnca.2018.02.011

Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76, 036106. (2007) https://arxiv.org/abs/0709.2938

Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, https://arxiv.org/abs/physics/0512106

Yang, Z., Algesheimer, R., & Tessone, C. J. (2016). A comparative analysis of community detection algorithms on artificial networks. Scientific Reports, 6(March). https://doi.org/10.1038/srep30750

Smith, N. R., Zivich, P. N., Frerichs, L. M., Moody, J., & Aiello, A. E. (2020). A Guide for Choosing Community Detection Algorithms in Social Network Studies: The Question Alignment Approach. American Journal of Preventive Medicine, 59(4), 597–605. https://doi.org/10.1016/j.amepre.2020.04.015

Huang, X., Chen, D., Ren, T., & Wang, D. (2020). A survey of community detection methods in multilayer networks. In Data Mining and Knowledge Discovery. Springer US. https://doi.org/10.1007/s10618-020-00716-6

Mittal, R., & Bhatia, M. P. S. (2020). Classification and Comparative Evaluation of Community Detection Algorithms. Archives of Computational Methods in Engineering, 0123456789. https://doi.org/10.1007/s11831-020-09421-5

Resende, V. H., & Carneiro, M. G. (2019). Towards a high-level multi-label classification from complex networks. Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, 2019-November(Cml), 1140–1147. https://doi.org/10.1109/ICTAI.2019.00159