DETECÇÃO DE COMUNIDADES
TAIA
Hugo de Lima Santos (hls3)
ROTEIRO

Motivação

Conceitos

Algoritmos

Caso de uso no mundo real
MOTIVAÇÃO
 Redes
complexas modelam as redes
existentes no mundo real
 Obter
características da rede, sem invadir
a privacidade
 Em
redes sociais, as comunidades
representam grupo de pessoas reais.
Logo...
MOTIVAÇÃO
 Descobrindo
os nós mais importantes da
rede, pode-se analisar mais facilmente o
tráfego na rede.
 Nós
que ligam comunidades diferentes
têm grande importância no mundo real
(redes de contágio)
CONCEITOS
 Assortative
Mixing
Tendência que nós tem de se
relacionar com nós semelhantes a eles.

 K-core

Maior sub grafo de uma rede, onde
todos nós possuem ao menos k ligações
CONCEITOS
 Caminho

Geodésico
(próxima página.)
CONCEITOS
MEDIDA DE CENTRALIDADE

Degree


Geral
Grafos direcionado
 Indregree
 Outdegree
MEDIDAS DE CENTRALIDADE

Betweeness


Importância do vértice, no controle do fluxo
de informação
Fração dos Caminhos Geosédicos, que
passam pelo vértice
MEDIDAS DE CENTRALIDADE

Closeness


Grau de proximidade de um vértice, em
relação aos outros vértices do grafo
É calculado através da distância média do
vértice em questão, até os outros
MEDIDA DE DENSIDADE

Coeficiente de Clustering


Local: Mede o quão perto um vértice está de
se tornar um clique
Probabilidade de dois amigos meus se
conhecerem é maior do que duas pessoas
aleatórias
COMUNIDADES...

Sub-redes de uma rede maior

Alto grau de conexões entre vértices de
uma mesma comunidade

Baixo grau de conexões entre vértices de
comunidades diferentes
COMUNIDADES...
Detecção de
Comunidades
DETECÇÃO DE COMUNIDADES

Clustering Particional

Clustering Hierarquical
DETECÇÃO DE COMUNIDADES

Clustering Particional

K-Means


Muito simples de ser implementado
Necessita de capacidade computacional
moderada
DETECÇÃO DE COMUNIDADES

K-Means

Algoritmo:

1 – São definidas K partições

2 – É calculado o centróide de cada uma delas


3 – Reorganizam-se os nós, de acordo com os
centróides mais próximos
4 – Volta para 2, até que a rede permaneça estável
DETECÇÃO DE COMUNIDADES

K-Means

Problemas:

Depende do K arbitrado
Depende da configuração inicial das
comunidades geradas

DETECÇÃO DE COMUNIDADES

K-Means

Algumas variações foram
desenvolvidas

Ex: Definir K como raiz quadrada da
metade de N
DETECÇÃO DE COMUNIDADES

Clustering Hierárquico

Girvan-Newman
DETECÇÃO DE COMUNIDADES

Girvan-Newman

Divisivo

A cada passo, uma aresta é excluída

A escolha da aresta é feita através do Edge
Betweenness
DETECÇÃO DE COMUNIDADES

Girvan-Newman

Para calcular o edge betweennes:
Shortest-path
Random-walk
Current-flow

DETECÇÃO DE COMUNIDADES

Girvan-Newman

A cada retirada de uma arestas, será gerado
uma nova configuração da rede.

Após atingir a condição de parada, teremos as
nossas comunidades
GIRVAN-NEWMAN

Algoritmo
Calcular Edge Betweennes para cada aresta da
rede



Remover aresta com maior Edge Betweennes
Recalcular Edge Betweennes para arestas
restantes (!)
 Repete
até que a condição de parada seja atingida
GIRVAN-NEWMAN

Dendrograma

A cada iteração do algoritmo é gerado um
dendrograma
Árvore binária que sinaliza cada remoção que
aconteceu na rede

DENDROGRAMA
GIRVAN-NEWMAN

Questões:
Como decidir qual a hora de parar de
tirar arestas da rede?

Quando as comunidades encontradas
são boas o suficiente?

GIRVAN-NEWMAN

Solução:

Modularidade!
Medida da qualidade da rede gerada,
em relação as comunidades existentes

GIRVAN-NEWMAN

Modularidade:
Deve ser calculado a cada evolução do
dendrograma

No final do processo, escolhemos o
maior Q

Com maior Q, temos a melhor divisão
da rede em comunidades

GIRVAN-NEWMAN

Modularidade:

Dada rede com K comunidades

Define uma matriz K x K
E(i,j) corresponde a fração de arestas
que ligam elementos de (i) aos de (k)

CALCULANDO O TRAÇO DA MATRIZ
GIRVAN-NEWMAN

Traço da Matriz
Corresponde
a fração das arestas da rede que
ligam nós de uma mesma comunidade.
Boa
divisão das comunidades acarreta em alto
valor de Tr.
Porém
usar SÓ essa medição é pobre. Rede com
apenas 1 comunidade tem Tr = 1
GIRVAN-NEWMAN

Logo...
 Definição
de mais uma medida:
GIRVAN-NEWMAN

Corresponde a somatória de todas
arestas que possuem pelo menos um
vértice da comunidade (i)
 Com
esse novo valor, podemos recalcular a
modularidade...
GIRVAN-NEWMAN


Calculando a modularidade:
|e²| = Valor calculado baseado na geração aleatória de
uma matriz correspondente a nossa
GIRVAN-NEWMAN

Exemplo prático...
GIRVAN-NEWMAN
CASO DE ESTUDO REAL

Academia Zacharty’s

Década de 1970

Dois anos de observação...
CASO DE ESTUDO REAL


Durante o experimento, a academia foi
dividida em duas
Uma formada pelo antigo dono


Outra formada pelo antigo professor


(#1)
(#33)
Os alunos se dividiram de acordo com a
proximidade com o novo chefe
CASO DE ESTUDO REAL
CASO DE ESTUDO REAL
 Aplicaram-se três configurações diferentes do
algoritmo de Girvan-Newman
Shortest path
 Ramdom walk
 Shortest path – sem recálculo

CASO DE ESTUDO REAL - RESULTADOS
CONCLUSÃO
 Algoritmos de clustering particional são mais
rápidos, porém pouco precisos.


K-means
Algoritmos de clustering hierárquico são mais
eficientes e precisos
Girvan-Newman
 Recalculo essencial para bons resultados


Usando shortest path, conseguimos resultados
mais confiáveis para redes conhecidas
(verificáveis)
CONCLUSÃO
 Para
redes não conhecidas, podemos usar
modularidade para gerar comunidades

Dúvidas ?
REFERÊNCIAS
 Newman
M, Girvan M. Finding and
evaluating community structure in
networks. August 2003
 M. E. J. Newman, Phys. Rev. E 64,
016132. 2001.
 U. Brandes, J. Math. Sociol. 25, 163.
2001.
 http://www.public.asu.edu/~huanliu/dmml
_presentation/2008/Community%20Detect
ion%20in%20Social%20Networks.pdf