Henrique Menezes Pedro Lopes. Introdução Detecção de Comunidades Método Proposto Redes Geradas por Computador Redes Reais Estrutura de Comunidade Conhecida

Detecção de Comunidades

Henrique MenezesPedro 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

Roteiro

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

Introdução

Outra propriedade comum a muitas redes◦ Estrutura da comunidade

Comunidade◦ Subconjuntos de vértices em que conexões

vértice-vé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.

Introdução

Método para detecção de comunidades◦ Índices de centralidade para encontrar limites da

comunidade

Introdução

Aplicações práticas:◦ Redes sociais: pode indicar grupos reais◦ Redes de citação: artigos de um mesmo topico◦ Redes metabólicas: ciclos e grupos funcionais◦ Redes 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

Introdução

Método Tradicional◦ Clustering hierárquico

Baseado em pesos entre dois vértices Número de caminhos independentes de nós (node-

independent) 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

Detecção de Comunidade

Caso de falha

Detecção de Comunidade

Intermediação de vértices◦ Medida de centralidade de um vértice

◦ 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

Método Proposto

A

C

D

B

G

F E

Método Proposto

Alta Intermediação(pontos críticos para disseminação)

Algoritmo1. Calcula-se o grau de intermediação de cada

aresta da rede2. Remove-se a aresta com maior grau de

intermediação3. Calcula-se o grau de intermediação de todas as

arestas afetadas pela remoção4. Volta para o passo 2 até que não reste

nenhuma aresta

Método Proposto

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)

Redes geradas por computador

Redes geradas por computador

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

Redes ReaisEstrutura de Comunidade Conhecida


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

Redes ReaisEstrutura de Comunidade Não Conhecida

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

Demonstração

https://apps.facebook.com/touchgraph/?ref=ts

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

Conclusão

[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

Referência

?Dúvidas

Documents

Henrique Menezes Pedro Lopes. Introdução Detecção de Comunidades Método Proposto Redes Geradas por Computador Redes Reais Estrutura de Comunidade Conhecida