Tópicos Avançados em Inteligência Artificial
Prof. Ricardo Prudêncio
Community Structure in Jazz
de Pablo M. Gleiser e Leon Danon
apresentado por Bernardo Reis
Agenda





Introdução
Conceitos básicos
Análise estatística
Análise de estrutura de comunidade
Conclusões
2
Jazz
 Gíria de origem desconhecida
 Chicago, 1915
 Gênero musical




Mistura de tradições africanas e européias
Comunidades afro-americanas
Swing, espontaneidade, improviso, individualidade
Bebop, cool jazz, hard bop, modal jazz, free jazz, latin
jazz, post bop, soul jazz, jazz funk, smooth jazz, acid
jazz, nu jazz, jazz rap, jazzcore, ...
3
Jazzistas








Miles Davis
Louis Armstrong
John Coltrane
Ella Fitzgerald
Sarah Vaughan
Billie Holiday
Dizzie Gillespie
...
4
Objetivo do Trabalho
 Estudar a rede de colaboração entre jazzistas
 A nível de indivíduos
 A nível de bandas
 Analisar a estrutura de comunidade
 Analisar a topologia da rede de colaboração
5
Conceitos Básicos
 Redes sociais
 “A social network is a set of people or groups each of which has
connections of some kind to some or all of the others” (Jan Rupnik)
 Comunidade
 “Communities appear in networks where vertices join together in tight
groups that have few connection between them” (Gleiser et al.)
 Grau – quantidade de conexões de um dado nó
 Distância média – média das quantidades mínimas de conexões
entre cada par de nó
 Clustering – subgrupos em um conjunto grande de dados que
possuem similaridade de alguma categoria
6
Rede de Jazz
 Banco de dados The Red Hot Jazz Archive
 198 bandas
 1275 nomes de músicos
 Entre 1912 e 1940
 Considerações:
 Sem distinção temporal
 1 artista com vários nomes
 Henry Allen, Red Allen e Henry Red Allen
 Desconhecidos são classificados como unknown.
7
Distribuição de Músicos
 Pico entre 5 e 10 músicos
 Bandas com até 171 músicos
8
Distribuição de Músicos
9
Rede de Colaboração
 De indivíduos
 Cada vértice é um músico
 Dois vértices estão conectados se eles tocaram na
mesma banda
 Distância média = 2.79
 De bandas
 Cada vértice é uma banda
 Dois vértices estão conectados se eles têm um
músico em comum
 Distância média = 2.26
10
ANÁLISE ESTATÍSTICA
Análise Estatística
 Pontos de vista
 Microscópico – músicos individuais
 De maior granulação - bandas
 Distribuição cumulativa de grau – P(k)
 Grau de clustering - Ck
 Grau médio de vizinhos mais próximos - Knn
12
Distribuição Cumulativa de Grau – P(k)
 Uma forma de apresentar a Distribuição de
Grau
 Fração de nós que têm grau maior ou igual a k
13
P(k) de músicos
 Decaimento
devagar
em formato
de leiede
potência
“Estes músicos
funcionam
como hubs
conectam
 Para valores
deou
k até
170simplesmente
(tamanho da maior
banda)nas
muitas
bandas
eles
tocaram
poucasdecaimento
bandas que incluíam o maior número de
 Rápido
músicos?”
 Acima de 170
14
P(k) de bandas
 Comportamento exponencial esticado
 Sugere que as bandas são interconectadas por um número
característico de links.
15
Grau Médio de Vizinhos Mais Próximos
 Medida de correlação entre o grau de um nó e
o grau dos seus vizinhos
 Probabilidade condicional de que um nó de grau k
se conecte a um nó de grau k’
16
Knn - Indivíduos
 Knn varia com k
 Implica em correlação entre o grau dos vértices
conectados
 Knn cresce, quando k cresce
 Assortative mixing?
17
Knn - Bandas
 Knn flutua sobre um valor constante
 Não existe correlação entre o grau dos vértices
18
Coeficiente de Clustering - Ck
 Fração dos vizinhos de um nó com grau k que
estão conectados
 Medida da probabilidade de que dois vizinhos de
um nó também sejam vizinhos
 Redes reais, particularmente redes sociais,
tendem a ser altamente agrupadas
19
Coeficiente de Clustering - Ck
 Músicos são altamente agrupados
 Ck ≈ 1 para k até 30
 Então decaimento devagar com oscilações
 Bandas também são altamente agrupadas
Rede de músicos
Rede de bandas
20
Conclusões
 Possível assortative mixing na rede de músicos
 Nenhuma correlação na rede de bandas
 Como saber se essa rede é realmente a rede
de colaboração de músicos de jazz?
 Pode existir melhores maneiras de construir
essa rede?
21
ANÁLISE DE ESTRUTURA DE
COMUNIDADE
22
Análise de Estrutura de Comunidade
 Estrutura de comunidade
 Propriedade de redes cujos nós se agrupam fortemente e
cada grupo possui poucos laços entre si
 Análise do comportamento dos indivíduos e
grupos
 Algoritmo de Girvan e Newman
23
Algoritmo de Girvan e Newman
 Objetivo:
 Detectar comunidades em uma rede social
 Como:
 Isolar comunidades altamente “clusterizadas”
 Índices de centralidade
 Importância relativa de uma aresta em um grafo
24
Algoritmo de Girvan e Newman
 Edge betweenness
 O número de caminhos mínimos entre pares de
nós que atravessam aquela aresta
25
Algoritmo de Girvan e Newman
Algoritmo
Entrada: grafo G de uma rede de colaboração
Saída: grafo G’ subdividido com comunidades isoladas
1:
Para cada aresta A em grafo G faça
Calcular edge betweenness de A
2:
Remover a aresta Meb de G com maior edge betweenness
3:
Para cada aresta B de G afetada pela remoção Meb faça
Calcular edge betweenness de B
4:
Repetir a partir do passo 2 até não sobrar arestas
26
Análise de Estrutura de Comunidade
 Representação visual
 Dendograma (árvore binária)
 Bifurcações = Remoção de uma aresta
 Folhas = Vértices do grafo
27
Communities in e-mail network of
University Rivora i Virgili
28
Análise de Estrutura de Comunidade
 Resultados
 2 grandes ramos
 Segregação racial
 Assortative mixing
Músico
Músico com k > 170
Raiz da árvore
29
Análise de Estrutura de Comunidade
 Estrutura de comunidade simples
 2 grandes comunidades
 Segregação racial
 Relação espacial
 Local de gravação preferido
30
Análise de Estrutura de Comunidade
 Análise Quantitativa
 Distribuição cumulativa do tamanho da comunidade – P(s)
 Comparação com rede de e-mails da Universitat Rovira
i Virgili
31
Análise de Estrutura de Comunidade
 Conclusões
 Assortative mixing na rede de músicos
 Segregação racial entre os músicos
 Divisão em comunidades tem correlação geográfica
com o lugar de gravação
 Formato de P(s) similar a uma rede de e-mails
Garante que as redes criadas capturam ingredientes
essenciais da rede de colaboração de músicos de jazz
32
Referências
 Gleiser, P. e Danon, L., “Community Structure in Jazz”,
Advances in Complex Systems, Vol. 6, n. 4, 2003.
 Rupnik, J., “Finding Community Structure in Social Network
Analysis – Overview”, Intl. Multiconference Information
Society, Slovenia, 2006.
 Pastor-Satorras, R., Vázquez, A. e Vespignani, A.,
“Dynamical and Correlation Properties of the Internet”,
Physical Review Letters, Vol. 87, n. 25, 2001.
 Guimerà, R. et al., “Self-similar community structure in
organisations”, Physical Review E, Vol. 68, n. 6, 2006.
 Girvan, M. e Newman, M. E. J., “Community structure in
social and biological networks”, Proceedings of the National
Academy of Sciences of the USA, Vol. 99, 2002.
33