Eduardo Menezes Pires
[email protected]
Marcelo Machado da Paixão
[email protected]
Centralidade
Análise da centralidade, redes de
terrorismo, redes de contágio
Centro de Informática - UFPE
2012.1
Roteiro
• Introdução
• Definições
– Centralidade
– Proximidade
– Intermediação
• Aplicações
– Redes de Terrorismo
– Redes de Contágio
– Market Graph
• Referências
INTRODUÇÃO
Grafos
• Um grafo é uma estrutura G(V;E) onde V é um
conjunto de vértices (ou nós) e E é o conjunto
de subconjuntos de dois elementos de V,
denomidas arestas de G.
Grafos
• Conexidade de um grafo está relacionada à
possibilidade de transmissão de fluxo de um
vértice a outro, utilizando as arestas existentes
• Grafo conexo
– Possibilita a ligação entre todos os seus vértices
através das arestas
• Grafo desconexo
– Dois subconjuntos de vértices disjuntos
Grafos - Aplicação
• Redes Sociais
• Redes de Transportes
– Cidades, estações de trem
• Mercado Financeiro
– Del-Vecchio, Galvão, Silva. Medidas de Centralidade da Teoria dos Grafos aplicada a
Fundos de Ações no Brasil.
Centralidade - Objetivos
• Quais são os nós estruturalmente
importantes?
• Quais são os nós relevantes para o fluxo de
informação?
Centralidade
• Grau
– O nó A possui mais conexões com outros nós
B
G
C
A
F
D
E
Centralidade
• Proximidade
– O nó A está mais próximo aos outros nós da rede
B
G
C
A
F
D
E
Centralidade
• Intermediação
– O nó A está sempre entre dois outros nós
quaisquer
B
G
C
A
F
D
E
DEFINIÇÕES
Grau de Centralidade
• Grau de Centralidade (Informação)
– Número de relações diretas que o nó estabelece
com os demais
n
CG (vk )   wkj
j 1
– Medida pode ser normalizada
CG ( v k )
C 'G (vk ) 
n 1
Grau de Centralidade
– Grafos direcionados vs. Grafos não-direcionados
• In-degree
• Out-degree
– Centralidade local
– Dois nós com o mesmo Grau de Informação
podem não ter a mesma capacidade de influenciar
• Número de seguidores no Twitter não define a
influência dentro da rede
Proximidade
• Grau de Proximidade
– Distância total de um nó aos demais nós da rede
– Representa a velocidade de acesso do fluxo de
informação de um nó aos demais
• Custo mínimo
– Instalação de um centro de distribuição de
mercadorias
Proximidade
– Eficiência e independência
– Redes desconectadas: uso limitado
– Nós adjacentes a nós de alto Grau de Proximidade
também terão alto Grau, mas não a mesma
importância
• Redes de co-autoria: aluno + professor orientador
Intermediação
• Medida de Intermediação
– O quanto um nó está no caminho geodésico entre
outros nós
– Importância do nó em função da passagem de
fluxo por ele
• Controle do tráfego da informação na rede
– Aplicações
• Redes de transmissão da tuberculose
Intermediação
– Nós com alto Grau de Intermediação podem
perturbar ou atrasar a comunicação na rede
– Conectar comunidades diferentes
– Alto poder de tornar a rede um grafo desconexo
Outras Medidas de Centralidade
• Autovetor (Eigenvector)
– Relevância do nó a partir dos nós vizinhos
• Se um nó está ligado a outros centrais, então o referido nó
terá alta Centralidade de Autovetor
• Alcance (Reach)
– Links indiretos
• PageRank
– Análise de ligações
– Nós centrais são os mais referenciados
Centralidade
Aplicações
REDES DE TERRORISMO
Redes de Terrorismo
Atentados do 11 de setembro
•
•
•
•
19 terroristas do Al-Qaeda
4 aviões sequestrados
2996 pessoas morreram
Muitas questões ainda abertas sobre o
atentado
Contexto
Estudo de caso
• Mapear a rede
terrorista
• Valdis Krebs
Metodologia
• Valdis Krebs, consultor de Cleveland, decidiu mapear os
sequestradores do 11/9
• Busca de padrões de rede para revelar táticas da AlQaeda
• Necessidade de ter um protótipo visual
• Malcom Sparrow (Sparrow, 1991) realizou estudo sobre
uso da análise de redes sociais no contexto de
atividades criminosas
Metodologia
Fundamentos
• Dinâmica: Redes desse tipo estão em constante
mudança
• Incompletude: Nós e ligações serão perdidos
• Limites difusos: Difícil decidir pela inclusão de
um nó
Metodologia
• Rede criada iterativamente
• Links medidos pelo tempo que os terroristas se
conhecem/convivem
Métricas utilizadas
• Grau
• Proximidade
• Intermediação
Análise das redes socias
• Atualmente a análise de redes sociais (SNA) tem sido usada para
expor atividades criminosas
• Método muito útil para estruturar conhecimento da investigação
• Na análise da rede terrorista, sabia-se quem procurar.
• Exige cuidado com culpa por associação (conhecer um terrorista
não prova envolvimento, mas sugere investigação)
• Muito difícil prever ataques, mais usada como mecanismo de
acusação)
Coleta dos dados
• Times
• Wall Street Journal
• Washington Post
• Google
Estruturando
Tipos de link entre terroristas:
• Forte: Viviam juntos / Mesma escola
• Médio: Viajavam juntos / Reuniões
• Fraco: Transações comerciais / Conheciam
ocasionalmente
Mapeando a rede
• Uma vez descobertos, acompanhou-se os
passos
• Gradativamente novos links são incluídos
(com cuidado) e esses são investigados e
acompanhados
Mapeando a rede
Mapeando a rede
• A partir desses desmembramentos os
indivíduos chave começam a se destacar
Estudo da rede
• Muitos terroristas não
tinham ligações entre si
• Os 19 sequestradores
tinham outros cúmplices
Estudo da rede
• Reuniões criavam
“atalhos” na rede e
reduziam a
dispersão do grupo
Estudo da rede
Estudo da rede
Resultados
• Liderança inquestionável de Mohammed Atta
• Redes secretas funcionam de forma diferente.
• Dificuldade da rede entre balancear sigilo/discrição e repasse de tarefas
• Rede com aumento de conectivadade em períodos de mais atividade
• Membros da rede não tem muito contato com pessoas de fora da rede
• Aparentemente muitos laços se concentram nos pilotos
• Diz-se que, para enfraquecer a rede, é preciso alvejar os nós com
habilidades únicas
Conclusão
• O melhor método seria com varias agências de
inteligência agregando infos individuais num
mapa maior abrangente
• No compartilhamento, uma visão mais apurada
dos perigos é estabelecida
• Necessidade de construir uma rede de
informação e partilha melhor que as dos
terroristas
Aplicações
REDES DE CONTÁGIO
Redes de contágio
Tuberculose
• Doença infecciosa que mais mata no mundo (2
milhões/ano)
• 1/3 da população mundial está infectado pelo bacilo de
Koch (mas a mais preocupante é a Mycobacterium
tuberculosis)
• Nos EUA foram registrados 14000 casos em 2005
Porque usar análise?
• Controle da TB depende de um processo caro e complexo chamado
exame de contato, que avalia pessoas expostas a pacientes com TB
• Métodos pra priorizar os examinados ajuda desperdício de recursos
e tempo
• Atualmente os registros são isolados e em papel, não permitindo
uma estratégia sistemática de análise dos vínculos
• Análise da rede vem como complemento para o controle da TB
• Dados do serviço de saúde foram processados por análise de rede e
foi testada a hipótese de que contatos priorizados teriam mais
chance de possuir TB latente
Metodologia
•
Municípios com histórico de 5 casos de TB/ano apresentaram 18 pacientes e 17
suspeitos em 9 meses (em 2002)
•
O primeiro paciente ligado ao surto tinha sido preso 5 vezes entre 1996 e 2001 e
seu primeiro sintoma apareceu no fim de 200.
•
Em 9 meses ele compartilhou moradia com família e 3 munícipios de Oklahoma
•
4 visitas a emergências de hospitais
•
3 semanas de trabalho como lavador de pratos
•
22 dias numa cadeia da cidade
•
Em julho de 2001 foi diagnosticado com TB pulmonar
Metodologia
Classificação do link dos pacientes:
• Próxima: > 4 horas de exposição
• Casual: < 4 horas de exposição
• Indeterminada: incapaz de dizer o tempo
Metodologia
As três métricas mencionadas foram usadas:
• Grau
• Proximidade
• Intermediação
Resultados
Excetuando-se os contatos no hospital e trabalho:
• Taxas maiores que 40% para TB positivo
294 contatos nesses 9 meses:
• 251 (85%) foram localizados e avaliados
• 106 (42%) deram positivo para TB
Resultados
Resultados
Acerca dos primeiros 34 casos secundários:
• 1019 identificados
• 749 indivíduos
• 609 chamados para exame
• 73 deram positivo
Resultados
Vizualização dos 35 primeiros casos secundários de TB e seus 1039 contatos – sudoeste de Oklahoma, 2002.
Resultados
Vizualização dos 35 primeiros casos secundários de TB e seus contatos categorizados em necessidade de tratamento
Conclusão
• Embora custosas, investigações de contatos são
essenciais pro controle da TB
• Já existe muito dado coletado mas não é feita a análise
como uma rede
• Diminui-se o desperdício de recursos
• Agiliza-se a localização dos possíveis casos
• Reduz a transmissão da bactéria
Aplicações
MEDIDAS DE CENTRALIDADE
APLICADA A FUNDOS DE AÇÕES
Aplicações – Market Graph
• Fatores que influenciam o preço das ações
– Variação do valor patrimonial
– Maior demanda por uma ação
– Instabilidade da moeda
– Taxa de câmbio
– etc
• Identificar a existência de um agente líder no
mercado acionário
Aplicações – Market Graph
•
•
•
•
Ativos são os nós
Relações entre os ativos
Dados utilizados são de 2003 ~ 2007
Análise empírica ano a ano
Aplicações – Market Graph
Aplicações – Market Graph
• Resultados
– Banco Western e Itaú foram líderes 4 dos 5 anos
– Representação e interpretação do market graph
deu uma nova visão da estrutura do mercado de
valores
– Identificação das instituições líderes, que exercem
maior influência sobre as demais instituições no
mercado de fundo de ações do Brasil
– Entretanto, não há indícios que sugerem que o
líder é o que tem maior rentabilidade
Referências
Del-Vecchio, Renata; Galvão, Délio; Silva, Leonardo; de Lima, Renato.Medidas de Centralidade da Teoria dos
Grafos aplicada a Fundos de Ações no Brasil. UFF, 2009.
Silva, Thiago S. A. Um Estudo de Medidas de Centralidade e Confiabilidade em Redes. Dissertação de
Mestrado, CEFET/RJ, 2010
Alejandro, Velásquez A. O.; Norman, Aguilar G. Manual Introdutório à Análise de Redes Sociais – Medidas de
Centralidade. 2005
MARTELETO, Regina Maria. Análise de redes sociais: aplicação nos estudos de transferência da informação.
Ciência da Informação, Brasília, v. 30, n. 1, p. 71-81, 2001.
Borgatti, Steve. Centrality. Analytic Tech. Artigo disponível em
http://www.analytictech.com/networks/centrali.htm. Acessado em 6 de março de 2012.
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1805030/?tool=pubmed , acesso em 9 de março de 2012.
http://bvsms.saude.gov.br/html/pt/dicas/dica_tuberculose.html , acesso em 9 de março de 2012.
http://en.wikipedia.org/wiki/September_11_attacks , acesso em 9 de março de 2012.
http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 , acesso em 9 de março de
2012.
http://globalguerrillas.typepad.com/globalguerrillas/2004/04/mapping_terrori.html , acesso em 9 de março de
2012.
http://www.land.ufrj.br/~daniel/rc/slides/aula_4.pdf, acesso em 12 de março de 2012.
Obrigado!
Eduardo Menezes Pires
[email protected]
Marcelo Machado da Paixão
[email protected]