Henrique Menezes
Pedro Lopes





Introdução
Detecção de Comunidades
Método Proposto
Redes Geradas por Computador
Redes Reais
◦ Estrutura de Comunidade Conhecida
◦ Estrutura de Comunidade Não Conhecida


Demonstração
Conclusão

Muitos sistemas tem a forma de rede
◦ Ex.: Redes sociais, redes de conhecimento, web,
cadeias alimentares, redes metabólicas, etc.

Pesquisadores têm focado em algumas
propriedades que essas redes compartilham
◦ Efeito mundo pequeno
◦ Desvio a direita das distribuições de graus
◦ Clustering ou transitividade da rede

Outra propriedade comum a muitas redes
◦ Estrutura da comunidade

Comunidade
◦ Subconjuntos de vértices em que conexões vérticevértice são densas, mas entre os subconjuntos as
conexões são menos densas.
◦ Nós da rede estão unidos em grupos coeso, entre
os quais existem apenas ligações mais frouxas.

Método para detecção de comunidades
◦ Índices de centralidade para encontrar limites da
comunidade

Aplicações práticas:
◦
◦
◦
◦

Redes
Redes
Redes
Redes
sociais: pode indicar grupos reais
de citação: artigos de um mesmo topico
metabólicas: ciclos e grupos funcionais
na Web: páginas sobre temas relacionados
Ser capaz de identificar estas comunidades
poderiam nos ajudar a entender e explorar as
redes de forma mais eficaz

Método Tradicional
◦ Clustering hierárquico
 Baseado em pesos entre dois vértices
 Número de caminhos independentes de nós (nodeindependent) ou arestas (edge-indepentent)
 Número total de caminhos entre os vértices
 Agrupa os vértices, adicionando arestas de acordo com
os pesos
◦ O grafo resultante pode ser representado por
estrutura de árvore

Árvore de clustering hierárquico
(dendograma)

Método Tradicional
◦ Possui resultados razoáveis
◦ Falha
 Vértices periféricos ficam fora da comunidade a qual
deveriam pertencer

Caso de falha
B

Intermediação de vértices
◦ Medida de centralidade de um vértice
G
C
A
F
D
E
◦ Mede a frequência com que o nó aparece no menor
caminho entre dois nós quaisquer
◦ Pontecial para conectar comunidades diferentes
◦ Eliminar nós de alta intermediação pode ter o efeito
de desconectar a rede
Alta Intermediação
(pontos críticos para
disseminação)

Algoritmo
1. Calcula-se o grau de intermediação de cada
aresta da rede
2. Remove-se a aresta com maior grau de
intermediação
3. Calcula-se o grau de intermediação de todas as
arestas afetadas pela remoção
4. Volta para o passo 2 até que não reste nenhuma
aresta

Parâmetros
◦
◦
◦
◦

128 vértices
4 comunidades
32 vértices por comunidade
Grau médio z igual a 16
Procedimento
◦ Arestas inseridas aleatoriamente para cada par de
vértices
 𝑃𝑖𝑛 - probabilidade de ligação com um vértice da
mesma comunidade (intracommunity)
 𝑃𝑜𝑢𝑡 - probabilidade de ligação com um vértice de
outra comunidade (intercommunity)

Zachary’s Karate Club
◦ Rede de amizade
◦ Clube que foi divido após disputa entre o
administrador e instrutor
◦ Foi ignorado o grau de afinidade

Dendograma gerado a partir do Proposto

Dendograma gerado a partir do Método
Tradicional

Observações
◦ O algoritmo conseguiu detectar as comunidades
formadas
◦ Previsão da evolução da rede
◦ Falha:
 O único caso de falha foi o nó 3

College Football
◦ Vértices: times de futebol americano da divisão I da
liga do ano de 2000
◦ Arestas: jogos realizados numa temporada
◦ Estrutura de comunidade
 Conferências formadas por 8 a 12 times
 Obs: Cada time tem mais jogos com time que pertence a
mesma conferência em média

Observações
◦ Conferências identificadas com alta precisão
◦ Falha:
 A conferência Sunbelt foi separa em duas comunidades
◦ Motivo:
 A estrutuda da rede não corresponde a estrutura da
comunidade
 Sunbelt realizou mais jogos com a conferência Western
Athletic do que a própria conferência

Rede de Colaboração
◦ Vertices: 271 cientistas do Institute de Pesquisa de
Santa Fé nos anos de 1999 e 2000
◦ Arestas: co-autoria em artigos nos anos de 1999 e
2000
◦ Grau médio = 5

Rede de Colaboração
◦ 118 vértices
◦ Maior Componente

Rede de Colaboração
◦ Observações
 Identificação de áreas de pesquisa
 Divisão de subáreas
 Interesse de pesquisa de membro dominante
 Interessante: agrupamento por metodologia

Teia Alimentar
◦ Vértices: 33 taxa mais proeminetes de Chesapeak
Bay
 Espécies ou Gênero
 Grupos de espécies relacionadas
◦ Arestas: relação trófica entre vértices ligados
◦ Direção ignorada

Teia Alimentar

Teia Alimentar
◦ Observações
 Pelágicos vs Bênticos
 Ecossistemas razoavelmente independentes
 Bênticos relacionando com Pelágicos
 Nesse caso a divisão pode não ser apropriada
 Em cada grupo vários níveis tróficos observados
◦ Problema: teias alimentares são densas ou não
possuem estruturas de comunidade

TouchGraph
Aqui

Verificamos os métodos de detecção de
comunidade
◦ Clássico: núcleos fortementes conectados
◦ Proposto: intermediação de arestas



Vimos que esses métodos são úteis na
análise de redes e que o método proposto é
superior ao clássico
Várias melhorias podem ser realizadas ainda
para método proposto
Diversas aplicações podem ser realizadas a
partir da detecção de comunidades

[1] M. Girvan and M. E. J. Newman Community structure in social and
biological networks PNAS 2002 99 (12) 7821-7826;
doi:10.1073/pnas.122653799

[2] http://www.touchgraph.com/navigator