Finding and Evaluating Community
Structure in Networks
Thiago Henrique F. da Paz
Roteiro
•
•
•
•
•
Introdução
Tipos de abordagens
Algoritmo proposto
Aplicações
Conclusão
Introdução
• Comunidades
– Divisão da rede em grupos
– Nós bastante conectados dentro dos grupos
– Poucas conexões entre os nós de grupos
diferentes
Introdução
Introdução
• Vários algoritmos para se identificar
comunidades
• Diferentes métricas utilizadas
• Relacionadas com várias áreas
– Teoria dos grafos
– Ciência da Computação
– Sociologia
– Etc...
Introdução
• Mas pra que serve?
– Melhor visualização da rede
– Informações presentes nas comunidades
– Ligações entre comunidades também contém
informações valiosas
Métodos
• Detectar comunidades
– Pode-se utilizar várias métricas de similaridades
entre os nós
• Os algoritmos se dividem em duas grandes
classes:
– Aglomerativos
– Divisivos
Métodos
• Aglomerativos
– Inicialmente, a rede só tem nós, nenhuma aresta
– O grau de similaridade é calculada entre um par
de nós
– Arestas são inseridas entre os nós com maiores
valores de similaridade
Métodos
• Aglomerativos
– O processo pode parar a qualquer momento
– Após a execução, rede dividida em comunidades
bem definidas
• Ex: Rede de atores
– Um ator está ligado a outro se já trabalharam
juntos antes em algum filme.
Métodos
• Problema:
– O algoritmo só detecta melhor os nós do núcleo
das comunidades
– Estes possuem maior grau de similaridade
– Os nós mais distantes são deixados de lado, pois
não possuem um alto grau de similaridade
Métodos
• Aglomerativos:
Métodos
• Divisivos
– Nesta abordagem, os nós com grau de
similaridade mais baixa são desconectados
– Após sucessivas repetições, a rede vai ser dividida
em comunidades
– O processo pode ser parado em qualquer
momento
Grau de Intermediação
• Em inglês: Betweenness
• Conceito chave nos algoritmos apresentados
• Métrica usada nas arestas
Grau de Intermediação
• Exemplo: shortest-path betweenness
• Utiliza o conceito do caminho mais curto em
grafos
• Calcula-se o caminho mais curto entre todos
os pares de vértices
• A quantidade de caminhos que passam pela
aresta é seu grau de intermediação
Grau de Intermediação
• Exemplo: random-walk betweenness
• Ao invés de seguir o menor caminho, segue-se
por um caminho aleatório
• O número esperado de vezes que deve-se
passar por uma determinada aresta é o valor
do seu grau de intermediação
Algoritmo proposto
• O algoritmo proposto possui as seguintes
características:
– Algoritmo divisivo
– Utiliza a métrica do short-path betweenness
– Recalcula o grau de intermediação das arestas da
rede cada vez que uma aresta é removida
Algoritmo proposto
• O algoritmo basicamente é feito assim:
– Calcula-se o grau de intermediação das arestas da
rede
– Encontra a aresta com maior grau de
intermediação
– Remove esta aresta
– Recalcula o grau de intermediação das arestas
– Repete a partir do passo 2.
Algoritmo proposto
• Mas por quê recalcular?
– A cada remoção a rede se modifica
– E com essa modificação, os caminhos mais curtos
podem modificar
– Assim, uma aresta que não tinha um grau alto,
pode passar a ter
Implementação
• Exemplo:
– Calculo do grau de intermediação
– Por simplicidade, apenas um caminho entre os
vértices
– Utiliza-se busca em largura
– As arestas que ligam as folhas recebem valor 1
– As próximas arestas recebem valor da soma das
precedentes + 1
Implementação
• Exemplo:
– Calcula-se os valores para cada nós da rede
– O grau de intermediação de cada aresta é a soma
dos valores para cada um dos nós
Implementação
Implementação
• Exemplo: Supondo agora que existam vários
caminhos entre dois vértices
– Primeiramente, calcula-se a distância e o peso de
um nó até todos os outros
– O peso será utilizado para calcular o grau das
arestas
Implementação
1. O vértice inicial tem distância 0 e peso 1
2. Para cada vértice i adjacente ao inicial, a distância é
1 e o peso também é 1
3. Para cada vértice j adjacente a um desses vértices i
A. Se j não recebeu ainda nenhum valor, seu valor é di + 1
B. Se j já recebeu um valor e o valor é igual à di+1, então o
peso wj = wi + 1
C. Se j já recebeu um valor e o valor é menor que di+1, não
faz nada
4. Repete o passo 3 para todos os nós restantes
Implementação
• Para se calcular o grau de intermediação das
arestas
1. Para cada vértice i ligado a um dos vértices t que
são folhas, o peso da aresta entre eles é wi/wt
2. Para os outros vértices, o peso é 1 + a soma dos
pesos das outras arestas do nó, multiplicado por
wi/wt
3. Repete o passo 2 até se chegar ao nó inicial
Implementação
Implementação
• O algoritmo calcula isso para cada um dos nós
da rede
• A cada remoção, é calculado tudo novamente,
para cada um dos nós restantes...
Implementação
• Após tudo isso, surge uma questão:
– Como saber se a rede foi dividida realmente em
comunidades e se essas comunidades estão
corretas?
• O algoritmo sempre divide a rede em
comunidades, mesmo não havendo nenhuma
estrutura de comunidades presente na rede
Modularidade
• Modularidade
– Medida da qualidade da divisão feita na rede pelo
algoritmo
• Exemplo: Se foram criadas k comunidades na
rede:
– Cria-se uma matriz K x K, onde cada elemento ei,j
da matriz é a fração das arestas que ligam vértices
da comunidade i para a comunidade j
Modularidade
• Logo, o traço da matriz (a soma dos elementos
da diagonal principal) é a fração das arestas
que ligam vértices da mesma comunidade
• Ou seja, quanto maior o valor, melhor ficou a
divisão da rede
Modularidade
• Porém, só este valor não diz muito coisa...
• Se for colocados todos os vértices numa única
comunidade, o valor é praticamente 1 (100%),
não dando nenhuma informação realmente
relevante
Aplicação
• Zachary’s karate club network
Aplicação
Aplicação
Conclusões
• Os algoritmos se dividem basicamente em
duas classes: aglomerativos e divisivos
• Existem diversas métricas que podem ser
utilizadas nos algoritmos que identificam
comunidades em redes
• A inserção de um passo a mais para recalcular
o grau de intermediação das arestas melhorou
a taxa de acerto
Referências
• [1] Newman M, Girvan M. Finding and
evaluating community structure in networks.
August 2003
• [2] Freeman L. A set of measures of centrality
based upon betweenness. Sociometry 40, 3541. 1997
Dúvidas